# Achieving Capacity Region of 2-users Weak GIC by Enlarging the Core in a
Nested Set of Polymatroids
in continuation of arXiv:2012.07820 entitled: “Optimality of Gaussian in
Enlarging HK Rate Region, and its Overlap with the Capacity Region of 2-users
GIC" 111This draft provides derivation details for an earlier submission
reported in [1] (also see [2]).

Amir K. Khandani E&CE Department, University of Waterloo, Waterloo, Ontario,
Canada<EMAIL_ADDRESS>
###### Abstract

This article shows that achieving capacity region of a 2-users weak Gaussian
Interference Channel (GIC) is equivalent to enlarging the core in a nested set
of polymatroids (each equivalent to capacity region of a multiple-access
channel) through maximizing a minimum rate, then projecting along its
orthogonal span and continuing recursively. This formulation relies on
defining dummy private messages to capture the effect of interference in GIC.
It follows that relying on independent Gaussian random code-books is optimum,
and the corresponding solution corresponds to achieving the boundary in HK
constraints.

This article provides an alternative view to the results reported in [1]. It
is a continuation of an earlier report [2]. It provides an alternative method
to prove optimality of independent Gaussian density functions in generating
random code-books in 2-users GIC, initially reported in [1]. For the sake of
simplicity, discussions are focused on the weak interference, i.e., $a<1$ and
$b<1$, and on the case that both users have both private and public messages
(see [1] for related conditions). Other cases can be handled using the
arguments presented here by setting some of the code-books to be empty in the
formulation.

##  1 Introduction

###  1.1 Optimality of Gaussian Random Code-books in All-Private Messaging

Let us assume, in the optimum solution to a 2-users GIC, power allocated to
private messages are equal to $\hat{P}_{1}(\mu)$ and $\hat{P}_{2}(\mu)$,
respectively. Nested optimality condition derived in [1] states that the
solution to the same 2-users GIC with power constraints
$P_{1}=\hat{P}_{1}(\mu)$ and $P_{2}=\hat{P}_{2}(\mu)$ will be composed of
private messages only. Note that $\hat{P}_{1}(\mu)$ and $\hat{P}_{2}(\mu)$ are
the lowest power levels for which relying on private messages only results in
an optimum solution. Another perspective is to allow for private messages
only. In this case, the power budget for each private messages will be the
entire available power, i.e., $P_{1}$ and $P_{2}$, respectively, however, as
we will see, one of the two transmitters may use less than its corresponding
maximum available power. For $\mu\leq 1$, it will be transmitter 2 which may
not send at full power $P_{2}$. For $\mu\geq 1$, it will be transmitter 1
which may not send at full power $P_{1}$. In any event, the inclusion of
constraints on power renders the problem intractable. For this reason, we rely
on the parameter of entropy that relates to power and random coding density
function. We will be dealing with channels with noise terms that are
independent of channel input and are composed of additive Gaussian noise plus
interference. In any such channel, a straightforward application of data
processing theorem confirms that, the lower is the entropy of noise plus
interference, the higher will be the corresponding capacity value.

A review of Entropy Power Inequality: Consider two random variables; $A$ has
an entropy $H_{A}$ and a power $P_{A}$, and $G$ is Gaussian
$\mathcal{N}(0,1)$. We have

$e^{2\breve{H}_{A}}+e^{\log_{2}(2\pi e)}\leq e^{2H\left(A+G\right)}\leq
e^{\log_{2}\left(2\pi e(P_{A}+1)\right)},$ (1)

where $H(\alpha)$ specifies the entropy of the random variable $\alpha$. The
left hand side, which is an expression of Entropy Power Inequality, is
satisfied with equality if $A$ is a Gaussian of entropy $H_{A}$, and
consequently of power

$\tilde{P}_{A}=\frac{1}{2\pi e}2^{2H_{A}}.$ (2)

This case means among all densities with with a limit on entropy, Gaussian
results in minimizing the entropy of the sum, $A+G$.

The right hand-side, which is an expression of maximum entropy property of
Gaussian, is satisfied with equality if $A$ is Gaussian of power $P_{A}$. This
case means among all densities with a limit on power, Gaussian results in
maximizing the entropy of the sum, $A+G$.

Note that, if $\tilde{P}_{A}=P_{A}$, or equivalently, $H_{A}=0.5\log_{2}(2\pi
eP_{A})$, then the upper bound and the lower bound in 1 coincide. This case
means, in the sense of the two limits in 1, Gaussian is the minimizer and also
the maximizer of the entropy of $A+G$, since minimum and maximum values
coincide. $\blacksquare$

Private messages result in a two-inputs channel, maC1, at $Y_{1}$ and a two-
inputs channel, maC2, at $Y_{2}$. The two inputs at $Y_{1}$ are the private
message of user 1 and the interference caused by the private message of user
2, and likewise for $Y_{2}$. Let us consider maC1 and maC2, each composed of
two layers: $L^{(1)}_{1}$, $L^{(1)}_{2}$ for maC1 and $L^{(2)}_{1}$,
$L^{(2)}_{2}$ for maC2 (see Fig. 1).

Figure 1: Layers involved in all-private messaging.

Let us assume in the optimum solution, we have
$H\left(L^{(1)}_{1}\right)=\breve{H}_{1}$ and
$H\left(L^{(2)}_{1}\right)=\breve{H}_{2}$. Let us write the optimization
problem by explicitly adding these two constraints.

Maximize $\displaystyle R_{ws}=R(L^{(1)}_{2})+\mu R(L^{(2)}_{2})$ (3) where
(4) $\displaystyle R\left(L^{(1)}_{2}\right)$
$\displaystyle=H\left(L^{(1)}_{2}+L^{(1)}_{1}+z_{1}\right)-H\left(L^{(1)}_{1}+z_{1}\right)$
(5) $\displaystyle R\left(L^{(2)}_{2}\right)$
$\displaystyle=H\left(L^{(2)}_{2}+L^{(2)}_{1}+z_{2}\right)-H\left(L^{(2)}_{1}+z_{2}\right)$
(6) $\displaystyle H\left(L^{(1)}_{1}\right)$ $\displaystyle=\breve{H}_{1}$
(7) $\displaystyle H\left(L^{(2)}_{1}\right)$ $\displaystyle=\breve{H}_{2}.$
(8)

The optimum solution subject to 3 to 8 will be the same as the optimum
solution to 3 to 6. Now let us relax the problem. Relaxation is based on
allowing the probability density functions for the four code-layers
$L^{(1)}_{1}$, $L^{(1)}_{2}$, $L^{(2)}_{1}$ and $L^{(2)}_{2}$ to be
independent of each other. Selecting the random coding density for
maximization of 3 narrows down to maximization of the entropy values
$H\left(L^{(1)}_{1}+L^{(1)}_{2}+z_{1}\right)$ and
$H\left(L^{(2)}_{1}+L^{(2)}_{2}+z_{2}\right)$, and minimizing the entropy
values of $H\left(L^{(1)}_{1}+z_{1}\right)$ and
$H\left(L^{(2)}_{1}+z_{2}\right)$ subject to 7 and 8 and power constraints.
Assuming $z_{1},z_{2}$ are $\mathcal{N}(0,1)$ and applying entropy power
inequality to $L^{(1)}_{1}+z_{1}$ and to $L^{(2)}_{1}+z_{2}$, it follows

$\displaystyle e^{2H\left(L^{(1)}_{1}+z_{1}\right)}$
$\displaystyle\leavevmode\nobreak\ \geq\leavevmode\nobreak\
e^{2\breve{H}_{1}}+e^{\log_{2}(2\pi e)}$ (9) $\displaystyle
e^{2H\left(L^{(2)}_{1}+z_{2}\right)}$ $\displaystyle\leavevmode\nobreak\
\geq\leavevmode\nobreak\ e^{2\breve{H}_{2}}+e^{\log_{2}(2\pi e)}.$ (10)

with equality if $L^{(1)}_{1}$ and $L^{(2)}_{1}$ are Gaussian. Note that
equality conditions in 9 and 10 result in minimizing the entropy of
$H\left(L^{(1)}_{1}+z_{1}\right)$ and $H\left(L^{(2)}_{1}+z_{2}\right)$,
respectively. Relying on the relationship between entropy and power in a
Gaussian random variable, the power of interference terms and consequently the
power of code-book used by each transmitter will be determined. Given the
power values, the entropy of signal terms, i.e.,
$H\left(L^{(1)}_{1}+L^{(1)}_{2}+z_{1}\right)$ in 5 and
$H\left(L^{(2)}_{1}+L^{(2)}_{2}+z_{2}\right)$ in 6 are maximized, since all
random variables in summations constructing the two signals are Gaussian, each
with its maximum allowable power value. Note that one of the two transmitters
may use only part of its power budget, and in this case, the allowable power
value for that transmitter is governed by some other considerations to be
discussed.

A question remains concerning the possibility of realizing the target entropy
levels $\breve{H}_{1}$ and $\breve{H}_{2}$ using Gaussian density functions,
and its impact on the signal terms. The answer to the question is positive
since Gaussian requires the least amount of power for a given entropy. In
other words, if some other density function has been capable of generating
entropy values $\breve{H}_{1}$ and $\breve{H}_{2}$ within the available power
budgets, then Gaussian density can do it as well. By selecting Gaussian
density functions to realize the target entropy levels, we are maximizing the
individual capacity values in 5 and 6 by minimizing the entropy of their
respective interference plus noise terms. For example, in 5, $L^{(1)}_{2}$ is
the signal and $L^{(1)}_{1}+z_{1}$ (a term independent from the corresponding
signal) is the noise-plus-interference. According to data processing theorem,
a channel with a noise of a lower entropy will have a higher capacity,
regardless of the impact of noise in signal term, i.e., in
$L^{(1)}_{2}+L^{(1)}_{1}+z_{1}$. On the other hand, the power of interference
term $L^{(1)}_{1}$ affects the second capacity term in 6. Indeed, in this
setup, as we are avoiding the use of public messages, one of the two
transmitters may not use its entire power budget. The important point is that
the transmitter sending less than full-power should rely on a Gaussian density
because it minimizes the impact of the interference term on the capacity
achieved by the transmitter sending at full power, and at the same time, it
maximize the entropy of both signal terms subject to the allowable power
values used by each transmitter. Expressing 3 as,

$\displaystyle R_{ws}$
$\displaystyle=H\left(L^{(1)}_{2}+L^{(1)}_{1}+z_{1}\right)-H\left(L^{(1)}_{1}+z_{1}\right)+\mu\left[H\left(L^{(2)}_{2}+L^{(2)}_{1}+z_{2}\right)-H\left(L^{(2)}_{1}+z_{2}\right)\right]=A+B$
(11) where $\displaystyle A=H\left(L^{(1)}_{2}+L^{(1)}_{1}+z_{1}\right)-\mu
H\left(L^{(2)}_{1}+z_{2}\right),\leavevmode\nobreak\ \leavevmode\nobreak\
B=\mu
H\left(L^{(2)}_{2}+L^{(2)}_{1}+z_{2}\right)-H\left(L^{(1)}_{1}+z_{1}\right).$
(12)

Note that the power of interference term $L^{(2)}_{1}$, denoted as
$P\left(L^{(2)}_{1}\right)$, satisfies (see Fig. 3 for definition of cross
channel gains $a$ and $b$),

$P\left(L^{(2)}_{1}\right)=bP\left(L^{(1)}_{2}\right),$ (13)

and $P\left(L^{(1)}_{1}\right)$ satisfies

$P\left(L^{(1)}_{1}\right)=aP\left(L^{(2)}_{2}\right).$ (14)

Replacing for entropy values of Gaussian terms, and then computing derivatives
of 11 and 12 with respect to the power values (subject to 13 and 14), it is
straightforward to show that $A$ and/or $B$ in 12 will be maximized by having
its corresponding transmitter to transmit at full power, i.e., at least one of
transmitters uses all its power budget.

Reference [1] shows that the lower part of the boundary curve, i.e., $\mu\leq
1$, for 2-users weak GIC starts from a corner point in which user 1 sends an
all-private message and user 2 sends an all-public message. The case
considered in this section does not permit the use of public messages, so the
corner point in an all-private signaling will correspond to user 1 sending a
private message at full-power and user 2 remaining silent. Then, in [1],
moving counterclockwise along the lower part of the boundary, the power
allocated to private message of user 2 gradually increases, while the power
allocated to its public message decreases. However, up to point $D_{3}$ (see
Fig. 11 of [1]) user 1 continues sending an all-private message at full power.
In an all-private signaling scheme presented in this section, the power
allocated to private messages will be the same as the case of [1], while
public messages accompanying the private messages in [1] will be dropped. This
allows moving from corner point $A$ to point $D_{3}$ by keeping the power of
private messages the same as in [1], while putting the power of accompanying
public messages (involved in forming Fig. 11 of [1]) equal to zero. An all-
private boundary curve does not extend beyond the counterpart of point $D_{3}$
(counterpart means the same point without public messages).

The arguments presented in this section, in terms of using Gaussian density
for interference term in order to minimize the entropy of the noise-plus-
interference, can be better understood by expressing the problem of computing
the lower part of the boundary curve as follows:

Maximize $\displaystyle
R\left(L^{(1)}_{2}\right)=H\left(L^{(1)}_{2}+L^{(1)}_{1}+z_{1}\right)-H\left(L^{(1)}_{1}+z_{1}\right)$
(15) Subject to: $\displaystyle
R\left(L^{(2)}_{2}\right)=H\left(L^{(2)}_{2}+L^{(2)}_{1}+z_{2}\right)-H\left(L^{(2)}_{1}+z_{2}\right)\equiv\mathsf{C}_{2}.$
(16)

In covering the lower part of the boundary, the value of $\mathsf{C}_{2}$ will
gradually increase in infinitesimal steps. As the objective is to maximize
$H\left(L^{(1)}_{2}+L^{(1)}_{1}+z_{1}\right)-H\left(L^{(1)}_{1}+z_{1}\right)$,
the step for increasing $\mathsf{C}_{2}$ to
$\mathsf{C}_{2}+\delta\mathsf{C}_{2}$ should be such that the entropy of the
noise term $H\left(L^{(1)}_{1}+z_{1}\right)$ is minimized, which justifies the
arguments starting from 9 and concluding $L^{(1)}_{1}$ should be Gaussian.
Using Gaussian code-books for other layers follow knowing $L^{(1)}_{1}$ is
Gaussian. A similar argument applies to the upper part of the boundary, i.e.,
$\mu\geq 1$, using 10 and concluding interference term $L^{(2)}_{1}$ should be
Gaussian.

In 7 and 8, the condition on the density functions are expressed in terms of
corresponding entropy values as parameters. Let us relax the problem (to
obtain an upper bound) where the probability densities of four layers:
$L^{(1)}_{1}$, $L^{(1)}_{2}$, $L^{(2)}_{1}$, $L^{(2)}_{2}$ are allowed to be
selected independently. Using Gaussian density for $L^{(1)}_{1}$ and
$L^{(2)}_{1}$ minimizes the entropy of additive noise-plus-interference in
channels formed at $Y_{1}$ and $Y_{2}$ (see 9 and 10). Note that, in selecting
a density function to realize certain entropy value, one needs to adhere to
existing constraints on power. Since Gaussian requires least amount of power
for a given entropy, if there exist densities satisfying

$\displaystyle H\left(L^{(1)}_{1}\right)=\breve{H}_{1}$ (17) $\displaystyle
H\left(L^{(2)}_{1}\right)=\breve{H}_{2}.$ (18)

subject to existing power constraints, then Gaussian density can also achieve
the target entropy values within the allowable power limits. With Gaussian
interference-plus-noise, the density of $L^{(1)}_{2}$ and $L^{(2)}_{2}$, which
are each the input to a channel with additive Gaussian noise-plus-interference
(noise-plus-interference term in each case is independent from corresponding
channel input) should be Gaussian. A remaining question concerns the role of
input power constraint in selecting the density functions for channel inputs,
i.e., $L^{(1)}_{2}$ and $L^{(2)}_{2}$. In the case of $L^{(1)}_{2}$, it is
always at full power, meaning that the lower and upper bound in 1 coincide.

A remaining point is to justify replacing the role of density function for
$L^{(2)}_{2}$ in 16 with the entropy value. The problem is the relationship
between density function and entropy value is not one-to-one. Moving along the
boundary can be also formulated in terms of an infinitesimal increase in the
entropy of $H\left(L^{(1)}_{1}\right)=\breve{H}_{1}+\delta H$ in 7. In the
context of all-private messaging discussed here, a $\delta H$ step in entropy
means increasing the power of private message of user 2 by $\delta P$, while
user 1 continues to transmit at full power. For a Gaussian $L^{(1)}_{1}$, a
fixed $\delta H$ is accompanied with minimum $\delta P$, i.e., minimum
increase in the power of additive noise-plus-interference in 15. In other
words, use of Gaussian density in view of 9 (for minimizing the entropy of the
additive noise-plus-interference) has also kept the power of additive noise-
plus-interference at $Y_{1}$ minimum. In other words, in 16, optimality
condition necessitates realizing $\mathsf{C}_{2}$ with minimum power for
$L^{(2)}_{2}$. If one could achieve the value of $\mathsf{C}_{2}$ with a lower
power for $L^{(2)}_{2}$, it would translates to a lower power for the additive
noise-plus-interference term at $Y_{1}$, which could be used to increase
$R\left(L^{(1)}_{2}\right)$, contradicting the optimality of the solution.
Gaussian $L^{(2)}_{1}$ minimizes the entropy of the interference-plus-noise at
$Y_{2}$ (see 10) and then using Gaussian $L^{(2)}_{2}$ would enable realizing
the target capacity value of $\mathsf{C}_{2}$ with minimum power. Note that
all these discussions are focused on $\mu\leq 1$, where $X_{1}$ sends at full
power, i.e., $P_{1}$, and $X_{2}$ may send at a power level less than $P_{2}$.

Noting above discussions, it is concluded that in the optimum solution to 15,
16 (while relaxing consistency condition, i.e., allowing independent density
functions for $L^{(1)}_{1}$, $L^{(1)}_{2}$, $L^{(2)}_{1}$, $L^{(2)}_{2}$), the
consistency conditions have been automatically satisfied. This means, the
optimum solution to the upper bound coincides with the optimum solution to the
original problem.

###  1.2 Considering both Public and Private Messages: Preliminaries

Consider a memory-less multiple-access channel with inputs
$X_{1},\ldots,X_{M}$ and output $Y$ described by conditional distribution
$f_{Y|X_{1},\ldots,X_{M}}(y|x_{1},\ldots,x_{M})$, where fixed and independent
density functions are deployed for generating random code-books. The capacity
region of such a channel forms a polymatroid [3]. Sum-capacity facet is
composed of $M!$ corner points which can be realized relying on different
orderings in successive decoding of messages. The optimum solution in
maximizing a weighted sum-rate falls on a corner point on the sum-capacity
facet, which, through ordering of messages in successive decoding, assigns
higher rate values to terms with a larger weight in the weighted sum-rate (see
Lemma 3.2 of [3]). Reference [4] shows that the fairest corner point,
maximizing the minimum rate in a memory-less multiple-access channel,
corresponds to ordering users according to their rate values in increasing
order from bottom to top and applying successive decoding from top to bottom.

Consider the problem of transmitting $M$ messages over a multiple-access
channel with additive Gaussian noise $\mathcal{N}(0,1)$. The solution is the
set of all rate vectors $\mathsf{R}$ satisfying:

$\mathsf{R}(S)\leq I\left(Y;X_{i},i\in S\leavevmode\nobreak\
|\leavevmode\nobreak\ X_{i},i\notin S\right)\leavevmode\nobreak\
\leavevmode\nobreak\ \forall S\subset\\{1,2,\ldots,M\\}\leavevmode\nobreak\
\leavevmode\nobreak\ \mbox{where}\leavevmode\nobreak\ \leavevmode\nobreak\
\mathsf{R}(S)=\sum_{i\in S}r_{i}.$ (19)

The goal is to maximize a weighted sum-rate
$L=\sum_{i=1}^{M}\lambda_{i}r_{i}$. The power used for sending message $i$ is
denoted as $p_{i}$. Instead of imposing a fixed limit on $p_{i},i=1,\ldots,M$,
the vector of power budgets, $\mathbf{p}=(p_{1},\ldots,p_{M})$, is limited by
a set of linear constraints with positive coefficients. This results in a
simplex region in the positive orthant, called a Power Vector Simplex, or
$\mathsf{PVS}_{M}$, hereafter.

Expressions in 19 are identical to the case of superposition coding with
successive decoding. The difference between the two formulations stems from
differences in constraints on power values. There are $2^{M}-1$ expressions
defining 19, with left hand sides composed of different sum-rates. Each rate
value appears in $2^{M/2}$ expressions. We are interested in maximizing a
weighted sum-rate, $R_{ws}$, over 19. The optimum solution will be a vector of
rates that maximizes $R_{ws}$ subject to the underlying power constraints.
Constraints on power are a set of linear (equality) terms over power values
allocated to different code-books. Assuming the optimum value is equal to
$R^{opt}_{ws}$, the optimization problem can be expressed as realizing
$R_{ws}=R^{opt}_{ws}$ using a power vector that satisfies the power
constraints and is Pareto minimal, i.e., a decrease in any of its power values
results in reducing the achieved $R_{ws}$. In other terms, the optimum rate
vector maximizes $R_{ws}$ with minimum power. Given an optimum rate vector,
the order of code-books can be changed if the set of constraints on their
respective power values permit. In such a case, there will be multiple optimum
solutions corresponding to permuting the positions of code-books in successive
decoding, and accordingly adjusting their power levels to achieve the same
optimum rate vector with shuffling of its components. For example, if the
constraint is on total power in a superposition code composed of $M$ code-
books, if a vector of rate $\vec{r}$ is achievable, different rate vectors
obtained by permuting the elements of $\vec{r}$ will be achievable as well. In
our case, constraints on power are such that only one order for successive
decoding can achieve $R^{opt}_{ws}$. In this case, the optimization problem is
equivalent to minimizing the power values for realizing a desired rate vector
subject to the optimum decoding order.

Let us use notation $\mathsf{PVS}_{M-K}(p_{1},\ldots,p_{K})$ to refer to power
simplex available to massages indexed by $K+1$ to $M$ if the power vector for
messages indexed by $1,\ldots,K$ is $(p_{1},\ldots,p_{K})$. Let us focus on
the rate of the first message (decoded last), and denote it by $r_{1}$. For a
given value of $r_{1}$, placing the message first minimizes the required
$p_{1}$, and thereby enlarges the Power Vector Simplex available to remaining
messages, i.e.,

$\mathsf{PVS}_{M-1}(\breve{p}_{1})\subset\mathsf{PVS}_{M-1}(\overline{p}_{1})\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \mbox{if}\leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \overline{p}_{1}<\breve{p}_{1}.$
(20)

Minimizing $p_{1}$ also reduces the amount of interference observed by
messages $2,\ldots,M$, which are all ordered above the first message. More
generally, let us assume, as part of problem definition, the rates of the
first $\ell$ messages (decoded last) are set at $r_{1}$ to $r_{\ell}$ .
Regardless of the form of power simplex, the optimum random coding for all
layers will be independent Gaussian. Using a Gaussian density for a layer
results in: (i) worst noise for layers above it, (ii) least amount of power
allocated to the layer, thereby maximally enlarging the $\mathsf{PVS}$
governing the power vectors available for remaining code-books above it, (iii)
the power of interference is minimized. Regardless of values of $r_{1}$ to
$r_{\ell}$ and the structure of $\mathsf{PVS}$, the positive impacts in (ii)
and (iii) are more advantageous than the negative impact in (i). Also see
Theorems 5, 6 and Example 1.

Remark: Let us consider maximizing a weighted sum-rate over a multiple-access
channel (or equivalently in a superposition code). The power constraints are
such that one of the non-zero rates in the optimum rate vector has zero weight
in the weighted sum-rate. The corresponding rate value contributes to the
formation of optimal solution by appearing in the left hand sides of $2^{M/2}$
expressions among the $2^{M}-1$ expressions in 19. This means, it indirectly
affects the achieved optimum value for the weighted sum-rate. Solution of
2-users GIC narrows down to minimizing the power required to realize all non-
zero rate values, which, directly or indirectly, affect the value of the
weighted sum-rate. $\blacksquare$

Following Theorem summarizes the above arguments.

######  Theorem 1.

Consider the problem of maximizing a weighted sum-rate over a multiple-access
region, or over the intersection of several multiple-access regions, subject
to power constraints captured by certain $\mathsf{PVS}$. Assume there is a
set, $S_{R}$, of rate values with zero weight in the weighted sum-rate, which
are assigned a non-zero rate value in the optimizing solution. This can be the
case only if, subject to the set of equations corresponding to active
constraints among the set in 19, the rate values with non-zero weight turn out
to be an increasing function of rate values in $S_{R}$.

###### Proof.

Having a non-zero rate value for a code-book always comes at a cost in terms
of power. Accordingly, power constraints permit allocation of power to code-
books that directly or indirectly result in improving the achieved weighted
sum-rate. For terms that have zero weight in the weighted sum-rate, the
relevance of their rate value to improvement in the weighted sum-rate is
indirectly embedded within the relationships imposed by the set of active
constraints among expressions in 19. On the other hand, the right hand sides
of the set of active constraints are a set of mutual information terms.
Optimization of random code-books and power allocation result in minimizing
the power (subject to the underlying $\mathsf{PVS}$) required to achieve the
rates that directly or indirectly affect the weighted sum-rate. ∎

Following Theorem will be beneficial is establishing the result of the Section
1.3.

######  Theorem 2.

Consider the problem of constructing a superposition code over an AWGN
channel, $\mathcal{N}(0,1)$, with $2$ layers. The objective is to maximize the
rate of the second layer. The total power is fixed at $\breve{P}$. The problem
is linked to a second problem which: (i) does not allow allocating zero power
to the first layer, and (ii) the power allocated to the first layer will be
minimized if the corresponding code-book is Gaussian. Use of Gaussian code-
books for both layers is optimum.

###### Proof.

The condition that “power allocated to the first layer will be minimized if
corresponding code-books is Gaussian” is equivalent to the condition that the
“mutual information between first layer and output should be larger than or
equal to a given value”, say $\breve{r}_{1}$. Rate of the second layer is
bounded by

$r_{2}\leq 0.5\log_{2}(1+\breve{P})-\breve{r}_{1}.$ (21)

The condition for equality in 21 is that both layers are Gaussian. ∎

Theorem 2 can be generalized to the case of maximizing a weighted sum-rate
over a superposition code (or a multiple-access channel) with $M$ messages.
Weighted sum-rate is defined over layers $\ell+1,\ldots,M$, and the power
allocated to layers $1,\ldots,\ell$ will be minimized if their code-books are
Gaussian. It follows that using independent Gaussian code-books for all layers
is optimum. As will be shown in Section 1.3, in the case of 2-users GIC, there
are two such superposition codes that are linked together. Each code-book in
one superposition code has a pair code-book in the second one. Random coding
alphabets in code-books forming a pair are obtained by scaling the output of
the same generator. Weighted sum-rate involves layers $\ell+1,\ldots,M$,
$\ell=M/2$, in the two superposition codes. The code-books in layers
$1,\ldots,\ell$ in one superposition code are paired with code-books in layers
$\ell+1,\ldots,M$ in the other one, and vice versa. Noting Theorem 2, use of
Gaussian code-books is optimum in terms of maximizing the weighted sum-rate
over the two superposition codes.

###  1.3 Construction of Code-books Relying on Infinitesimal Layers

Complexity of solving 22 to 34 is partially due to the inclusion of power
allocation problem. To overcome this issue, in [1], the power budget $P_{1}$
and $P_{2}$ are each divided into a continuum of $L_{1}=P_{1}/\delta$ and
$L_{2}=P_{2}/\delta$ infinitesimal values of power $\delta$, respectively,
each called an infinitesimal layer. $Y_{1}$ and $Y_{2}$, each receive all the
$L_{1}+L_{2}$ infinitesimal layers. There is a close connection between
“superposition coding in a point-to-point link" and “relying on separate
transmitters in a multiple-access channel". In particular, in both
configurations, using multi-level code-books with independent layers in
transmitter(s) and successive decoding in receiver(s) is optimum (assuming
memory-less channels). Relying on this viewpoint, the optimization problem in
22 to 34 can be considered as a setting in which $L_{1}+L_{2}$ separate
transmitters, each with power $\delta$, send their signals to two receivers,
$Y_{1}$ and $Y_{2}$. In this case, $Y_{1}$ and $Y_{2}$ will each receive
$L_{1}+L_{2}$ infinitesimal code-books, with a one-to-one correspondence
between code-books at $Y_{1}$ and those at $Y_{2}$ (in the sense that two
copies, with different scale factors, of each infinitesimal code-book are
received, one at $Y_{1}$ and the other one at $Y_{2}$). Optimizing the
weighted sum-rate over this setup narrows down to determining the rate of each
code layer, and deciding the order of successive decoding at each of the two
receivers. Note that here we are dealing with two sets of constraints, each of
the form in 19. Solving the two sets of constraints of the form in 19 results
in a subset of the corresponding constraints to be satisfied with equality
(active constraints). Active constraints can be solved as a set of equations
to determine the rates of each infinitesimal code-book. Successive decoding of
infinitesimal code-books at $Y_{1}$ and $Y_{2}$ proceeds from top to bottom.
infinitesimal code-books constructing public messages are decoded first. Then
comes the private code-book of user 1 at $Y_{1}$ and the private code-book of
user 2 at $Y_{2}$. The key point is that, the optimization of power
allocation, which is determining the number of layers in public and private
messages, will be such that after decoding of infinitesimal public code-books,
infinitesimal private code-books of user 1 are decoded at $Y_{1}$ and
infinitesimal private code-books of user 2 are decoded at $Y_{2}$. For each
infinitesimal private code-book at $Y_{1}$, there is a corresponding copy at
$Y_{2}$ (called dummy private message of user 1) which is placed after all
infinitesimal private code-books of user 2 . Likewise, for each infinitesimal
private code-book at $Y_{2}$, there is a corresponding copy at $Y_{1}$ (called
dummy private message of user 2) which is placed after all infinitesimal
private code-books of user 1. This ordering is a consequence of optimization
problem, and can be explained relying on Theorem 9.

Consider a pair of infinitesimal code-books $\Omega_{1}$ and $\Omega_{2}$,
formed at $Y_{1}$ and $Y_{2}$, respectively. Let us assume rate of
$\Omega_{1}$, denoted as $\delta r_{1}$ contributes to the weighted sum-rate.
Using Gaussian random code-books minimizes the amount of power in $\Omega_{1}$
for the given rate $\delta r_{1}$. On the other hand, $\Omega_{2}$ is formed
by the same probability density function after being subject to a scale factor
corresponding to relevant channel cross gain. As a result, minimizing the
power of $\Omega_{1}$ will also minimize the power of $\Omega_{2}$. Assuming
$\Omega_{1}$ is part of the private message of user 1, then $\Omega_{2}$ will
act as interference at $Y_{2}$. Note that the total power received at $Y_{1}$
is fixed at $P_{1}+aP_{2}$ and total power received at $Y_{2}$ is fixed at
$bP_{1}+P_{2}$, as required in Theorem 2. By minimizing power allocated to
private message of user 1, the power of interference observed by user 2 is
minimized, but at the cost of having a Gaussian density for the interference
term. Noting Theorem 2, the overall trade-off will be in favor of relying on
Gaussian density for all infinitesimal code-books forming the private messages
of users 1 and 2.

Following theorem summarizes the above arguments.

######  Theorem 3.

Construction of code-books relying on infinitesimal Gaussian layers optimizes
the weighted sum-rate in 2-users GIC.

###### Proof.

Let us focus on user 1. Optimality of Gaussian random codes for infinitesimal
code-books is due to the fact that, at $Y_{1}$, the set of public layers and
private layers of user 1 are equivalent to a superposition code with
successive decoding subject to AWGN plus interference from dummy private
messages of user 2. For each infinitesimal code-book in the private message of
user 1, say code-book $\Omega$, there is a counterpart copy, say
$\breve{\Omega}$, with the same probability density at $Y_{2}$ (with some
scaling due to relevant channel cross gain). The rate that could be embedded
in $\breve{\Omega}$ is less than the rate of $\Omega$, simply because rate of
$\breve{\Omega}$ does not count in the weighted sum-rate. The optimization
governing rates of infinitesimal code-books could set the rate of the
corresponding layer at the smaller value corresponding to $\breve{\Omega}$,
which would result in the code-book to be decoded at both $Y_{1}$ and $Y_{2}$,
or set the rate at the higher value corresponding to ${\Omega}$, which would
entail the code-book can be decoded only at $Y_{1}$. The option of decoding
the infinitesimal code-book at both $Y_{1}$ and $Y_{2}$ would entail it is
indeed part of a public message. This cannot be the case since the
optimization problem has determined a fixed (optimum) number of layers to be
part of public messages. This is indeed a statement of nested optimality
condition. Regardless of how the rate of each infinitesimal code-book is
decided, the optimum random code for the construction of all infinitesimal
code-books at $Y_{1}$ as well as at $Y_{2}$ (when considered independently) is
based on using independent Gaussian density of power $\delta$ for all code-
books ($\delta$ is the power at the transmit side, it will be subject to
channel gain before reaching the receiver side). Since the use of Gaussian
code-books for all layers satisfy the consistency requirement (in terms of
having the same density for counterpart copies of the same infinitesimal code-
books), then Gaussian density will be also optimum when the constraints at
$Y_{1}$ and $Y_{2}$ are considered together. Note that consistency requirement
on random code-books is equivalent to what is expressed in 31 to 34 for the
case of four code-books. Indeed, the four code-books in 22 to 34 are obtained
by combining consecutive infinitesimal Gaussian code-books that could form a
continuous layer (see [1] for definition).

To shed some lights, let us present the proof in a different language. Let us
consider an upper bound on the solution in which the random coding density
function for the two code-books forming a pair can be selected independent of
each other. Consider an ordering of layers at $Y_{1}$ and an independent
ordering of layers at $Y_{2}$. Consider a strategy in which the random coding
density for each layer is selected (independent of its pair) to maximize its
rate given its position in successive decoding. Let us consider a pair of
layers achieving rates $\breve{r}_{1}$ and $\breve{r}_{2}$ at $Y_{1}$ and
$Y_{2}$, respectively. Once the rates of layers are independently optimized
(using independent Gaussian code-books of power $\delta$ for all layers) a
second algorithm decides for a single rate for the two code-books forming a
pair, i.e., for the pair of rates $\breve{r}_{1}$ and $\breve{r}_{2}$, the
final rate will be selected as $[\breve{r}_{1}\leavevmode\nobreak\
\mbox{or}\leavevmode\nobreak\ \breve{r}_{2}]$ depending on the contribution of
the code-book to weighted sum-rate. As a result, for some of the pairs
(forming private messages) only one of the two code-books will be decodable.
However, for all pairs, at least one of the two code-books, called non-
redundant component of the pair (vs. redundant component), will be decoded and
its rate directly appears in the weight sum-rate. Using Gaussian random code-
book is necessary to maximize the rate of the non-redundant component, and as
a side-effect, it also maximizes the rate of redundant component. The
consistency condition is automatically satisfied since the optimum density
function for all layers, regardless of their position in successive decoding,
is a Gaussian of power $\delta$ at the transmit side (subject to scaling by
channel gains). This also means the upper bound coincides with the actual
solution.

In summary, since each infinitesimal code-book is decoded in at least one of
the two receivers, the random coding density for the pair should be the
optimum one, which is a Gaussian of power $\delta$. This is possible since a
Gaussian of power $\delta$ for all layers automatically satisfies the
consistency requirement, i.e., having the same random coding density for the
two code-books forming a pair. ∎

###  1.4 Formation of Multiple-access Channels with Four Inputs

Consider the 2-users GIC model in 3 for the case that both users have both
private and public messages. Let us assume public and private messages of each
user are independent (to be justified later). With independent $U_{1}$,
$V_{1}$, $U_{2}$ and $V_{2}$, a multiple-access channel,
$\overline{M\\!AC_{1}}$ with four inputs is formed at $Y_{1}$, and a multiple-
access channel, $\overline{M\\!AC_{2}}$ with four inputs is formed at $Y_{2}$.
Let us define the corresponding optimization problem $\mathcal{P}_{0}$ as
follows

Maximize: $\displaystyle L_{0}=R_{U_{1}}+R_{V_{1}}+\mu(R_{U_{2}}+R_{V_{2}})$
(22) Subject to:
$\displaystyle\left(R_{U_{1}},R_{V_{1}},R_{U_{2}},R^{(1)}_{V_{2}}\right)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\in\leavevmode\nobreak\ \leavevmode\nobreak\
\overline{M\\!AC_{1}}\left(P^{(1)}_{U_{1}},P^{(1)}_{V_{1}},P^{(1)}_{U_{2}},P^{(1)}_{V_{2}}\right)$
(23) $\displaystyle\left(R_{U_{1}},R^{(2)}_{V_{1}},R_{U_{2}},R_{V_{2}}\right)$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\in\leavevmode\nobreak\ \leavevmode\nobreak\
\overline{M\\!AC_{2}}\left(P^{(2)}_{U_{1}},P^{(2)}_{V_{1}},P^{(2)}_{U_{2}},P^{(2)}_{V_{2}}\right)$
(24) where: $\displaystyle P^{(1)}_{U_{1}}=P^{(2)}_{U_{1}}/b$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ P_{U_{1}}$ (25)
$\displaystyle P^{(2)}_{U_{2}}=P^{(1)}_{U_{2}}/a$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ P_{U_{2}}$ (26)
$\displaystyle P^{(1)}_{V_{1}}=P^{(2)}_{V_{1}}/b$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ P_{V_{1}}$ (27)
$\displaystyle P^{(2)}_{V_{2}}=P^{(1)}_{V_{2}}/a$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ P_{V_{2}}$ (28)
$\displaystyle P_{U_{1}}+P_{V_{1}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ =\leavevmode\nobreak\ \leavevmode\nobreak\ P_{1}$ (29)
$\displaystyle P_{U_{2}}+P_{V_{2}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ =\leavevmode\nobreak\ \leavevmode\nobreak\ P_{2}$ (30)
$\displaystyle f^{(1)}_{U_{1}}=f^{(2)}_{U_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ f_{U_{1}}$ (31)
$\displaystyle f^{(1)}_{U_{2}}=f^{(2)}_{U_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ f_{U_{2}}$ (32)
$\displaystyle f^{(2)}_{V_{1}}\circeq f^{(1)}_{V_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ f_{V_{1}}$ (33)
$\displaystyle f^{(1)}_{V_{2}}\circeq f^{(2)}_{V_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
\triangleq\leavevmode\nobreak\ \leavevmode\nobreak\ f_{V_{2}}$ (34)

where $\triangleq$ means "denoted as", and $\circeq$ means the density
functions will be the same once random variables are normalized by dividing
with their respective standard deviations. In 23 and 24, MAC regions are
expressed as a function of the power budget for their respective message set
to emphasize the role of power allocation. Solution to 22 to 34 should satisfy
some consistency requirement, in the sense that power vectors related to
$\overline{M\\!AC_{1}}$ and $\overline{M\\!AC_{2}}$ are linked to each other
through 25 to 28, while satisfying 29 and 30, and random coding density
functions should be consistent in view of 31 to 34.

Note that

$\displaystyle R^{(1)}_{V_{2}}$
$\displaystyle=I(\sqrt{a}V_{2};Y_{1}|U_{1},U_{2},V_{1})$ (35) $\displaystyle
R^{(2)}_{V_{1}}$ $\displaystyle=I(\sqrt{b}V_{1};Y_{2}|U_{1},U_{2},V_{2}).$
(36)

are simply mathematical expressions that could be used to form the expressions
governing successive decoding.

Dummy Private Messages: Let us use refer to messages resulting in rates
$R^{(1)}_{V_{2}}$ and $R^{(2)}_{V_{1}}$ in solving $\mathcal{P}_{0}$ as
dummy222Called dummy since these are merely an expression in terms of power.
private messages. Dummy private messages capture the role of interference in
2-users GIC, and relates its solution to the solution of problem
$\mathcal{P}_{0}$. Messages realizing $R_{V_{1}}$ and $R_{V_{2}}$ are called
non-redundant private messages.

To further clarify the roles of dummy private messages and thereby the
relationships between 2-users GIC and $\overline{M\\!AC_{1}}$,
$\overline{M\\!AC_{2}}$, let us consider the optimum solution to 2-users GIC,
and focus on interference terms at $Y_{1}$ and $Y_{2}$. These are random code-
books that have been already labeled/selected indirectly through private
messages. However, consider a hypothetical case in which one could provide an
independent set of labels for elements of these code-books up a rate that
would be decodable at their respective receiver. This would result in 4 rate
values at each receiver. These 4-tuple rate values cannot fall outside
$\overline{M\\!AC_{1}}$ (at $Y_{1}$) or outside $\overline{M\\!AC_{2}}$ (at
$Y_{2}$).

Note that, in dealing with $\overline{M\\!AC_{1}}$ and
$\overline{M\\!AC_{2}}$, rates of dummy private messages are simply an
expression in terms of relevant power values. In 2-users GIC, the actual code-
book/rate of the dummy private message of user 1 is the same as the code-
book/rate for the non-redundant private message of user 2 and vice versa. As
we will see, formulation (handling non-redundant rates) for 2-users GIC is
obtained by projecting $\overline{M\\!AC_{1}}$ and $\overline{M\\!AC_{2}}$
along the orthogonal span of the rate of their relevant dummy private message.
This removes the role of the rate of dummy private messages in the formulation
relevant to 2-users GIC, i.e., solely accounts for their impacts in terms of
an interference term from a lower level code-book in successive decoding of
non-redundant messages. Consequently, dummy private messages (interference
terms) do not need to be decodable in 2-users GIC. $\blacksquare$

Dominant Multiple-Access Region: The optimum solution maximizing $L_{0}$ in
22, either falls on the sum-rate front of $\overline{M\\!AC_{1}}$, which is
equal to

$0.5\log_{2}\left(1+(P1+aP_{2})/\sigma^{2}\right),$ (37)

and on the boundary of $\overline{M\\!AC_{2}}$, or on the sum-rate front of
$\overline{M\\!AC_{2}}$, which is equal to

$0.5\log_{2}\left(1+(bP1+P_{2})/\sigma^{2}\right),$ (38)

and on the boundary of $\overline{M\\!AC_{1}}$. The MAC with the optimizing
sum-rate front is called the dominant MAC. Note that sum-rates in 37 and 38
include rates of dummy private messages. $\blacksquare$

Nested Optimality of Private Messages: Nested optimality condition states
that, in solving 22 to 34 for a given $\mu$, the power of private messages
will be at a saturation level which depends on $\mu$. This means, beyond the
point of saturation, increasing the power of public message(s) will result in
a higher return in terms of the weighted sum-rate.

In other words, if power values allocated to private messages are equal to
$\hat{P}_{1}(\mu)$ and $\hat{P}_{2}(\mu)$, solving 22 to 34 for
$P_{1}=\hat{P}_{1}(\mu)$, $P_{2}=\hat{P}_{2}(\mu)$ results in zero power to be
allocated to public messages. Likewise, solving 22 to 34 for
$P_{1}=\hat{P}_{1}(\mu)$ allocates zero power to the public message of user 1,
and solving 22 to 34 for $P_{2}=\hat{P}_{2}(\mu)$ allocates zero power to the
public message of user 2.

As indicated, saturation levels for private messages depend on $\mu$. All
discussions presented hereafter in conjunction with saturation levels concern
the same value of $\mu$ determining the relevant saturation levels. One
conclusion is that, in solving 22 to 34, public messages are formed above
private messages and should be decoded first while considering private
messages as noise. Later parts show that the dummy private messages are placed
first. Following discussions are based on such a configuration.

Let us consider the multiple-access region formed over redundant message of
user 2 and non-redundant message of user 1 at $Y_{1}$, called maC1, and the
multiple-access region formed over redundant message of user 1 and non-
redundant message of user 2 at $Y_{2}$, called maC2. The optimum solution to
22 to 34 maximizes $R_{V_{1}}$ over maC1, and $R_{V_{2}}$ over maC2. Noting
nested optimality, we can focus on the optimality of maC1 and maC2 assuming
$P_{1}=\hat{P}_{1}(\mu)$, $P_{2}=\hat{P}_{2}(\mu)$, i.e., set aside the roles
of public messages in optimizing maC1 and maC2. We have the following theorem.

######  Theorem 4.

Consider the optimum solution to maC1 and maC2 in conjunction with an AWGN
channel. The optimum solution maximizes $R_{V_{1}}$ over maC1 and $R_{V_{2}}$
over maC2. The dummy private messages should have the smallest rate in their
corresponding multiple-access region, and should be ranked first (decoded last
in successive decoding), with non-redundant private messages positioned next.
In addition, if, in the final solution, the rates of redundant and non-
redundant private messages, in maC1 and maC2 (which are functions of $a$, $b$,
$\mu$ only) are equal to $\breve{r}_{1}$, $\breve{r}_{2}$, $\hat{r}_{1}$ and
$\hat{r}_{2}$, respectively, then solving 22 to 34 subject to some of the
following constraints

$R_{V_{1}}\neq\hat{r}_{1}\leavevmode\nobreak\ \leavevmode\nobreak\
R_{V_{2}}\neq\hat{r}_{2}\leavevmode\nobreak\ \leavevmode\nobreak\
R^{(1)}_{V_{2}}\neq\breve{r}_{1}\leavevmode\nobreak\ \leavevmode\nobreak\
R^{(2)}_{V_{1}}\neq\breve{r}_{2}$

reduces the value of $L_{0}$ in the optimum solution.

###### Proof.

Noting that the weight of redundant (dummy) private messages is zero in
$L_{0}$ defined in 22, which is the smallest among different weights forming
$L_{0}$, it follows that the rates of each redundant private message should be
the minimum in its respective multiple-access region. Under this condition,
let us consider all possible decoding orders in maC1 and maC2. It follows that
the only possible decoding order which can satisfy nested optimality
condition, satisfy consistency condition in 25 to 34 while achieving a point
on the sum-rate front of both multiple-access regions, is the one that places
dummy private messages first (decoded last in successive decoding). Achieved
corner point in maC1 is based having the non-redundant message of user 1 above
the noise plus interference (caused by the dummy private message of user 2).
Likewise, achieved corner point in maC2 is based having the non-redundant
message of user 2 above the noise plus interference (caused by the dummy
private message of user 1). Both these corner points correspond to a
stationary solution in terms of power values in the sense that changing
(increasing or decreasing) the power of one of the private messages results in
a reduction in the rate of the other private message. ∎

In summary, in the optimum solution, the rates of redundant and non-redundant
private messages in maC1 and maC2 are fixed (function of $\mu$ and gain values
$a$ and $b$). Optimality in this case translates to achieving the designated
rates with minimum power, while maintaining consistency in the sense of 25 to
34. $\blacksquare$

The following Theorem, although not directly related to 2-users GIC, sheds
some light on the reason for relying on Gaussian random code-books.

######  Theorem 5.

Consider a two-level superposition code with AWGN. The rates of code-books
should be equal to $\tilde{r}_{1}$ and $\tilde{r}_{2}$. The optimum solution
achieving the minimum power vector relies on Gaussian code-books for both
layers.

###### Proof.

A two-layer Gaussian code-book result in minimizing the total power for a sum-
rate of $\tilde{r}_{1}+\tilde{r}_{2}$. The power associated to the first code-
book is minimum due to forming a Gaussian code-book subject to noise only. On
the other hand, the sum of power values is determined by the sum-rate and is
minimized using a Gaussian code-book of total power $\breve{P}$ satisfying
$\tilde{r}_{1}+\tilde{r}_{2}=0.5\log_{2}(1+\breve{P})$. Noting the sum-power
is minimized and the power of first layer is minimized as well, it follows
that the power of second layer is minimized too. This problem has two
solutions, depending on the order of code-books realizing rate $\tilde{r}_{1}$
and $\tilde{r}_{2}$. ∎

######  Theorem 6.

Consider maC1 and maC2 with AWGN. The rates of code-books forming maC1 as well
as maC2 are fixed (function of $\mu$ and channel gain values $a$ and $b$). The
optimum solution minimizing power for the designated rates rely on Gaussian
code-books where the code-books corresponding to dummy private messages are
ranked first.

###### Proof.

According to Theorem 4, dummy private messages are placed first at both
$Y_{1}$ and $Y_{2}$. Regardless of the random coding density function, rate of
these first layers (dummy private messages) will be an increasing function of
their respective power levels. Saturation, which is the cause of nested
optimality, occurs at a point that further increase in the power of one or
both of private message(s) result(s) in a lower increase in the weighted sum-
rate as compared to allocating any extra power, in one or both transmitter(s),
to the respective public message(s). This means, saturation happens when the
rate of one or both dummy private message(s) has/have reached to a respective
threshold which is a function of $\mu$ and channel gain values $a$ and $b$.
Let us refer to these saturation rates as $\breve{r}_{1}$ and $\breve{r}_{2}$,
respectively. Noting the total power at $Y_{1}$ and $Y_{2}$ are equal to
$\hat{P}_{1}(\mu)+a\hat{P}_{2}(\mu)$ and $\hat{P}_{2}(\mu)+b\hat{P}_{1}(\mu)$,
respectively, the problem reduces to maximizing the rate of each non-redundant
private message subject to the condition that the rate of its counterpart
dummy private message is fixed. This situation corresponds to the conditions
of Theorem 2 at $Y_{1}$ and $Y_{2}$, which states the optimum code-books will
be independent Gaussian.

The proof for Theorem 6 could also follow from Theorem 5. Note that in maC1
and maC2, minimizing the power of each dummy private message is equivalent to
minimizing the power of its associated non-redundant private message since the
power values are linked to each other through 27 and 28. ∎

In Theorem 6, rate of dummy private messages are considered as bottlenecks
governing the saturation conditions. A question may arise why the bottleneck
is not directly related to the rates of non-redundant private messages. To
explain the reason, let us consider adding an extra $\delta$-layer of power
(see [1] or Section 1.3 of the current report for definition) beyond the point
of saturation. Without loss of generality, let us focus on user 1. As shown in
Fig. 2, the added $\delta$-layer becomes part of superposition code structure
forming the non-redundant private message of user 1. The only distinction is
that the rate of this added $\delta$-layer, unlike layers before it, is
determined such that the layer can be decoded at both $Y_{1}$ and $Y_{2}$,
i.e., it becomes part of the public message of user 1. However, in the
formation of dummy private message of user 1 at $Y_{2}$, the added
$\delta$-layer leaves the continuum of superimposed $\delta$-layers forming
the dummy private message of user 1, and will be placed above the non-
redundant private message of user 2. This entails the structure of dummy
private message of user 1 at $Y_{2}$ is locked at the saturation level and its
rate does not change beyond the point of saturation. According to Theorem 3 of
[1], the rate of the added $\delta$-layer is governed by the structure of
code-books at $Y_{2}$. As far as $Y_{1}$ is concerned, the rate of the added
layer follows the smooth (infinitesimal) decrease in rates of subsequent
$\delta$-layers stacked together to form the non-redundant private message of
user 1 at $Y_{1}$, while the rate of added $\delta$-layer at $Y_{2}$
experiences a much larger decrease with respect to its previous layer placed
on top of the redundant message of user 1 at $Y_{2}$. This is in accordance
with the rate of non-redundant private message of user 1 to remain locked at
$\breve{r}_{1}$ beyond the point of saturation.

Figure 2: Conditions governing nested optimality of private messages, and
addition of a $\delta$-layer beyond point of saturation.

In summary, nested optimality entails the optimum values for rates of
redundant and non-redundant private messages, forming maC1 and maC2, should be
realized with minimum power using Gaussian random code-books for private
messages.

######  Theorem 7.

Random coding density functions for public messages should be Gaussian.

###### Proof.

The proof follows noting public code-books see a Gaussian noise at both
$Y_{1}$ and $Y_{2}$. Public messages form a multiple-access channel, called
Mac1, at $Y_{1}$ and a multiple-access channel, called Mac2, at $Y_{2}$.
Gaussian random code-books are optimum in both cases. Indeed, public code-book
at $Y_{1}$ can be viewed as a Gaussian layer (on top of private code-book of
user 1) in a superposition code encoding message of user 1. Likewise, public
code-book at $Y_{2}$ can be viewed as a Gaussian layer (on top of private
code-book of user 2) in a superposition code encoding message of user 2.
However, rates of public layers are adjusted to be decodable at both
receivers. This is needed to provide a space of shared rate values between
$Y_{1}$ and $Y_{2}$ to be able to satisfy conditions over both
$\overline{M\\!AC_{1}}$ and $\overline{M\\!AC_{2}}$ in 22 to 34. ∎

Example 1: Consider the problem of designing a two-levels superposition code
over an AWGN channel subject to an available power of $\breve{P}$. The
objective is to maximize the rate of one of the layers, subject to having a
rate of $r_{1}$ for the other layer. There are two solutions for this problem
resulting in the same value of $S-r_{1}$ for the objective function: (i) layer
of rate $r_{1}$ is first, and a layer of rate $S-r_{1}$ is second, where
$S=0.5\log_{2}(1+P/\sigma^{2})$ is the achievable sum-rate. (ii) layer of rate
$S-r_{1}$ is first, and layer of rate $r_{1}$ is second.

In both solutions, the random coding density functions for the two layers are
independent Gaussian. Either of these solutions may appear counter intuitive.
In solution (i), a Gaussian code-book (that does not count in the objective
function) is used in the first layer, creating the worst noise (Gaussian) for
the second code-book above it, while this second code-book is the one that
determines the value of objective function. In solution (ii), second code-book
is selected to be Gaussian. This maximizes the rate of the second code-book,
while this rate does not count in the objective function. To explain these
contradictions, in both cases, Gaussian code-books play the important role of
minimizing the power required for achieving their respective rates and thereby
leave a higher (maximum) amount of power for the other code-book. It is a
property of multiple access channel that saving in power due to using a
Gaussian code-book is advantageous in comparison to the harm caused by
creating the worst (Gaussian) interference. More generally, in optimizing a
weighted sum-rate over a multiple-access channel (or multi-level coding in a
point-to-point setup), all layers, regardless of their weights (even if their
respective weight is zero) should rely on Gaussian random code-book. Of
course, if the power constraints permit, zero power will be allocated to code-
books that do not count (have zero weight) in the objective function. However,
in some cases, including the problem arising from 2-users GIC, power values
cannot be set to zero. In particular, the power of each dummy private messages
is linked to the power of its relevant non-redundant private message through
27 and 28. In this case, power values allocated to dummy private messages are
minimized subject to problem constraints in 22 to 34. As expressions in 19 are
in terms of rates, the rates of dummy private messages is what contributes to
the formation of the optimum solution. To further reduce the power of dummy
private messages for a given rate, these are placed first which results in
highest return in rate vs. allocated power.

Returning to our example, consider solution (ii) and assume in the final
solution, one assigns a rate $\breve{r}>r_{1}$ to the first layer without
changing the power allocation. Obviously, the first layer cannot be decoded
any longer. However, the second layer above it can still achieve its assigned
rate of $S-r_{1}$ simply because it sees the first layer merely as
interference (rate of the first layer does not come to the picture) and as
long as the power does not change, the decoding can proceed. This is analogous
what happens in 2-users GIC. We start by including dummy rate values which
have a zero weight in the weighted sum-rate, and then conclude to decode the
code-books which do count in the weighted sum-rate, decoding of these dummy
messages is not needed. More importantly, regardless of which code-books count
in the weighted sum-rate and which code-books have zero weight, random coding
density for all code-books should be independent Gaussian.$\blacksquare$.

##  2 Optimum Solution to 2-users GIC

Consider a 2-users GIC and rely on the concept of dummy private messages,
which entails interfering terms can be independently encoded/decoded (subject
to power constraints in 25 to 30). The weighted sum-rate achievable in such a
relaxed 2-users GIC cannot be worse that the weighted sum-rate achievable in
the original 2-users GIC. On the other hand, the rate-tuple achieved at each
receiver in the relaxed 2-users GIC cannot be better than what can be achieved
in a multiple-access channel which is optimally enlarged (using single letter,
independent Gaussian code-books forming a superposition code at each
transmitter). This means solution to 22 to 34 provides an upper bound on the
solution to 2-users GIC. To explain this point differently, let us consider
the optimum solution to 2-users GIC. Interference terms at each receiver can
be assigned a rate value that renders them decodbale when messages above
interference terms are decoded and removed. Including this dummy rates for
interference terms result in a 4-tuple rate vector at $Y_{1}$ and another
4-tuple rate vector at $Y_{2}$ that cannot fall outside
$\overline{M\\!AC}_{1}$ and $\overline{M\\!AC}_{2}$, respectively.

Once dummy private messages are ranked first, if they are decodable or not,
does not affect the rate-tuple achievable by code-books above them. The
impacts of dummy private messages on code-books above them merely depend on
their respective power. This property permits the rate-tuple achieved in
2-users GIC (over non-redundant messages, without decoding dummy private
messages) to be the same as the rate-tuple achieved in the lower bound
corresponding to HK rate region, and the upper bound based on the intersection
of $\overline{M\\!AC}_{1}$ and $\overline{M\\!AC}_{2}$ in 22 to 34. Noting
properties of multiple-access channel, any weighted sum-rate is optimized
using single letter, independent Gaussian code-books forming a superposition
code at each transmitter.

Overall orderings of messages are as follows:

$\small\overline{M\\!AC}_{1}:\mbox{(1) Dummy Private Message of User 2, (2)
Private Message of User 1, (3,4) Public Messages}$ (39)
$\small\overline{M\\!AC}_{2}:\mbox{(1) Dummy Private Message of User 1, (2)
Private Message of User 2, (3,4) Public Messages}$ (40)

Using this ordering, the rate-tuple of non-redundant messages in the optimum
solution to 22 to 34 (with or without decoding of dummy private messages) is
the same as the rate-tuple achieved in HK optimization problem defined in 41
to 57 (without decoding the dummy private messages), as well as the rate tuple
achieved in 2-users GIC (without decoding the dummy private messages).

##  3 A Closer Look at the Optimum Solution

This section helps in understating arguments discussed in earlier parts, and
paves the way to understanding the structure of the final solution. As will be
discussed later, the formation of optimum solution to 2-users GIC involves
three corner points in $\overline{M\\!AC_{1}}$ and $\overline{M\\!AC_{2}}$,
two on the dominant MAC involved in time-sharing and one on non-dominant MAC.
Theorem 8 below clarifies that in a nested formation of Multiple-Access
Polymatroids (MAPs), a corner point on a parent MAP corresponds to a corner
point in each of its children.

######  Theorem 8.

Consider a Multiple-Access Polymatroid (MAP) composed of $M$ messages ordered
from bottom to top indexed by $1,2,\ldots,M$. Consider integer $1\leq\ell\leq
M$. Two MAPs are identified, one including messages $\ell+1,\ldots,M$ by
considering interference from $1,\ldots,\ell$ as noise, and the other one
composed of messages $1,\ldots,\ell$ when messages $\ell+1,\ldots,M$ are
decoded and removed. The former is denoted as Map and the latter as maP. We
have: (i) In the sense of iff, a corner point (on the sum-rate front) of MAP
corresponds to a corner point in Map and a corner point in maP. (ii) Map is
equal to the projection of MAP on the orthogonal span of rate tuple
corresponding to maP, i.e., Map is lifted to MAP by including the missing
rate-tuples from maP.

###### Proof.

Proof follows noting that expressions for Map are a subset of expressions
defining MAP. Direct replacement shows that region Map is mapped to a corner
region in MAP by including missing rate components by rate-tuples from maP. ∎

Theorem 9 below is a different way of expressing the fact that public messages
are formed above private messages. In the language of nested optimality,
public messages are formed when private messages have reached their saturation
level (which depends on the value of $\mu$, and channel gains, i.e., $a$ and
$b$).

######  Theorem 9.

Consider a 2-users GIC (see Fig. 3) realizing a rate-tuple
$(R_{U_{1}},R_{U_{2}},R_{V_{1}},R_{V_{2}})$. In realizing
$(R_{U_{1}},R_{U_{2}},R_{V_{1}})$ at $Y_{1}$, $V_{2}$ is considered as noise,
and likewise, in realizing $(R_{U_{1}},R_{U_{2}},R_{V_{2}})$ at $Y_{2}$,
$V_{1}$ is considered as noise.

###### Proof.

Without loss of generality, let us focus on $Y_{1}$, and let us assume part of
message $V_{2}$, denoted as $\hat{V}_{2}$, is decoded at $Y_{1}$. Noting that
$V_{2}$ is entirely decoded at $Y_{2}$, it turns out that $\hat{V}_{2}$ is
decoded at both $Y_{1}$ and $Y_{2}$, and consequently, it will be a public
message. By moving $\hat{V}_{2}$ from private to public (and accordingly
readjusting power allocation), the private message of user 2 reduces until it
entirely acts as noise in $Y_{1}$. ∎

Another question concerns the reason for having a private message and a public
message for each user in 2-users GIC, which has motivated the formulation in
22 to 34. Having superposition coding at $X_{1}$ and $X_{2}$, equipped with
power allocation between layers, does not contradict optimality. Rates of
public and private messages are adjusted to enable simultaneously satisfying
conditions associated with multiple-access reception at $Y_{1}$ and $Y_{2}$
(also see [1]).

###  3.1 Position of Optimum Solution on the Sum-rate Front of Dominant MAC

It is also known that formulation in 41 to 57, corresponding to HK rate
region, results in an achievable solution (lower bound) to 2-users GIC. Upon
projecting $\overline{M\\!AC_{1}}$ and $\overline{M\\!AC_{2}}$ along the
orthogonal span of their respective dummy private message, one obtains MAC1
(defined in HK constraints 42 to 48) and MAC2 (defined in HK constraints 49 to
55). The optimum solution to 41 to 57 falls on the sum-rate of MAC1 and/or on
the sum-rate front of MAC2. Otherwise, the solution would be within both
regions, MAC1 and MAC2, and could be improved by increasing some of its (non-
redundant) rate values. Let us assume the optimum solution falls on the sum-
rate front of MAC1, called dominant. It is easy to see that the solution
corresponds to a corner point in MAC2 (called non-dominant) once one of its
corresponding public rates is reduced to bring the solution to a point on the
sum-rate front of MAC1. Any point on the sum-rate front of MAC1 can be
realized by time-sharing between two corner points, called time-sharing corner
points hereafter. The optimum solution, falling on the sum-rate front of MAC1
(dominant) by interpolation between time-sharing corner points, is lifted to a
point on the sum-rate front of $\overline{M\\!AC_{1}}$ by including the rate
of the dummy private message of user 2. Likewise, the solution on the boundary
of MAC2 (non-dominant) is lifted to a point on the boundary of
$\overline{M\\!AC_{2}}$. This boundary point is obtained by reducing the rate
of a public message with respect to a corner point of $\overline{M\\!AC_{2}}$.

Rates of public messages are the only rate values that are shared between
$\overline{M\\!AC_{1}}$/MAC1/Mac1 and $\overline{M\\!AC_{2}}$/MAC2/Mac2. As a
result, satisfying both constraints (in 23 and 24) requires adjusting the
rates of public messages, including: (i) time-sharing between two corner
points in the dominant multiple-access region defined over public messages,
and reducing the rate of one of public messages in non-dominant multiple-
access region defined over public messages such that the final solution falls
on the sum-rate front of the dominant multiple-access region. Noting Theorem
8, a corner point in $\overline{M\\!AC_{1}}$ corresponds to a corner point in
MAC1 (region of non-redundant messages at $Y_{1}$), a corner point in Mac1
(region of public messages at $Y_{1}$), and a corner point in maC1 (region of
private messages at $Y_{1}$). Likewise, a corner point in
$\overline{M\\!AC_{2}}$ corresponds to a corner point in MAC2 (region of non-
redundant messages at $Y_{2}$), a corner point in Mac2 (region of public
messages at $Y_{2}$), and a corner point in maC2 (region of private messages
at $Y_{2}$). As we will be discussed in Section 3, at most three corner points
will contribute to the final solution, two on the dominant MAC which will be
involved in time-sharing and one on the non-dominant MAC. The optimum solution
always falls on corner points of maC1 and maC2, but, assuming
$\overline{M\\!AC_{1}}$ is dominant, it falls on the sum-rate front of
$\overline{M\\!AC_{1}}$/MAC1/Mac1. Note that region of public messages is the
only region shared between $\overline{M\\!AC_{1}}$ and
$\overline{M\\!AC_{2}}$, and time-sharing over it enables realizing a point
that satisfies both constraints (related to $\overline{M\\!AC_{1}}$ and
$\overline{M\\!AC_{2}}$), while being optimized through power allocation.

###  3.2 Lack of Ability to Decoded Interference Terms - Impact on Optimizing
Non-redundant Rate Values

In the case of 2-users GIC, the code-books forming interference terms are the
same as the code-books forming non-redundant private messages. These changes
in code-books/rates with respect to dummy messages in $\mathcal{P}_{0}$ do not
affect the solution in maximizing the weighted sum-rate in 2-users GIC. Note
that in successive decoding, the code-books corresponding to non-redundant
messages are above the interference terms, and consequently, see the
interference as additional noise. The important point is that the power of
interference terms are minimized, providing the means to maximize the weighted
sum-rate over non-redundant messages. This point establishes the link between
the optimum solution to 2-users GIC and the optimum solution to problem
$\mathcal{P}_{0}$ in 22 to 34.

The final conclusion is that, in the optimum solutions explained above, the
lower bound (HK rate region in 41 to 57) and the upper bound (problem
$\mathcal{P}_{0}$ defined in 22 to 34) coincide in the space spanned by non-
redundant rate values, concluding that both result in the optimum solution to
2-users GIC.

##  4 Relationship to HK Rate Region

To derive the HK constraints using notations widely used in the literature,
one should refer to expressions 3.2 to 3.15 on page 51 of [5], and apply the
following changes, ($\mbox{current\leavevmode\nobreak\
article}\leftrightarrow$ [5]): $U_{1}\leftrightarrow W_{1}$,
$U_{2}\leftrightarrow W_{2}$, $V_{1}\leftrightarrow U_{1}$,
$V_{2}\leftrightarrow U_{2}$, $R_{U_{1}}\leftrightarrow T_{1}$,
$R_{U_{2}}\leftrightarrow T_{2}$, $R_{V_{1}}\leftrightarrow S_{1}$,
$R_{V_{2}}\leftrightarrow S_{2}$. Applying these changes, the expanded Han-
Kobayashi constraints and the associated optimization problem are expressed as
follows

Maximize: $\displaystyle R_{ws}=R_{1}+\mu
R_{2}=R_{U_{1}}+R_{V_{1}}+\mu(R_{U_{2}}+R_{V_{2}})$ (41) Subject to:
$\displaystyle R_{U_{1}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1};Y_{1}|U_{2},V_{1})$ (42) $\displaystyle R_{U_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{2};Y_{1}|U_{1},V_{1})$
(43) $\displaystyle R_{V_{1}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(V_{1};Y_{1}|U_{1},U_{2})$ (44) $\displaystyle R_{U_{1}}+R_{U_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{1},U_{2};Y_{1}|V_{1})$
(45) $\displaystyle R_{U_{1}}+R_{V_{1}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1},V_{1};Y_{1}|U_{2})$ (46) $\displaystyle R_{U_{2}}+R_{V_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{2},V_{1};Y_{1}|U_{1})$
(47) $\displaystyle R_{U_{1}}+R_{U_{2}}+R_{V_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{1},U_{2},V_{1};Y_{1})$
(48) $\displaystyle-------$ $\displaystyle---------$ $\displaystyle R_{U_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{1};Y_{2}|U_{2},V_{2})$
(49) $\displaystyle R_{U_{2}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{2};Y_{2}|U_{1},V_{2})$ (50) $\displaystyle R_{V_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(V_{2};Y_{2}|U_{1},U_{2})$
(51) $\displaystyle R_{U_{1}}+R_{U_{2}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1},U_{2};Y_{2}|V_{2})$ (52) $\displaystyle R_{U_{2}}+R_{V_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{2},V_{2};Y_{2}|U_{1})$
(53) $\displaystyle R_{U_{1}}+R_{V_{2}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1},V_{2};Y_{2}|U_{2})$ (54) $\displaystyle R_{U_{1}}+R_{U_{2}}+R_{V_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\ I(U_{1},U_{2},V_{2};Y_{2})$
(55) $\displaystyle E(U_{1}^{2})+E(V_{1}^{2})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ =\leavevmode\nobreak\
\leavevmode\nobreak\ P_{1}$ (56) $\displaystyle E(U_{2}^{2})+E(V_{2}^{2})$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ =\leavevmode\nobreak\
\leavevmode\nobreak\ P_{2}.$ (57)

To establish the connection between solution to problem $\mathcal{P}_{0}$ in
22 to 34 to HK optimization problem in 41 to 57, without loss of generality,
let us focus on constraints for $\overline{M\\!AC_{1}}$. It includes fifteen
constraints in terms of four rate values
$(R_{U_{1}},R_{V_{1}},R_{U_{2}},R^{(1)}_{V_{2}})$. A subset of constraints are
as follows

$\displaystyle R_{U_{1}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1};Y_{1}|U_{2},V_{1},V_{2})$ (58) $\displaystyle R_{U_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{2};Y_{1}|U_{1},V_{1},V_{2})$ (59) $\displaystyle R_{V_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(V_{1};Y_{1}|U_{1},U_{2},V_{2})$ (60) $\displaystyle R_{U_{1}}+R_{U_{2}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1},U_{2};Y_{1}|V_{1},V_{2})$ (61) $\displaystyle R_{U_{1}}+R_{V_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1},V_{1};Y_{1}|U_{2},V_{2})$ (62) $\displaystyle R_{U_{2}}+R_{V_{1}}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
{\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{2},V_{1};Y_{1}|U_{1},V_{2})$ (63) $\displaystyle
R_{U_{1}}+R_{U_{2}}+R_{V_{1}}$ $\displaystyle\leavevmode\nobreak\
\leavevmode\nobreak\ {\leq}\leavevmode\nobreak\ \leavevmode\nobreak\
I(U_{1},U_{2},V_{1};Y_{1}|V_{2}).$ (64)

Constraints 58 to 64 above, corresponding to constraints 42 to 48 in HK
constraints, define the multiple access region corresponding to treating the
dummy private message of user 1 as well as the non-redundant private messages
of user 2 as noise at $Y_{1}$. A similar set of equations can be obtained in
conjunction with $\overline{M\\!AC_{2}}$ coinciding with constraints 49 to 55
in HK constraints, forming the multiple access region corresponding to
treating the dummy private message of user 2 as well as the non-redundant
private messages of user 1 as noise at $Y_{2}$

Figure 3: Model for 2-users Gaussian Interference Channel (GIC).

###  4.1 Projection of a MAC Region on its Sub-spaces

Consider a memory-less multiple-access channel where the mutual information
terms on the right hand sides of corresponding constraints are some function
of a power vector $\mathbf{p}$. In the following, the ploymatroid
corresponding to capacity region of such a multiple access channel is simply
called MAP, sanding for Multiple-Access Polymatroid.

Let us consider a MAP with $M$ inputs, and focus on one of its rate values,
say $r_{1}\in[\min r_{1}\leavevmode\nobreak\ \mbox{to}\leavevmode\nobreak\
\max r_{1}]$. For a given power vector, $\mathbf{p}$, value of $r_{1}$ depends
on its order in successive decoding. $r_{1}$ is maximized when its
corresponding code-book is placed first (decoded last) in successive decoding,
and it is minimized when its corresponding code-book is placed last (decoded
first) in successive decoding. Setting $r_{1}=\max r_{1}$ results in a MAP,
$\mathsf{P}_{\max}$, defined over the space orthogonal to $r_{1}$, shifted up
to position of $\max r_{1}$ along the $r_{1}$ axis. The constraints for
$\mathsf{P}_{\max}$ are a subset of constraints defining the original MAP.
These constraints in the original MAP correspond to placing the $r_{1}$ code-
book first, decoding all code-books above the $r_{1}$ code-book, while
treating the interference from lower code-books (including $r_{1}$ code-book)
as noise. $r_{1}$ plays the role of dummy private message in
$\overline{M\\!AC_{1}}$ and $\overline{M\\!AC_{2}}$.

Likewise, setting $r_{1}=\min r_{1}$ results in a MAP, $\mathsf{P}_{\min}$,
defined over the space orthogonal to $r_{1}$, shifted up to position of $\min
r_{1}$ along the $r_{1}$ axis.

Depending on the order of code-book corresponding to $r_{1}$ in successive
decoding, one obtains $M$ cuts (cuts are orthogonal to $r_{1}$-axis) in the
original MAP region. The projections of these cuts on the sub-space orthogonal
to $r_{1}$ results in a nested set of regions bounded within an interior MAP
and an exterior MAP. Interior MAP corresponds to $\max r_{1}$ and exterior MAP
corresponds to $\min r_{1}$. Achieving capacity in a 2-users interference
channel, formed by a MAP at $Y_{1}$ and a MAP at $Y_{2}$, narrows down to
optimally enlarging the interior core formed when $r_{1}$ maximizes the
minimum rate in the original MAP. Figure 4 provides an example.

Figure 4: Example of nested projections of a three dimensional multiple access
region with rate-tuple $(r_{1},r_{2},r_{3})$ on the sub-space $(r_{2},r_{3})$.

## References

  * [1] Amir K. Khandani, “Capacity Region of Two-users Weak Gaussian Interference Channel", arXiv:2011.12981
  * [2] Amir K. Khandani “Optimality of Gaussian in Enlarging HK Rate Region, and its Overlap with the Capacity Region of 2-users GIC," arXiv:2012.07820
  * [3] D. N. C. Tse and S. V. Hanly, “Multiaccess fading channels. I. Polymatroid structure, optimal resource allocation and throughput capacities,” IEEE Transactions on Information Theory, vol. 44, no. 7, pp. 2796–2815, Nov. 1998 (also see D. Welsh, Matroid Theory, (1976), Academic Press, London)
  * [4] M. A. Maddah-Ali, A. Mobasher and A. K. Khandani, "Fairness in Multiuser Systems With Polymatroid Capacity Region," in IEEE Transactions on Information Theory, vol. 55, no. 5, pp. 2128-2138, May 2009
  * [5] T. S. Han and K. Kobayashi, “A new achievable rate region for the interference channel," in IEEE Transactions on Information Theory, vol. 27, no. 1, pp. 49-60, January 1981


Theorem <ref>.
Assuming that $\forall \pmbs{} \in \Gamma$, it holds that $| \hat f_\mcalU{} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] | \le \lambda$. It is guaranteed that $\forall \tau \in [L], \forall \pmb{s} \in \Lambda^\tau$:  i) if $f_\mcalU{} [ \pmb{s} ] \ge 3 \cdot \lambda$, then $\pmbs{} \in \mcalP{}_\tau$;  ii) if $f_\mcalU{} [ \pmb{s} ] < \lambda$, then $\pmbs{} \notin \mcalP{}_\tau$, consequently, $\mcalP{}_\tau \subseteq \Gamma_\tau$.

Suppose that $\forall \pmbs{} \in \Gamma = \cup_{0 \le \tau < L } \left( \Gamma{}_\tau \times \Lambda \right)$, we have that $\left| \hat f_\mcalU{} [ \pmbs{} ] - f_\mcalU{} [ \pmbs{} ] \right| \le \lambda$.
We prove the theorem by induction.

When $\tau = 1$, $\mcalP{}_{\tau - 1} = \Gamma_{\tau - 1} = \{ \bot \}$.
Then $\mcalP{}_0 \times \Lambda = \Gamma_0 \times \Lambda = \Lambda$.
For all $\pmbs{} \in \Lambda$, if $f_\mcalU{} [ \pmb{s} ] \ge 3 \cdot \lambda$, then it holds that

\hat f_\mcalU{} [ \pmbs{} ] \ge f_\mcalU{} [ \pmbs{} ] - \lambda \ge 2 \lambda\,.

According to the definition of $\mcalP{}_1$, the element $\pmbs{}$ belongs to $\mcalP{}_1$.
On the other hand, if $f_\mcalU{} [ \pmb{s} ] < \lambda$, then

\hat f_\mcalU{} [ \pmbs{} ] \le f_\mcalU{} [ \pmbs{} ] + \lambda < 2 \lambda\,.

It is guaranteed that $\pmbs{} \notin \mcalP{}_1$. Consequently, for all $\pmbs{} \in \mcalP{}_1$, we have $f_\mcalU{} [ \pmbs{} ] \ge \lambda$, which implies that $\mcalP{}_1 \subseteq \Gamma_1$.

Let $\tau > 1$ and assume that the claims holds for $\tau -1$.
For all $\pmbs{} \in \Lambda^\tau$, let $\pmbs{}[1 : \tau - 1] \in \Lambda^{\tau - 1}$ be the prefix of $\pmbs{}$ of length $\tau - 1$. If $f_\mcalU{} [ \pmb{s} ] \ge 3 \cdot \lambda$, then it holds that

f_\mcalU{} [ \pmbs{} [1: \tau - 1] ] \ge f_\mcalU{} [ \pmbs{} ] \ge 3 \lambda\,.

By the induction hypothesis, $\pmbs{} [1 : \tau - 1] \in \mcalP{}_{\tau - 1} \subseteq \Gamma_{\tau - 1}$.
$\pmbs{} \in \mcalP{}_{\tau - 1} \times \Lambda \subseteq \Gamma_{\tau - 1} \times \Lambda$, and

\hat f_\mcalU{} [ \pmbs{} ] \ge f_\mcalU{} [ \pmbs{} ] - \lambda \ge 2 \lambda\,.

According to the definition of $\mcalP{}_\tau$, the element $\pmbs{}$ belongs to $\mcalP{}_\tau$.

On the other hand, if $f_\mcalU{} [ \pmb{s} ] < \lambda$, there are two possible cases. First, if $\pmbs{} [ 1 : \tau - 1] \notin \mcalP{}_{\tau - 1}$, then by the definition of $\mcalP{}_\tau$, it is guaranteed that $\pmbs{} \notin \mcalP{}_\tau$. Second, if $\pmbs{} [ 1 : \tau - 1] \in \mcalP{}_{\tau - 1}$, by the inductive hypothesis that $\mcalP{}_{\tau - 1} \subset \Gamma_{\tau - 1}$, we have $\pmbs{} \subset \mcalP{}_{\tau - 1} \times \Lambda \subset \Gamma_{\tau - 1} \times \Lambda$.

\hat f_\mcalU{} [ \pmbs{} ] \le f_\mcalU{} [ \pmbs{} ] + \lambda < 2 \lambda\,.

It is guaranteed that $\pmbs{} \notin \mcalP{}_\tau$. Consequently, for all $\pmbs{} \in \mcalP{}_\tau$, we have $f_\mcalU{} [ \pmbs{} ] \ge \lambda$, which implies that $\mcalP{}_\tau \subseteq \Gamma_\tau$.