The K-User DM Broadcast Channel with Two Groupcast Messages: Achievable Rate Regions and the Combination Network as a Case Study
Mohamed Salman Mahesh K. Varanasi




The top quark charge asymmetry in tt̅γ production at the LHC
    Jonas Bergnere1,addr1
        Markus Schulzee2,addr1

    December 30, 2023
============================================================

empty
headings
arabic




A novel class of achievable rate regions is obtained for the general K-receiver discrete memoryless broadcast channel over which two groupcast messages are to be transmitted, with each message required by an arbitrary group of receivers.  
The associated achievability schemes are parameterized by an expansion of the message set which then determines how 
random coding techniques are employed. These techniques include generalized versions of up-set message-splitting, the generation of possibly multiple auxiliary codebooks for certain compositions of split messages using superposition coding with subset inclusion order, partial interference decoding at all receivers in general, joint unique decoding at receivers that desire both messages, and non-unique or indirect decoding at receivers that desire only one of the two messages.

The generality of the proposed class of schemes implies new achievable rate regions for problems previously not considered as well as those that were studied before, with specific members of that class having rate regions that coincide with previously found capacity regions for special classes of broadcast channels with two private or two nested groupcast messages, wherein the group of receivers desiring one message is contained in that desiring the other. Moreover, new capacity results are established for certain partially ordered classes of general broadcast channels for certain non-nested groupcast messages such as two messages each desired at K-1 receivers and two messages with one desired at K-1 receivers and the other message desired at some arbitrary subset of receivers including the receiver at which the first message is not desired. To further show the strength of the proposed class of achievable rate regions we consider the so-called combination network, a 
special class of linear deterministic broadcast channels, as a test case. When specialized to the combination network, some members of the class of inner bounds 
are shown, via converse results, to result in the capacity region for three different scenarios, namely, (a) the two messages are intended for two distinct sets of K-1 receivers each and (b) two nested messages in which one message is intended for one or (c) two (common) receivers and both messages are intended for all other (private) receivers. In the latter two nested messages cases, we hence recover, in a top-down manner, previous results by Bidokhti, Prabhakaran and Diggavi obtained therein using network coding schemes based on rate-splitting and linear superposition coding tailored to the combination network, while in the first case we obtain a new capacity result for a non-nested message set, which was hitherto not studied. Furthermore, we show, via a suitable choice of the distribution of the auxiliary random variables and the encoding function in our framework, the achievability of rate pairs in two interesting examples of combination networks, with three and four common receivers each. These examples were used in the previous literature to show the sub-optimality of the rate-splitting and linear superposition coding mentioned earlier, and hence to motivate the additional consideration of a pre-encoding technique and a block-Markov linear superposition coding for the combination network, with the latter then lifted to the general broadcast channel. Our results suggest that the proposed framework here
for the general broadcast channel when specialized to the combination network is strong enough to incorporate the enhancements afforded by those two latter techniques, thereby suggesting among other things, that perhaps block-Markov superposition coding is not necessary in the general broadcast channel. Moreover, there is a trade-off between the complexity of the coding scheme within the class of schemes we propose when applied to the combination network and that of the determination of the distribution of the auxiliary random variables and the encoding function that achieve the capacity region. This may have interesting implications for the general broadcast channel as well.  











§ INTRODUCTION





The problem of sending two groupcast messages over the K-receiver broadcast channel (BC) is studied. Each such message is intended for a distinct group of receivers, with the two groups of receivers assumed to be arbitrary in general.

In spite of its apparent simplicity, this problem remains unsolved in general in the Shannon-theoretic sense. However, capacity results have been obtained in the literature for various special cases of the BC and for specific (especially degraded) message sets in the two and three-receiver cases, and more recently, in the general K-receiver case.

The most studied problem however of sending two messages over the BC is the two-receiver discrete memoryless (DM) case with private messages. The capacity region is notoriously difficult in general even in this case and remains unsolved in general to date. However, for the increasingly larger classes of degraded <cit.>, less noisy <cit.> and more capable <cit.> channels, the capacity region was found in the series of seminal papers <cit.> in the 1970s. In particular, the superposition coding scheme proposed in <cit.> was shown, using a clever identification of auxiliary random variable, to achieve the capacity region in <cit.> for the degraded BC. The same scheme was also shown to achieve the capacity region for the larger class of less noisy and more capable BCs in <cit.> and <cit.>, where the images-of-a-set technique <cit.> and the Csiszar sum lemma <cit.> were used to prove the converses, respectively.










The capacity region for the two-receiver DM BC with two nested (i.e., degraded) messages was found by Korner and Marton in 1977 <cit.>. Interestingly, with superposition coding as the achievability scheme and a converse based on the images-of-a-set technique <cit.>, the authors therein established the capacity region without any restriction on the channel. However, 
the generalization of this result for three or more receivers has remained elusive ever since.
















In the K-receiver BC with two nested messages the receivers can be classified into L common receivers that require only one (common) message and P private receivers that require both messages (with P+L=K). The result of Korner and Marton in <cit.> might suggest that the nested structure of the messages might render a straightforward extension of their superposition coding scheme to be capacity-optimal even in this K-receiver setting. However, the authors of <cit.> and <cit.> showed that superposition coding alone is not optimal for the three-receiver DM BC with one and two common receivers, respectively.

In the latter case, they proposed a more general scheme that involves a simple form of rate-splitting along with superposition coding <cit.>. However, even this scheme was only shown to achieve capacity for the restricted class of DM BCs wherein the private receiver is less noisy than one of the two common receivers. 

One of the challenges of obtaining capacity results for rate-splitting based schemes beyond the three-receiver case is the difficulty of obtaining a closed-form polyhedral description for the inner bound in terms of the message rates due to the large number of split rates possible.

We make progress on this problem in
<cit.> where an achievable rate region that generalizes in one direction the capacity result for the three-user, two-common receiver problem in <cit.> to arbitrary K and arbitrary L is obtained. In particular, the private message is split into L sub-messages, and each common receiver decodes the common message uniquely, and certain sub-messages of the private message assigned to it, indirectly. 
The inner bound is presented in terms of the two nested message rates only, by eliminating all split rates for any K and any L, in general. Also, this inner bound is shown to be capacity-optimal for various classes of channels characterized by certain pair-wise relationships between and among the common and private receivers <cit.>. For example, the scheme is optimal for the class of four-receiver DM BCs with L=3 and P=1 in which the private receiver is less noisy than two of the three common receivers.

Combination networks, first proposed in <cit.> to demonstrate that network coding can attain unbounded gain over routing alone, can be seen to be a special class of linear deterministic broadcast channels. The capacity regions of the combination network for the two- and three-receiver cases were established in <cit.> under the guise of fundamental constraints in multicast capacity regions and where the transmitter must transmit all possible 2^K-1 independent groupcast messages. The achievability scheme depends mainly on the rate transfer argument. For example, in a two-receiver combination network, we have three possible independent messages; two private messages and one common message. If the transmitter is able to simultaneously send a rate of 1 bit per channel use for each of the three messages, then by sending the same information in each of the two private messages, it must be able to send a common message at rate of 2 bits per channel use for both receivers. Another possible rate transfer operation is when the transmitter merely uses the common bit to send private information to one of the receivers. Then, the channel can deliver 2 bits of private message per channel use to that receiver and 1 bit to the other. 
  
In other words, the achievability of any 2^K-1-dimensional rate-tuple of messages implies the achievability of a certain 2^K-1-dimension rate region regardless of the channel. The approach of <cit.> is to exhaustively determine all possibilities for rate transfer to characterize the inner bound for K=2, whereas for K=3, rate transfer and network coding are employed to establish the inner bound. On the other hand, the outer bound depends on cut-set bounds with some extensions. These proofs of the converse are specific to K being two or three, and hard to extend to K>3. In fact, the capacity region of the general K-receiver combination network is an open problem to date for K>3.

Because it is unclear how to generalize the approach of <cit.> to more that three receivers since the complexity of rate transfer increases exponentially with the number of users, Tian in <cit.>, under the guise of latent capacity regions, effectively considers a restricted class of symmetric K-receiver combination networks with the capacities of certain sets of finite capacity links being the same, and with symmetric message rates, wherein the messages required by the same number of receivers have the same rate. 
By simplifying the channel model and the message structure in this manner, Tian was able to establish the symmetric capacity region (where the rates of all messages of the same order are equal) of the symmetric K-receiver combination network by extending the rate-transfer approach of <cit.> to this scenario.

Later, in <cit.>, Salimi et al. proposed a general framework for the outer bound of broadcast networks in which they obtain a large family of outer bounds based on the sub-modularity of entropy they call generalized cut-set bounds. These bounds are used to reproduce the outer bounds of <cit.> for the two- and three-receiver combination networks and, along with an explicit polyhedral description, the symmetric capacity region of the K-receiver symmetric combination network of <cit.>.




Romero and Varanasi in <cit.> obtain the capacity region for the combination networks via a top-down approach unlike in <cit.> for K≤ 3 and in <cit.> for K-user symmetric combination networks. They first obtained a inner bound for the much more general K-user DM BC with general message sets <cit.> and then specialized to the combination network to recover the results in <cit.> and <cit.>. This bolsters the case for considering superposition coding and rate splitting (i.e., without binning) in the DM BC and specializing it to the combination network for achieving even the general (not just symmetric) capacity region of the general (not only symmetric) combination network for K>3. This is the approach we take on the combination network in this paper for the two groupcast message set.

Meanwhile, the authors in <cit.> studied two nested message set broadcasting over the K-receiver combination network where three different coding schemes tailored to it were proposed. The first is a linear superposition coding scheme with rate splitting for the private message where the transmitted signal is obtained by the multiplication of a carefully designed matrix over a finite field with the information symbols vector over that field. The structure of this matrix follows the zero-structured matrices of <cit.> while the rank of this matrix dominates the feasibility of decoding analysis. This zero-structured matrix has a zero in specific positions such that, when it is multiplied with the information symbols, the received signal at each common receiver does not depend on too many private sub-messages. The second scheme is a linear superposition coding scheme with a pre-encoder, i.e., the information symbols vector is multiplied first by a pre-encoder matrix before it is multiplied with a zero-structured matrix. The purpose of the pre-encoder matrix is to introduce dependency among the sub-messages of the private message. The last coding scheme is a block Markov coding scheme. The main idea is, instead of introducing the dependency among the sub-messages of the private message by multiplying with a pre-encoder matrix over one-time (one-block) code, a block Markov coding scheme can be used to introduce those dependencies sequentially across blocks. Upon receiving all the n blocks, each receiver finds its intended message by performing backward decoding <cit.>. 

The second and third coding schemes of <cit.> are motivated via two examples, <cit.> and <cit.>. In <cit.>, it was shown that the second coding scheme (with pre-encoding) can achieve a rate pair that is not achievable by the first, while in <cit.> the block Markov coding scheme was shown to achieve a rate pair that was not achievable by the second coding scheme. The first rate splitting and linear superposition coding scheme, was shown to be capacity achieving for a general K-receiver combination network with at most two common receivers <cit.>. The second the third coding schemes were shown to be optimal for the general K-receiver combination networks with three common receivers <cit.>. Capacity for more than three common receivers remains an open problem.



 §.§ Main Contributions


In this work, we begin by proposing an inner bound for the general K-user DM BC with two general groupcast messages in Section <ref>. That inner bound is based on a class of coding schemes parameterized by a flexible form of message set expansion, and involves general forms of rate-splitting, superposition coding, unique and non-unique decoding. Specific choices of the message set expansion parameter in the two, three and K receiver DM BCs lead to recovering the previously proposed achievability schemes based on rate-splitting and superposition coding for two, three- and K-receiver DM BCs  <cit.>. 
Moreover, our inner bound also gives new and potentially strictly larger achievable rate regions than those proposed based on rate-splitting and superposition coding for two nested groupcast messages in the three- and K-receiver DM BCs of <cit.> and <cit.>, respectively. Furthermore, it gives classes of achievable rate regions for K-user DM BCs for any two non-nested groupcast message sets as well, none of which appear to have been proposed in the literature before for three or more receivers. Hence our inner bound provides a general and unifying framework for studying the problem of sending two groupcast messages over a K-receiver DM BC. It is in fact an adaptation of the rate-splitting and superposition coding framework recently proposed by Romero and Varanasi in <cit.> which is applicable to general message sets with any number (up to 2^K-1) of groupcast messages. By specializing to the two-message set case, our aim here is to gain an in-depth understanding (which <cit.> does not do) —via explicit descriptions, converses, and choices of extremal coding distributions —of the strength of an adaptation of the general inner bound of <cit.> in the two-message set case. 


The adaptation of the framework of <cit.> to the two groupcast message case considered here involves replacing unique joint decoding in the coding scheme of <cit.> with non-unique joint decoding at all common receivers that require just one of the two groupcast messages. While the adoption of non-unique decoding may or may not strictly improve the achievable rate region in general (which is difficult to prove one way or the other) we choose it because (a) it expands the rate region per coding distribution (b) it does not shrink the rate region taken as a union over all admissible coding distributions (c) there are fewer inequalities leading to relative ease of doing projections via the Fourier-Motzkin Elimination (FME) technique <cit.> and (d) proving converses becomes easier as a result in some special cases as well. 

Indeed, for the case of two groupcast messages where (a) each message is desired at K-1 receivers, and (b) one message is desired at K-1 receivers and the other at some arbitrary subset of receivers that includes the one where the first message is not desired, we obtain the capacity region for classes of partially ordered DM BCs wherein certain pairs of receivers are ordered by the well-known less noisy and more capable ordering relations. These results complement the ones we obtained recently for two nested groupcast messages in <cit.>. 


Beyond the fact that we propose a general and unifying framework 

which provides general descriptions of rate-splitting, superposition coding, unique and non-unique decoding, and a succinct characterization of the associated rate regions, 
the key novel aspect underlying our achievable schemes 
is the message set expansion. It affects how everything is done: how the messages are split, what messages are reconstructed and how they are superposed, which reconstructed messages are uniquely decoded and which are non-uniquely decoded by the private and common receivers, respectively. There are in general 2^2^K-3 expanded message sets and each gives a distinct achievable rate region for a given two-message set and K. Three specific choices of message set expansions for the three-receiver case previously considered in <cit.> with two nested messages with 2 common receivers recover the results therein while the rest of the other choices yield new rate region descriptions for that setting. More importantly, there are message set expansions that result in coding schemes that assign multiple codewords to certain groups of sub-messages (after message splitting) according to different distributions, a feature not found in any previously proposed coding schemes, 


to the best of our knowledge. To be sure, the largest message set expansion yields a rate region that subsumes all others but it also yields the most complex coding scheme of all. It is of interest to consider simpler coding schemes corresponding to smaller message set expansions when such schemes suffice to achieve capacity. 

To more explicitly show the strength of the proposed class of achievable rate regions we consider the combination network as a test case in Section <ref>. In particular, when specialized to the combination network, the largest of the class of inner bounds, 
corresponding to the most complex of the class of coding schemes,
is shown, via converse results, to “easily" result in the capacity region via the choice of a single distribution of the auxiliary random variables and encoding function for three different scenarios, namely, (a) the two messages are intended for two distinct sets of K-1 receivers each and (b) two nested messages in which one message is intended for one or (c) two (common) receivers and both messages are intended for all other (private) receivers. In the latter two nested messages cases, we hence recover, in a top-down manner, the previous result of <cit.> obtained therein using network coding schemes based on rate-splitting and linear superposition coding tailored to the combination network and two nested messages, while in the first case we obtain a new capacity result for a non-nested message set, which was hitherto unknown. Moreover, we also show that via the same and single choice of auxiliary random variables and choice of encoding function in our inner bound applied to the combination network we recover, in a top-down manner, the rate region of the rate-splitting and linear superposition coding given by <cit.> for any two nested messages set for the K-user combination network.

Furthermore, we show in Section <ref>, again in a top-down manner, via suitable choices of the distribution of the auxiliary random variables and the encoding function in our framework, the achievability of “difficult" rate pairs in two interesting examples of six- and seven-receiver combination networks studied in detail <cit.>, with three and four common receivers, respectively. The first example was proposed therein to show the sub-optimality of the rate-splitting and linear superposition coding scheme mentioned earlier, and hence to motivate the additional consideration of a pre-encoding technique in that case <cit.>. The second example was proposed to show the sub-optimality in turn of the pre-encoding technique as well, and to further motivate a third block-Markov linear superposition coding scheme for the combination network. Our results hence suggest that the proposed framework here and the associated class of achievable rate regions for the general broadcast channel may be strong enough that, when it is specialized to the combination network, it would incorporate the enhancements afforded by pre-encoding with rate-splitting and linear superposition coding and block-Markov linear superposition coding schemes of <cit.>.

The authors in <cit.> lift their block-Markov linear superposition coding scheme for the combination network to a block-Markov superposition coding for the general broadcast channel because the former can achieve the “difficult" rate pair of the 7-receiver combination network with four common receivers of <cit.> whereas their pre-encoding technique with linear superposition coding does not. The fact, however, that that rate pair can be achieved via our proposed inner bound suggests that perhaps block-Markov superposition coding is not necessary in the general broadcast channel. 



Finally, in Section <ref>, we show that the consideration of simpler coding schemes within the class we propose corresponding to suitably chosen smaller message set expansions suffice in each case to achieve capacity for the combination network for the three message set cases mentioned previously for which we have capacity results. However, finding the extremal distributions is more involved. This is what we do in detail in Section <ref> where the allowed dependencies among the auxiliary random variables are exploited. 

Thus, the results in Sections <ref> and <ref> on the combination network seems to suggest that there is perhaps a trade-off between the complexity of coding scheme adopted within the class of coding schemes we propose and the ease of finding coding distributions to extract much (if not all) of the performance of that scheme in DM BCs in general.


In other words, even if we know that a union of regions inner bound is the capacity region it may still be worthwhile to consider more complex coding schemes in the hope of discovering coding distributions that achieve the capacity region in more explicit form that otherwise may prove difficult or impossible.

The rest of this paper is organized as follows. In Section <ref>, we describe the system model. In Section <ref>, we present the new achievable rate region for the DM BC with two general groupcast messages and the capacity region for certain partially ordered DM BCs for certain message sets including one with two messages each required by K-1 receivers. The inner bound is specified for the nested messages case in Section <ref>. Then, in Section <ref>, we obtain the capacity regions for combination networks for three different message sets. In Section <ref> we illustrate the relation between our capacity regions for combination networks and those proposed before in <cit.>. In Section <ref>, a trade-off between complexity of coding scheme (via message set expansion) and choice of random coding distributions is studied. Finally, the paper is concluded in Section <ref>.    














































































§ SYSTEM MODEL AND PRELIMINARIES 





 §.§ System Model






The DM BC consists of a transmitter X∈𝒳, K receivers Y_i∈𝒴_k, for 1 ≤ k ≤ K, and the channel transition probability W(y_1, ⋯ , y_K|x) with the conditional probability of the sequence of n outputs at the K receivers, denoted as Y_1^n, ⋯ , Y_K^n with Y_k^n ≜ (Y_k,1, ⋯ , Y_k,n), respectively, for the n inputs X^n ≜ (X_1, ⋯ , X_n) factors as

    p(y_1^n, ⋯ , y_K^n|x^n)= ∏_j=1^nW(y_1,j, ⋯ , y_K,j|x_j)

where X_j, Y_1,j,⋯ Y_K,j are the channel input and outputs in the j^th channel use. Denote the set of consecutive integers from i to j as [i:j].
The message M_S∈ [1:2^nR_S] of rate R_S is indexed by the subset S⊆ [1:K] of receivers it is intended for. Define 𝖤 as the set of all message indices (with a message index being a subset of [1:K]) and let 𝖯 be the power set of [1:K] excluding the empty set. Hence, in general, 𝖤⊆𝖯. 

For any 𝖥⊆𝖯 and i∈[1:K], define 𝖶_i^𝖥 as the set of message indices in 𝖥 of messages intended for receiver i so that

    𝖶_i^𝖥≜{S∈𝖥:i∈ S}


Denote the set of all messages {M_S : S ∈𝖤} to be sent over a K-user DM BC as M_𝖤. A ({2^nR_S}_S ∈𝖤, n) code consists of (i) an encoder that assigns to each message tuple m_𝖤∈∏_S ∈𝖤[1:2^nR_S] a codeword x^n( m_𝖤) (ii) a decoder at each receiver, with the k^th decoder mapping the received sequence Y_k^n for each k ∈ [1:K] into the set of decoded messages {m̃_S : S ∈𝖶_k^𝖤}∈∏_S ∈𝖶_k^𝖤[1:2^nR_S], denoted as m̃_𝖶_k^𝖤. We will have occasion to refer to the received sequence at receiver k from times t_1 to t_2, which we denote as Y_k,t_1^t_2. For simplicity, we choose to write  Y_i,1^t (i.e., when t_1=1) as just Y_i^t.
The three-receiver DM BC is illustrated in Fig. <ref>. The probability of error P_e^(n) is the probability that not all receivers decode their intended messages correctly. The rate tuple ( R_S : S∈𝖤 ) is said to be achievable if there exists a sequence of ({2^nR_S}_S ∈𝖤,n) codes with P_e^(n)→ 0 as n  →∞. The closure of the union of achievable rates is the capacity region.



When describing examples, we find it convenient to make certain notational simplifications when no confusion arises. For example, consider the three-receiver DM-BC with the message index set 𝖤={{1}, {1,2,3}}, so that there are two messages M_{1} and M_{1,2,3}, the first one intended for the first receiver and the second for all three receivers. For simplicity, we will denote these messages as M_1 and M_123. Similarly, we will write their rates R_{1} and R_{1,2,3} simply as R_1 and R_123. Also, for convenience, we denote 𝖤={1, 123} in this case. 
In other words, for simplicity, and when there is no confusion, we abbreviate the set {i_1,i_2,..,i_N}⊆ [1:K] as i_1i_2 ⋯ i_N (adopting the convention that i_1 < i_2 < ⋯ < i_N) when all i_j ∈{0,1, ⋯ 9}. Note that with this notational simplification, when K=3, we have 𝖯={1,2,3,12,13,23,123}. If we have numbers and variables in the set, say as in {1,2,3,K-2,K-1,K}, we write the elements of the set consecutively as before but we separate the variables with dots to avoid confusion. Hence, the set {1,2,3,K-2,K-1,K} is abbreviated as 123.K-2.K-1.K, not 123K-2K-1K (which is confusing). If there is only one variable at the end, such as in {1,2,3,⋯,K-2} we still abbreviate it as by 123⋯ K-2 since there is no confusion here.

In some cases, especially when the set {i_1,i_2,..,i_N} has many elements, we find it more convenient to denote it by its complement. For example, the common message intended for all K receivers is denoted by M_123⋯ K-1.K. It is simpler to denote it as M_ϕ where ϕ is the empty set and S={1,2,3,⋯,K}\ S is the complement of S. Similarly, we can represent the message index set 𝖤={123⋯ K-2.K,123⋯ K-2.K-1} of two messages, each required by K-1 receivers, simply as 𝖤={K-1,K}. 







The combination network <cit.>, which is a special case of the general DM-BC, is described next. 
It consists, as described in <cit.>, of three layers of nodes, as shown in Fig. <ref> for the three-receiver case. The top layer consists of a single source node X, and the bottom layer consists of K receivers Y_i, i∈[1:K]. The middle layer consists of 2^K-1 intermediate nodes, denoted V_S for all S∈𝖯. The source is connected to each of the intermediate nodes V_S through a noiseless link of capacity C_S (per channel use). Receiver Y_i is connected to the intermediate nodes V_S for all S ∈𝖶_i^𝖯 via noiseless links of unlimited capacity. An equivalent representation for the combination networks is given in <cit.> wherein it is considered to be a network of noiseless DM BCs with the channel input X connected in different ways to the channel outputs (Y_1,Y_2, ⋯ ,Y_K) each through a noiseless BC. In particular, the channel input X contains 2^K-1 components V_S, for all S ∈𝖯. For each S, the component V_S ∈𝒱_S, where |𝒱_S|=2^C_S, is noiselessly received at each receiver Y_i for all i ∈ S and not received at the receivers Y_j with j∉S, i.e., Y_i= {V_S : S ∈𝖶_i^𝖯}≜ V_𝖶_i^𝖯.




 §.§ Just Enough Order Theory


We introduce ideas from order theory following the notation in <cit.>. Any set equipped with an order is an ordered set. Let P be such an ordered set and Q be a subset of P. We say that Q is 



  * an up-set if x∈ Q, y∈ P, and y≥ x implies y∈ Q.

  * a down-set if x∈ Q, y∈ P, and y≤ x implies y∈ Q.
 Note that these two types of subsets are duals of each other, i.e., if Q is a down-set then P\ Q is an up-set. Moreover, for any subset Q⊆ P, we define the smallest down-set containing Q as ↓_P Q = {y ∈ P: y≤ x, x ∈ Q} and the smallest up-set containing Q as ↑_P Q = {y ∈ P: x≤ y, x ∈ Q}. Further, for any Q_1,Q_2⊆ P, denote the part of the smallest down-set containing Q_1 that is also in Q_2, i.e., ( ↓_P Q_1 ) ∩ Q_2, as ↓_Q_2 Q_1. Similarly, ( ↑_P Q_1 ) ∩ Q_2, the smallest up-set of Q_1 that is in Q_2, is denoted as ↑_Q_2 Q_1. Henceforth, for brevity, ↓_Q_2 Q_1 (or ↑_Q_2 Q_1) is referred to as the down-set (or up-set, respectively) of Q_1 in Q_2.

Also, let ℱ_↓(P) denote the family of all down-sets of P and ℱ_↑(P) denote the family of all up-sets of P. Finally, let ℱ_↑_Q(P) and ℱ_↓_Q(P) denote the family of all up-sets and all down-sets of P that contain Q, respectively. 

In this paper, we will take the ground set to be a set of sets, such as the set of non-empty subsets of [1:K], the receiver index set. We will denote a set of sets in sans-serif font to distinguish it from sets. The order on the ground set considered in this paper is exclusively that of set inclusion, i.e., S_1≤ S_2 if and only if S_1⊆ S_2. 
Recall that, for simplicity, we write the index set {i_1,i_2,..,i_N} as i_1i_2 ⋯ i_N (adopting the convention that i_1 < i_2 < ⋯ < i_N). To illustrate such notation, consider the example of K=3. The ground set in this case could be the set of all non-empty subsets of [1:3], denoted as 𝖯 = {1,2,3,12,13,23,123}. The down-set of, say, {12} in 𝖯 is ↓_𝖯{12}={1,2,12}, and the up-set of {12} in 𝖯 is ↑_𝖯{12}= {12,123}. For the same 𝖯, we have ↑_𝖶_3^𝖯{12}={↑_𝖯{12}}∩𝖶_3^𝖯={123}, whereas ↓_𝖶_3^𝖯{12}={↓_𝖯{12}}∩𝖶_3^𝖯= ϕ. 


To illustrate families of up-sets and down-sets, consider the ground set 𝖯={1,2,12}. Then, ℱ_↓(𝖯) = {{1} , {2} , {1,2} , {1,2,12}}, while ℱ_↑(𝖯) = {{1,12},{2,12},{12},{1,2,12}}. For the same 𝖯={1,2,12}, we have ℱ_↑_{1}(𝖯)={{1,12},{1,2,12}} and ℱ_↓_{1}(𝖯)={{1},{1,2},{1,2,12}}.










The following relationships are true:


  * For any set S={i_1,i_2,⋯, i_N}⊆{1,2,⋯ ,K}, we have  

    ∪_k∈ S𝖶_k^𝖯   = ↑_𝖯{i_1,i_2,⋯, i_N}
    ∩_k∈ S𝖶_k^𝖯   = ↑_𝖯{i_1i_2⋯ i_N}


  * For any set of sets 𝖶⊆𝖯,

    ∪_S∈𝖶↓_𝖶_i^𝖯{S}   = ↓_𝖶_i^𝖯𝖶
    ∩_S∈𝖶↓_𝖶_i^𝖯{S}   = ↓_𝖶_i^𝖯{∩_S∈𝖶S}











  * For any set S=i_1i_2⋯ i_N ⊂{1,2,⋯, K} and i∈ [1:K] 

    ↓_𝖶_i^𝖯{i_1,i_2,⋯, i_N}∪↑_𝖶_i^𝖯{S}   =𝖶_i^𝖯
    ↓_𝖶_i^𝖯{i_1,i_2,⋯, i_N}∩↑_𝖶_i^𝖯{S}   =ϕ
    ↓_𝖶_i^𝖯{S}∪↑_𝖶_i^𝖯{i_1,i_2,⋯ ,i_N}   =𝖶_i^𝖯
    ↓_𝖶_i^𝖯{S}∩↑_𝖶_i^𝖯{i_1,i_2,⋯ ,i_N}   =ϕ






The proofs of all the above equalities are straightforward given the order theoretic definitions except that of (<ref>) and (<ref>), which are given in Appendix <ref>.







§ A CLASS OF ACHIEVABLE RATE REGIONS AND SOME CONVERSES: TWO  MESSAGES





This paper is devoted to the problem of sending two groupcast messages over the K-receiver DM-BC. Let the two general messages be M_S_1 and M_S_2, so that the message index set is 𝖤={S_1,S_2}. Without loss of generality, we let S_1={1, 2 , ⋯ , P, P+1, ⋯ , P+L_1} and S_2= {1, 2, ⋯, P, P+L_1+1,⋯ ,P+L_1+L_2}. The set of indices of receivers that decode both messages is denoted as S_p={1,2,⋯ P}, that decode only M_S_1 is denoted by S_l_1={P+1,P+2,⋯ , P+L_1}, and that decode only M_S_2 is denoted by S_l_2={P+L_1+1, P+L_1+2, ⋯ , P+L_1+L_2}. The P receivers with indices in S_p can be thought of as private receivers, the L_1 receivers with indices in S_l_1 can be thought of as the first group of common receivers that decode only M_S_1, and the L_2 receivers with indices in S_l_2 can be thought of as the second group of common receivers that decode only M_S_2. Obviously, P+L_1+L_2=K. 

Of special interest for proving converses later in this paper are the three special cases of (a) two order-(K-1) messages (i.e., messages that are intended at two distinct sets of K-1 of the K users) so that L_1=L_2=1 and P=K-2 (b) one order-(K-1) message and another order-(P+1) message so that L_1=K-P-1 and L_2=1 for any 0 ≤ P ≤ K-2 and (c) two nested messages so that either L_1=0 or L_2=0.
  
Next, we obtain a class of new inner bounds for the K-user DM BC with two general messages.

We use order theory to describe our result. In particular, let 𝖯, the set of all non-empty subsets of receiver indices [1:K], be the ground set. As stated previously, we will think of 𝖯 as an ordered set with the order relation defined by set inclusion, i.e., S ≤ S' if and only if S ⊆ S'. Evidently, the message index set 𝖤 = { S_1, S_2}⊂𝖯. 


The class of inner bounds of the next theorem is parameterized by a message index superset 𝖥 that is some superset of message indices that contains the message indices in 𝖤 and can be as large as 𝖯, so that 𝖯⊇𝖥⊇𝖤. For each K and each message set 𝖤, every choice of the design parameter 𝖥 in the next theorem gives a distinct inner bound. Note that there are 2^2^K-3 choices of 𝖥 for any two groupcast message set 𝖤 = {S_1, S_2}. We refer to expanding 𝖤 to 𝖥 simply as message set expansion. While the choice of 𝖥 strongly determines the coding scheme employed and hence the rate region it achieves, both the description of the scheme and the characterization of its rate region can be done for any admissible 𝖥 in a general way.






Let 𝖥 be some message index superset so that 𝖯⊇𝖥⊇𝖤. The rate pair (R_S_1, R_S_2) is achievable if there exist non-negative up-set split rates (R_S→ S' :S∈𝖤, S' ∈𝖥, S⊆ S^') such that for each i ∈{1,2}

    R_S_i=∑_S^'∈↑_𝖥 S_i R_S_i → S^'

and reconstruction rates 

    R̂_S^'= ∑_S∈↓_𝖤 S^'R_S→ S^'    ∀ S^'∈𝖥

that satisfy the inequalities

    ∑_S^'∈𝖡R̂_S^'≤ I(U_𝖡; Y_j|U_𝖶_j^𝖥\𝖡, Q),  ∀𝖡∈ℱ_↓(𝖶_j^𝖥),  ∀  j∈ S_p

and, for each i ∈{1,2}, the inequalities

    ∑_S^'∈𝖡R̂_S^'≤ I(U_𝖡; Y_j|U_𝖶_j^𝖥\𝖡, Q),  ∀𝖡∈ℱ_↓_{S_i}(𝖶_j^𝖥),  ∀ j∈ S_l_i




for some time sharing and auxiliary random variables Q and U_𝖥≜{U_S : S ∈𝖥} with a joint distribution that factors as p(q, u_𝖥)= p(q) ∏_S∈𝖥p(u_S|u_(↑_𝖥 S)\{S },q) and X taken to be a deterministic function of (Q, U_𝖥). 




A detailed proof is given in Appendix <ref>. We only provide an outline here.

Each message M_S is divided into a collection of sub-messages M_S→ S' where S' ∈↑_𝖥 S, for each S∈𝖤 as per (<ref>). This explains why this form of rate-splitting is called up-set rate splitting.

The sub-message M_S→ S^' will be treated as if it was intended for the receivers in the larger set S^' instead of in S. 
By reassembling all sub-messages intended for the set of receivers with indices in S', we obtain the reconstructed message M̂_S^'=(M_S→ S^':S∈↓_𝖤 S^') for all S^'∈𝖥 with rate R̂_S^' given by (<ref>). Note that the message set expansion parameter 𝖥 determines how the message splitting is done and hence how the newly reconstituted messages M_S→ S' for all S^'∈𝖥 are reconstructed, which in turn determines the superposition coding scheme described next.

The set of reconstructed messages with indices in 𝖥 are encoded using superposition coding with dependent auxiliary codeword generation according to the subset inclusion order (cf. <cit.>) as described in Appendix <ref>. Private receiver Y_j jointly decodes the desired messages M_S_1 and M_S_2 
via the unique joint decoding of the set of reconstructed messages ( M̂_S : S ∈𝖶_j^𝖥 ) that contain those two messages for every j∈ S_p. As shown in Appendix <ref>, the reconstructed messages can be reliably transmitted over the DM BC if the partial sums of the reconstructed message rates satisfy the inequalities given by (<ref>).
On the other hand, the common receiver Y_j (with j∈ S_l_i, i ∈{1,2}) only needs to decode the message M_S_i. 

Hence, non-unique decoding can be employed by these receivers. Note that for each j∈ S_l_i, the reconstructed messages ( M̂_S : S ∈𝖶_j^𝖥 ) contain the desired message M_S_i as well as partial interference via up-set message splitting and reconstruction. Thus, among these reconstructed messages, only the ones with indices in ↑_𝖥𝖶_j^𝖤  are uniquely decoded because per (<ref>) and (<ref>), all such reconstructed messages are needed to reconstitute this receiver's desired message M_S_i, whereas the rest of the reconstructed messages do not, and these messages are hence decoded non-uniquely. This happens successfully with high probability if the partial sums of the reconstructed message rates satisfy the inequalities given by (<ref>).








In the conference paper <cit.> by Romero and Varanasi, an inner bound for a general message set 𝖤 was proposed that used the same encoding scheme but with 
each receiver Y_j uniquely decoding all reconstructed messages with indices in 𝖶_j^𝖥 for all j. Hence, a common receiver may end up decoding some reconstructed messages that only contain sub-messages of the message that is not of interest to it which in turn produces more inequalities on the reconstruction rates, hence possibly strictly limiting the achievable rate region compared to the one given in Theorem <ref>. 
The idea of non-unique decoding was first presented in the context of the two-user interference channel in <cit.> and later used as indirect decoding in <cit.> for the DM BC with the nested message set 𝖤={1,123} to make notable progress on establishing a matching converse for a class of DM BCs. In both those cases, each receiver that does non-unique decoding decodes its desired message(s) uniquely and the common sub-message of the undesired message non-uniquely. That idea can be seen to be generalized here as follows: each common receiver decodes (a) a subset of reconstructed messages intended for it uniquely, each necessarily including one or more sub-message of the desired message and possibly also some sub-message(s) of the undesired message and (b) a subset of reconstructed messages that do not include any sub-message of the desired message non-uniquely. Moreover, it is interesting, thanks to the order-theoretic formulation, that a general expression (<ref>) for the achievable rate region is possible even after incorporating such decoding at the common receivers. 




Next, we provide a simple example to illustrate  Theorem <ref>.


Consider the case K=3 and 𝖤={1,23} so that P=0, L_1=1, and L_2=2 and S_p=ϕ,  S_l_1={1}, S_l_2={2,3}. Choose the largest possible message index superset 𝖥=𝖯. 

Up-set message splitting described in the proof of Theorem <ref> yields M_1 = ( M_1→ 1, M_1→ 12, M_1→ 13, M_1→ 123 ) and M_23= (M_23 → 23, M_23 → 123) with split rates defined according to (<ref>). The reconstructed messages and their rates as per (<ref>) are given as 

    M̂_1=M_1→ 1      R̂_1=R_1→ 1
       M̂_2=ϕ      R̂_2=0
       M̂_3=ϕ      R̂_3=0
       M̂_12=M_1→ 12      R̂_12=R_1→ 12
       M̂_13=M_1→ 13      R̂_13=R_1→ 13
       M̂_23=M_23→ 23      R̂_23=R_23→ 23
       M̂_123=(M_1→ 123,M_23→ 123)        R̂_123=R_1→ 123+R_23→ 123


The resulting rate-splitting/superposition coding scheme described in the proof of Theorem <ref> is illustrated in Fig. <ref> with the specifics explained in its caption. The key point to note is the generation of the U_2 and U_3 codewords towards the end of that caption which has to do with R̂_2 = 0 and R̂_3 = 0. For every pair of U_12 and U_23 codewords there is a single U_2 codeword and similarly for every pair of U_13 and U_23 codewords there is a single U_3 codeword. If one uses the well known “cloud and satellite" symbolism, it is as if each U_2 (and U_3) codeword were a single satellite codeword for every pair of U_12 and U_23 (and U_13 and U_23, resp.) cloud codewords. Whereas, the usual picture one has is quite the contrary in that for every cloud codeword there are many satellite codewords. Note that this latter and usual symbolism works for all other codewords (i.e., other than U_2 and U_3 codewords). It is no accident that it is precisely the case that only R̂_2 = 0 and R̂_3 = 0, which in turn is a consequence of having chosen the message index superset 𝖥 to be equal to 𝖯. This phenomenon of zero-rate codebooks superposed over other codebooks has crucially important consequences that we will explain further in this example and in more depth in much of the paper later.

From the conditions for reliable communication of the messages at their desired destinations given in (<ref>) (note that  (<ref>) is vacuous since S_p =ϕ in this example) of Theorem <ref>, we get that the reconstructed message rates must satisfy the inequalities

    R̂_123+R̂_13+R̂_12+R̂_1≤   I(U_123,U_13,U_12,U_1;Y_1 |Q)
    R̂_13+R̂_12+R̂_1≤   I(U_13,U_12,U_1;Y_1|U_123,Q)
    R̂_12+R̂_1≤   I(U_12,U_1;Y_1|U_123,U_13,Q)
    R̂_13+R̂_1≤   I(U_13,U_1;Y_1|U_123,U_12,Q)
    R̂_1≤   I(U_1;Y_1|U_123,U_13,U_12,Q)
    
    R̂_123+R̂_23+R̂_12≤   I(U_123,U_23,U_12,U_2;Y_2|Q)
    R̂_23+R̂_12≤   I(U_23,U_12,U_2;Y_2|U_123,Q)
    R̂_23≤   I(U_23,U_2;Y_2|U_123,U_12,Q)
    
    R̂_123+R̂_23+R̂_13≤   I(U_123,U_23,U_13,U_3;Y_3|Q)
    R̂_23+R̂_13≤   I(U_23,U_13,U_3;Y_3|U_123,Q)
    R̂_23≤   I(U_23,U_3;Y_3|U_123,U_13,Q)

for some p(q) p(u_123,q)p(u_12|u_123,q)p(u_13|u_123,q) p(u_23|u_123,q) p(u_1|u_12,u_13,u_123,q) p(u_2|u_12,u_23,u_123,q) p(u_3|u_13,u_23,u_123,q) are achievable. 





The inequalities above may appear to be “standard" for rate-splitting, superposition coding and non-unique 
decoding if one realizes that in order to get a satellite codeword right one has to get its cloud codeword right as well and hence one doesn't have sum rate inequalities for all possible sum rates (cf. <cit.>). However, even though R̂_2 = 0 and R̂_3 = 0 the unusual, notice the unusual presence of the U_2 and U_3 auxiliary random variables.



While the above reliability conditions may seem almost familiar (except for the presence of U_2 and U_3), it is important to note that such inequalities have been succinctly expressed in Theorem <ref> in complete generality, i.e., for any K, any message set 𝖤={S_1, S_2}, and any choice of the message set expansion parameter 𝖥. The order-theoretic formulation turns out to just the right one to express a result of its generality with such analytical brevity. Quite importantly, this brevity is key to further work with the result of Theorem <ref> as we do in the rest of this paper.



As an aside, we note the simple point that the inner bound for the same example using the result in <cit.> would have the two additional inequalities

    R̂_12≤ I(U_12,U_2;Y_2|U_123,U_23,Q)
    R̂_13≤ I(U_13,U_3;Y_3|U_123,U_23,Q)

because in that scheme 
receiver Y_2 uniquely decodes the undesired sub-message M_1→ 12 and receiver Y_3 uniquely decodes the undesired sub-message M_1→ 13, whereas in the scheme of Theorem <ref> those sub-messages are decoded non-uniquely at Receivers 2 and 3, respectively.


In previous uses of non-unique decoding in <cit.> (see also the several references of <cit.>) it has been shown that the rate region for non-unique decoding taken as a union of admissible distributions is not strictly larger than that with unique decoding. Whether the use of non-unique decoding strictly enlarges the inner bound of Theorem <ref> is not the focus of this work, although a strict enlargement of the rate region would be desirable. Rather, we have adopted non-unique decoding because (a) it expands the rate region per coding distribution (i.e., admissible distribution of the auxiliary random variables and encoding function) (b) it does not shrink the rate region taken as a union over all admissible coding distributions and (c) there are fewer inequalities leading to relative ease of doing projections via FME and (d) proving converses in some special cases becomes easier as a result as we show later since there are fewer inequalities in the rate region after FME. The points (b-d) have been articulated before in their respective contexts (cf. <cit.>), and as in those contexts, and even to a greater degree here, we realize the benefits (c-d) in performing FME more efficiently than would be otherwise possible with unique decoding (if FME would be possible at all with reasonable effort in the latter case) in obtaining Corollaries <ref>,
<ref>, and 
<ref>, and
proving converse results for the DM BC with certain message sets in Theorem <ref> 
and Proposition 
<ref>, all of which are to follow. But it is also the first point (a) that we find very interesting and useful when we specialize Theorem <ref> to the combination network, and choosing certain single coding distributions to obtain “large" rate regions and even extremal ones in some cases leading to the capacity region as in Theorem <ref> and Propositions <ref>,  <ref> and <ref> and Examples <ref> and <ref> to follow. 
Indeed, all of Section <ref> is dedicated to the interesting task of finding simple coding schemes among the class of coding schemes proposed and analyzed in Theorem <ref> that yet achieve the capacity region in several settings of message sets through clever choices of the coding distribution in each case. The success we achieve in Section <ref> is due in no small part to non-unique decoding as well.
Finally, we note that
even if some of the aforementioned achievability and capacity results were possible with unique decoding we believe that the associated rate and capacity region descriptions would be less compact, and the proofs more laborious, in each case than the ones we obtain here.





In Theorem <ref>, for every possible message set expansion from 𝖤 to 𝖥 such that 𝖯⊇𝖥⊇𝖤, and there are 2^2^K-3 of them, we get a different achievable region which involves a different set of auxiliary random variables. Denote it as R(K,𝖤,𝖥) for brevity.
Expanding 𝖥 leads to finer message splitting, and hence to the use of more auxiliary random variables/codebooks, and it therefore cannot reduce the achievable region. Hence, the full power of the coding scheme of Theorem <ref> is realized by setting 𝖥=𝖯. This fact is exploited extensively in Sections <ref>-<ref>.


More generally, if 
𝖥_1 ⊃𝖥_2 then R(K,𝖤,𝖥_1) ⊇ R(K,𝖤,𝖥_2). 

Nevertheless, we prefer to leave 𝖥 as a parameter to be chosen rather than replace it with 𝖯 in Theorem <ref> since a smaller 𝖥 leads to a simpler coding scheme (with fewer random variables and hence fewer codebooks), and sometimes a specific such choice suffices to achieve capacity as we illustrate later in Section <ref>.  




Interestingly, when we choose 𝖥⊃↑_𝖯𝖤 we get some zero reconstruction rates in (<ref>) and this important point is explained in this remark. For example, when we chose 𝖥=𝖯⊃↑_𝖯𝖤 in Example <ref>, we got two zero reconstruction rates, namely, R̂_2 and R̂_3, per (<ref>). 

This is reflected in Fig. <ref> which depicts the superposition coding scheme described in Appendix <ref> for

Example <ref>. In particular, the codewords u_2^n(m̂_123,m̂_12,m̂_23) and u_3^n(m̂_123,m̂_13,m̂_23) do not encode more messages than those already encoded in u_12^n, u_13^n, and u_23^n. As mentioned earlier, for every pair of codewords u_12^n(m̂_123,m̂_12) and u_23^n(m̂_123,m̂_23), we generate a single codeword u_2^n(m̂_123,m̂_12,m̂_23) according to ∏_i=1^n p(u_2i|u_12i,u_23i,u_123i). Similarly, for every pair of codewords u_13^n(m̂_123,m̂_13) and u_23^n(m̂_123,m̂_23), we generate a single codeword u_3^n(m̂_123,m̂_13,m̂_23) according to ∏_i=1^n p(u_3i|u_13i,u_23i,u_123i). However, since R̂_1≠ 0, we generate 2^nR̂_1 codewords u_1^n(m̂_123,m̂_13,m̂_12,m̂_1) for every pair of codewords u_12^n(m̂_123,m̂_12) and u_13^n(m̂_123,m̂_13).   Hence, in general, in the coding scheme of Theorem <ref>, superposition coding is not only used to encode a message over other messages (satellites over cloud centers), but also to encode some messages multiple times using different distributions. This novel feature of generating a single satellite per one or more cloud centers will be present in general as long as we choose 𝖥 such that 𝖥⊃↑_𝖯𝖤.















 §.§ Explicit polyhedral representation for the inner bound with 𝖤={K,K-1} 



For this case, we have P=K-2, L_1=1 and L_2=1. Hence, S_p ={1, ⋯ , P}, S_l_1={K-1}, S_l_2={K}. We use Theorem <ref> to get a polyhedral description of the inner bound by eliminating the split rates. Here, the message M_K is split into two parts via (<ref>), i.e., M_K= (M_K→K,M_K→ϕ) while the other message M_K-1 is split into M_K-1→K-1 and M_K-1→ϕ. The polyhedral representation is presented in the next corollary.




An inner bound of K-user DM BC for the message index set 𝖤={K,K-1} is the set of rate pairs (R_K,R_K-1) satisfying

    R_K-1   ≤ I(U_𝖶_K^𝖯;Y_K|Q) 
    
    R_K   ≤ I(U_𝖶_K-1^𝖯;Y_K-1|Q) 
    
    R_K-1+R_K   ≤  I(U_𝖶_j^𝖯;Y_j|Q) ∀ j∈  S_p  
    
    R_K-1+R_K   ≤   I(U_↓_𝖶_j^𝖯{K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K},Q)  + I(U_𝖶_K^𝖯;Y_K|Q)   ∀ j∈ S_p ∪{ K-1}
    
    R_K-1+R_K   ≤ I(U_↓_𝖶_j^𝖯{K-1};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K-1},Q) + I(U_𝖶_K-1^𝖯;Y_K-1|Q)   ∀ j∈ S_p ∪{ K}
    
    2R_K-1+2R_K   ≤ I(U_↓_𝖶_j^𝖯{K-1,K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K-1,K},Q)+I(U_𝖶_K^𝖯;Y_K|Q)+ I(U_𝖶_K-1^𝖯;Y_K-1|Q)∀ j∈  S_p
 
for some p(q, u_𝖯)= p(q) ∏_S∈𝖯p(u_S|u_↑_𝖯 S\{ S },q) and X as a deterministic function of (Q, U_𝖯).


The proof begins with the result of Theorem <ref> by setting 𝖥=𝖯. In other words, the rate region of Corollary  <ref> is R(K,𝖤={K,K-1},𝖥=𝖯) expressed in explicit form after having projected split rates away.
Since we have L_1=1 and L_2=1, we have from (<ref>) that each message is split only into two parts so that

    R_K-1=R_K-1→K-1+R_K-1→ϕ
       R_K=R_K→K+R_K→ϕ

Moreover, from (<ref>),
we have the three non-zero reconstruction rates  R̂_ϕ,R̂_K,R̂_K-1, such that

    R̂_ϕ   =R_K→ϕ+R_K-1→ϕ
    R̂_K   =R_K→K
    R̂_K-1   =R_K-1→K-1
 


Hence, we can write (<ref>) as follow

    R_K-1+R_K≤ I(U_𝖶_j^𝖯;Y_j|Q)
       R_K-1→K-1≤  I(U_↓_𝖶_j^𝖯{K-1};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K-1},Q)
       R_K→K≤ I(U_↓_𝖶_j^𝖯{K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K},Q)
       R_K-1→K-1+R_K→K≤
          I(U_↓_𝖶_j^𝖯{K-1,K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K-1,K},Q)
 for all j∈ S_p. This follows from the fact we have just three non-zero reconstruction rates, and hence, 𝖡∈{𝖶_j^𝖯, ↓_𝖶_j^𝖯{K-1}, ↓_𝖶_j^𝖯{K},↓_𝖶_j^𝖯{K-1,K}}, because the rest of the down-sets in ℱ_↓(𝖶_j^𝖯) give redundant inequalities. 





On the other hand, we can rewrite (<ref>) as follows

    R_K+R_K-1→ϕ≤ I(U_𝖶_K-1^𝖯;Y_K-1|Q)
       R_K→K≤ I(U_↓_𝖶_K-1^𝖯{K};Y_K-1|U_𝖶_K-1^𝖯\↓_𝖶_K-1^𝖯{K} , Q)
       R_K-1+R_K→ϕ≤ I(U_𝖶_K^𝖯;Y_K|Q)
       R_K-1→K-1≤ I(U_↓_𝖶_K^𝖯{K-1};Y_K|U_𝖶_K^𝖯\↓_𝖶_K^𝖯{K-1},Q )
 
Moreover, in (<ref>) the only sets in ℱ_↓_{K}(𝖶_j^𝖯) and ℱ_↓_{K-1}(𝖶_j^𝖯) that do not give redundant inequalities are {𝖶_𝗃^𝖯,↓_𝖶_j^𝖯𝖶_j^𝖤 for j∈{K-1,K}} again because we have just three non-zero reconstruction rates where 𝖶_j^𝖤={K} for j=K-1 and 𝖶_j^𝖤={K-1} for j=K. By eliminating the sub-rates from (<ref>)-(<ref>) and (<ref>)-(<ref>) using FME <cit.>, we get the polyhedral description (<ref>)-(<ref>). 




 §.§ Converses for 𝖤={K,K-1} and more generally for 𝖤={K, S} for any S with K ∈ S


In what follows, we show that the achievable rate region of Corollary <ref> is optimal for certain classes of partially ordered DM BCs with the partial order denoting the relative strengths of channels to the receivers in terms of the well known ordering relations of one receiver being less noisy or more capable than another. We state here those definitions (including two for the more capable order) for completeness.
   <cit.>
Receiver Y_s is less noisy than Y_c if I(U;Y_s)≥ I(U;Y_c) for all p(u,x). Henceforth, we denote this condition as Y_s  ≽ Y_c.

 
Receiver Y_s is more capable than Y_c if for every 0< ϵ < 1 and δ>0 there exists an n_0, a function of ϵ and δ, such that for n>n_0 every ϵ-code ℬ⊆𝒳^n for the channel Y_c contains an ϵ-code ℬ^' for the channel Y_s such that 1/nlog(|ℬ^'|)>1/nlog(|ℬ|)-δ. 

This is essentially equivalent to saying that Y_s could decode any codebook that Y_c could decode. Korner and Marton showed that the above definition is equivalent to following one.
 <cit.> 
Receiver Y_s is more capable than Y_c if I(X;Y_s) ≥ I(X;Y_c) for all p(x). Henceforth, we denote this condition as Y_s  ⊒ Y_c[This notation can, but should not be, mistaken for “superset" (which, conveniently, is meaningless in the present context).]. 





The capacity region of K-user DM BC for the message index set 𝖤={K,K-1}, i.e., S_p={1,2,… ,K-2 } is the set of rate pairs (R_K,R_K-1) satisfying

    R_K-1   ≤ I(U;Y_K)
    
        R_K-1+R_K   ≤ I(X;Y_j|U)+I(U;Y_K)  ∀ j∈ S_p ∪{K-1}
    
        R_K-1+R_K   ≤ I(X;Y_K-1)
 for some p(u,x) for each of the following two classes of partially ordered DM BCs

    
  A. DM BCs for which Y_j  ⊒  Y_K-1⊒ Y_K for all j∈ S_p
    
  B. DM BCs for which Y_i ≽ Y_K for all i∈ S_p ∪{K-1}

 

The achievability proof of (<ref>)-(<ref>)  follow from Corollary <ref> by setting U_ϕ=U, U_K=X while setting the rest of the auxiliary random variables to be constants and |Q|=1. In particular, the inequalities in (<ref>)-(<ref>) are obtained from (<ref>), (<ref>), and (<ref>), respectively. Note that from (<ref>), we get the inequality R_K-1+R_K≤ I(X;Y_j)  ∀ j∈ S_p which is redundant for both classes A and B of DM BCs defined in the statement of Theorem <ref>. This concludes the achievbility proof. 


For Class A of DM BCs, that is, when Y_j  ⊒  Y_K-1⊒ Y_K for all j∈ S_p, the region in (<ref>)-(<ref>) can be written as 

    R_K-1   ≤ I(U;Y_K)
    
        R_K-1+R_K   ≤ I(X;Y_K-1|U)+I(U;Y_K) 
    
        R_K-1+R_K   ≤ I(X;Y_K-1)
 
for some p(u,x). There are two ways to prove the converse for the above inequalities. One is to use the Csiszar sum lemma <cit.> with the optimal choice of U_i= M_K-1,Y_K-1,1^i-1,Y_K,i+1^n. This proof is given in detail in Appendix <ref>. The other is to notice that the region (<ref>)-(<ref>), is the capacity region of the two receiver (Y_K-1,Y_K) more capable DM BC with two private messages (cf. <cit.>). In other words, it depends only on the channels of the two receivers Y_K-1, Y_K, although we are considering the K-receiver DM BC. Since Receiver Y_K-1 decodes from X it is forced to decode both messages, and hence, from Definition <ref>, adding any number of receivers that are more capable than Y_K-1, does not change the capacity region from the two receiver case. This concludes an alternative proof of the converse for the Class A of DM BCs.
  
For Class B of DM BCs in which Y_i ≽ Y_K for all i∈ S_p ∪{K-1}, the region in (<ref>)-(<ref>) can be written as 

    R_K-1   ≤ I(U;Y_K)
    
        R_K-1+R_K   ≤ I(X;Y_j|U)+I(U;Y_K)  ∀ j∈ S_p ∪{K-1}

for some p(u,x) where  (<ref>) are redundant for this class of channels. The converse proof depends on the information inequality in <cit.> and the details are given in Appendix <ref>. 


Evidently, one can exchange the roles of Y_K and Y_K-1 in Theorem <ref> to get a result that mirrors it by exchanging K-1 and K in the rate region and in the definition of classes of DM BCs.



 
 
 


 
 






We showed in <cit.> that the region in (<ref>)-(<ref>) is also the capacity region of the Class B of DM BCs for two nested messages with a single common receiver, i.e., 𝖤={ϕ, K}, where a similar achievability scheme and converse proof were used. Hence, even though we relaxed the decoding requirements for receiver Y_K-1 by considering the message set 𝖤={K-1, K} compared to 𝖤={ϕ, K}, we can prove the same outer bound for both message sets. Hence, our converse proof in Appendix <ref> is stronger than the one in <cit.>. Applied to the case of K=3, this implies that the converse proof in Appendix <ref> (for 𝖤={12,13}) is stronger than the one for 𝖤={12,123} in <cit.> where the Csiszar sum lemma is used, not the information inequality as in Appendix <ref>.  From the achievability perspective, there is no loss of optimality and it does not reduce the achievable region to force receiver Y_K-1 to decode M_K-1 as long as Y_K-1≽ Y_K. 





In the following proposition, we extend the argument in the previous remark to its most general conclusion by considering the message set 𝖤={K,S} (where K∈ S), and hence, relaxing the decoding requirements for the receivers Y_i i∈S instead of only Y_K-1, and still getting the same capacity region for the same class of channels.  



The capacity region of K-user DM BC with message index set 𝖤={K,S}, where S∈𝖯,K∈ S for the class of channels Y_i ≽ Y_K for all i∈{1,2,⋯ ,K-1} is the set of rate pairs (R_K,R_S) satisfying

    R_S   ≤ I(U;Y_K)
    
        R_S+R_K   ≤ I(X;Y_j|U)+I(U;Y_K)  ∀ j∈{1,2,⋯,K-1}

for some p(u,x). 


The proof is left to the reader since it is similar to that of Theorem <ref>. 


Consider Proposition <ref> in its strongest case, i.e., for S=K. Here, the proposition in effect states that forcing the receivers Y_1,Y_2,⋯,Y_K-1 to decode M_K is without loss of optimality as long as Y_i ≽ Y_K for all i∈{1,2,⋯ ,K-1}. While from the converse perspective, relaxing the decoding requirement of the receivers Y_1,Y_2,⋯,Y_K-1 by considering  𝖤={K,K} instead of 𝖤={K,ϕ} does not enlarge the outer bound from what it is for 𝖤={K,ϕ} when Y_i ≽ Y_K for all i∈{1,2,⋯ ,K-1}. In fact, the rationale behind this is the following. Unlike the more capable condition, the less noisy condition is a strong order relation. Hence, by considering the class Y_i ≽ Y_K for all i∈{1,2,⋯ ,K-1}, it is assured that the receivers Y_1,Y_2,⋯,Y_K-1 that decode from X can decode whatever message receiver Y_K decodes from U which explains why forcing them to decode the cloud center U is without loss of optimality. 
On the other hand, our converse proof given in <cit.> or in Appendix <ref> does not use the fact that the message encoded in U that is required by Y_K might be also required by any subset of the receivers Y_1,Y_2,⋯,Y_K-1. Hence, for 𝖤={ϕ,K} or 𝖤={K,K}, we get the same outer bound for the class of channels Y_i ≽ Y_K for all i∈{1,2,⋯ ,K-1}. 






§ ACHIEVABLE RATE REGION: TWO NESTED MESSAGES



In this section, we focus on the special case of two nested messages. Let S_1={1, 2, ⋯, P} and S_2= {1, 2, ⋯, P+L} with  P+L=K. Hence, the set of indices of private receivers that demand both messages is S_p ={1,2,⋯,P} and the set of indices of common receivers that demand only the common or multicast message M_S_2 is S_l={P+1, ⋯ , P+L}. It follows from the up-set rate-splitting technique described in Theorem <ref> that the private message is split into at most 2^L parts (depending on the choice of 𝖥) while the common message is not split because it is desired by all receivers. 




Next, we present the inner bound in a more explicit way for the two nested message case than in Theorem <ref>. In particular, the inner bound is presented in terms of the original message rates R_S (where S∈𝖤) and the split message rates R_S→ S^' (S^'∈𝖥) instead of the reconstruction rates as in Theorem <ref>. We are able to do this because of the simplicity afforded by the structure of the nested message set.




Let 𝖥 be any message index superset so that 𝖯⊇𝖥⊇𝖤. A rate pair (R_S_p, R_ϕ) is achievable over the K-user DM BC if 

    R_ϕ+R_S_p   ≤  I(U_𝖶_j^𝖥;Y_j|Q) ∀ j∈ S_p 
    ∑_S∈𝖡  R_S_p→ S   ≤ I(U_𝖡; Y_j|U_𝖶_j^𝖥\𝖡,Q)     𝖡∈ℱ_↓(𝖶_j^𝖥\ϕ),  ∀ j∈ S_p 
    
     R_ϕ+∑_S∈↑_𝖥{ 1 2 ⋯ P.i} R_S_p→ S   ≤ I(U_𝖶_i^𝖥;Y_i|Q)  ∀ i∈ S_l

for some p(q,u_𝖥)=p(q) ∏_S∈𝖥p(u_S|u_↑_𝖥 S\{S},q) and some deterministic function X of the time sharing and auxiliary random variables (Q,U_𝖥).


The proof of this theorem follows from Theorem <ref> when we specialize it to two nested messages. First,  note that since the private message M_S_p is split according to (<ref>), we can simplify the reconstructed message rates in (<ref>) as follows

    R̂_S= R_S_p→ S∀ S∈↑_𝖥 S_p\ϕ
       R̂_ϕ=R_ϕ+R_S_p →ϕ
       R̂_S = 0    S∈𝖥\↑_𝖥 S_p
 
Next, consider the set of inequalities in (<ref>). Note that ℱ_↓(𝖶_j^𝖥) for any j can be written as ℱ_↓(𝖶_j^𝖥\ϕ) ∪𝖶_j^𝖥 because the only down-set that contains ϕ must be 𝖶_j^𝖥. 

Hence, the inequality in (<ref>) simplifies to (<ref>) and (<ref>). On the other hand, for all common receivers Y_i (i∈ S_l), we have ℱ_↓_ϕ(𝖶_i^𝖥)= 𝖶_i^𝖥. However, since the only non-zero reconstruction rates are indexed by ↑_𝖥S_p, we can replace ℱ_↓_ϕ(𝖶_i^𝖥) in (<ref>) by 𝖶_i^𝖥∩↑_𝖥S_p = ↑_𝖥{12 ⋯ P.i} which yields (<ref>). This completes the proof of Theorem <ref>.   




 §.§ Recovering Prior Results from Theorem <ref>


Theorem <ref> can be seen as a generalization of previously proposed achievable schemes in the context of particular examples. These include (a) the two-receiver DM-BC with degraded messages in which superposition coding alone (without rate-splitting) is sufficient to achieve the capacity region as was shown in the important work of Korner and Marton in <cit.> (b) the three-receiver DM-BC with two nested messages with one and two common receivers which was investigated in-depth in <cit.> and (c) the DM-BC with two nested messages for an arbitrary number of receivers and with an arbitrary number of common receivers studied by the authors in <cit.>. In particular, the achievable rate regions based on rate-splitting and superposition coding obtained in the aforementioned papers can be obtained by specific choices of 𝖥. Those rate regions were shown in those works to be the capacity regions for certain classes of channels. In this section, we briefly describe those regions from the lens of Theorem <ref> and also specify the conditions on the DM-BC for which they yield the capacity region. This allows us to not only place known results in the general framework of Theorem <ref> but also to show how further improvements may be possible in DM-BCs for which the capacity region is not yet known.











Consider the case of K=2 and two degraded messages so that 𝖤={1,12}. Let us choose 𝖥=𝖤 and X=U_1 and Q to be an uninformative constant in Theorem <ref>. We get that that a rate pair (R_1, R_12) is achievable if there exist non-negative split rates with R_1= R_1 → 1 + R_1→ 12 such that the following inequalities hold

    R_12+R_1≤   I(X;Y_1)
    
    
    R_1 → 1≤   I(X;Y_1|U_12) 
    
    R_12+R_1→ 12≤   I(U_12;Y_2)

for some p(u_12)p(x|u_12). It was shown that the above region is the capacity region for K=2 with two nested messages in <cit.> without any channel restrictions. Note that even rate splitting is not necessary in this case.




Consider the three-receiver case with the message index set 𝖤={12,123}. We choose 𝖥=𝖤 and X=U_12 and Q= const in Theorem <ref> which then implies that a rate pair (R_12, R_123) is achievable if there exist non-negative split rates with R_12= R_12 → 12 + R_12→ 123 such that the following inequalities hold

    R_123+R_12   ≤min{I(X;Y_1),I(X;Y_2)}
    
    R_12 → 12   ≤min{I(X;Y_1|U_123), I(X;Y_2|U_123)}
    
    R_123+R_12→ 123   ≤ I(U_123;Y_3)
 
for some p(u_123)p(x|u_123). Projecting away the split rates yields that rate pairs for which

    R_123+R_12   ≤min{I(X;Y_1),I(X;Y_2)}
    
    R_123+ R_12   ≤min{I(X;Y_1|U_123), I(X;Y_2|U_123)}+ I(U_123;Y_3) 
    
    R_123   ≤ I(U_123;Y_3)

for some p(u_123)p(x|u_123) are achievable. This region is identical to that given in <cit.> (as it should be, since our general scheme reduces to that of <cit.> with the choices 𝖥=𝖤 and X=U_12 and Q= const). Notably, the above region was shown to be the capacity region when Y_1≽ Y_3 and Y_2≽ Y_3 in <cit.> [There is a typo in the statement of Proposition 11 of <cit.>. The conditions stated therein Y_1 ≽  Y_2 and Y_3 ≽  Y_2 should be Y_2≽ Y_3 and Y_1≽  Y_3. The correct conditions are stated in the proof of the proposition.]. 





Here, we 
consider K=3 and 𝖤={1,123}. We choose 𝖥={1,13,123} and X=U_1 and Q= const. From Theorem <ref>, we obtain inequalities that involve split rates. Using FME to eliminate the split rates we have that rate pairs (R_2, R_123) are achievable provided 









    R_123   ≤min{I(U_13;Y_3),I(U_123;Y_2)}
     
    R_123+R_1    ≤min{  I(X;Y_1), I(X;Y_1|U_13)+I(U_13;Y_3), I(X;Y_1|U_123)+I(U_123;Y_2)}

for some p(u_123)p(u_13|u_123)p(x|u_13).
This region is identical to that given in <cit.> since our scheme for this example and choice of 𝖥={1,13,123} and X=U_1 becomes that of <cit.>. Also, in <cit.>, this region was shown to be capacity region when Y_1≽ Y_2.  




Consider the four-receiver case with the message index set 𝖤={1,1234}.  By choosing 𝖥={1,12,123,1234} and Q= const, we get from Theorem <ref> that the set of rates satisfying

    R_1234+R_1   ≤ I(X;Y_1)
     
    R_1→ 1   ≤ I(X;Y_1|U_12)
    
    R_1→ 1+R_1→ 12   ≤ I(X;Y_1|U_123)
    
    R_1→ 123+R_1→ 12+R_1→ 1   ≤ I(X;Y_1|U_1234)
    
    R_123+R_1→ 12+R_1→ 123+R_1→ 1234   ≤ I(U_12;Y_2) 
    
    R_123+R_1→ 123+R_1→ 1234   ≤ I(U_123;Y_3)
    
    R_123+R_1→ 1234   ≤ I(U_1234;Y_4)

for some p(u_1234) p(u_123|u_1234) p(u_12|u_123)p(x|u_12) is achievable where R_1=R_1→ 1+R_1→ 12+R_1→ 123+R_1→ 1234 and X=U_1. By applying the FME procedure  to eliminate the sub-rates, the obtained polygon is the capacity region for the class of channels Y_1 ≽ Y_3 and Y_1 ≽ Y_4 from the result in <cit.> for K=4. 


In fact, if we choose 𝖥={1,12,123,1234,⋯ ,1234 ⋯ K}, we recover the result in <cit.> for any number of receivers K with any number of common and private receivers. Hence, the result in <cit.> is a special case of the result in Theorem <ref> obtained by a specific choice of 𝖥 but unlike in Theorem <ref> it has a polyhedral description in terms of the two message rates <cit.>.



 §.§ New rate regions from Theorem <ref> for K=3 and 𝖤={1,123}


In the previous section we saw that previous rate regions of <cit.>, <cit.>, and <cit.> can be obtained from Theorem <ref> by choosing 𝖥 accordingly. 
It this section, we show that Theorem <ref> can also produce new rate regions that are potentially larger.
As stated in Remark <ref>, the choice of 𝖥⊇𝖤 determines the achievable region and expanding 𝖥 cannot reduce the rate region. 

Moreover, choosing  𝖥⊃↑_𝖯𝖤 yields some zero reconstruction rates in (<ref>), or equivalently, multiple codebooks for certain groups of sub-messages. 



In particular, Theorem <ref> can produce potentially larger inner bounds
for the message set 𝖤={12,123} than that in Example <ref> (i.e., that in <cit.>) 
and for the message set 𝖤={1,123} than in Example <ref> (i.e., that of
<cit.>). We show this in the latter case in the next example.



Suppose K=3 and 𝖤={1,123}. We choose 𝖥={1,13,23,123} and Q= const. From Theorem <ref>, we can show, after projecting away the split rates using FME,  that the rate tuples that satisfy the inequalities

    R_123   ≤min{I(U_13,U_23;Y_3), I(U_23,U_123;Y_2)}
    
    R_123+R_1   ≤min{ I(U_1,U_13,U_123;Y_1), 
             
    I(U_1;Y_1|U_13,U_123)+I(U_13,U_23;Y_3),
              I(U_1,U_13;Y_1|U_123)+I(U_23,U_123;Y_2) }

for some p(u_123)p(u_23|u_123)p(u_13|u_123)p(u_1|u_13,u_123), and with X is deterministic function of U_𝖥, are achievable. Note that this region subsumes that of Example <ref> since by setting U_1=X and U_23=const., i.e., U_123 U_13 U_1=X, the above region reduces to that in Example <ref>. In other words, choosing X more generally as a deterministic function of U_𝖥 and taking the union over all admissible distribution of U_23 can only enlarge the inner bound compared to that in Example <ref>. In particular, in the rate region of this example U_23 is an extra degree of freedom that receivers Y_2,Y_3 can exploit (cf. the bounds in the inequalities (<ref>), (<ref>)-(<ref>)) which can possibly enlarge the inner bound.   















Suppose again K=3 and 𝖤={1,123}. This time choose 𝖥= ↑_𝖯𝖤={1,12,13,123}, X=U_1 and Q= const. From Theorem <ref>, we can show that the rate pairs that satisfy 

    R_123≤min{I(U_12,U_123;Y_2),I(U_13,U_123;Y_3)}
       R_123+R_1≤min{I(X;Y_1), 
                I(X;Y_1|U_123,U_12)+I(U_12,U_123;Y_2), 
                I(X;Y_1|U_123,U_13)+I(U_13,U_123;Y_3)}
       2R_123+R_1≤ I(X;Y_1|U_12,U_13)+ I(U_12,U_123;Y_2)+I(U_13,U_123;Y_3)
       2R_123+2R_1≤ I(X;Y_1|U_12,U_13)+  I(X;Y_1|U_123)+
    
                    I(U_12,U_123;Y_2)+I(U_13,U_123;Y_3)
 
for some p(u_123)p(u_12|u_123)p(u_13|u_123)p(x|u_12,u_13) are achievable. It can be shown that the above region is equivalent to that in <cit.> but with no binning. Note that without binning, the second and fifth inequalities in <cit.> become redundant. 









The largest inner bound obtainable from Theorem <ref> is obtained by setting 𝖥=𝖯. In the next example we present the achievable rate region for this choice after FME.



Consider again K=3 and 𝖤={1,123}. 
Choosing 𝖥=𝖯 and Q= const in Theorem <ref>, and after performing FME, it can be shown that the rate pairs that satisfy the inequalities

    R_123≤min{I(U_2,U_12,U_23,U_123;Y_2),I(U_3,U_13,U_23,U_123;Y_3)}
       R_123+R_1≤min{I(U_1,U_12,U_13,U_123;Y_1), 
                I(U_1,U_13;Y_1|U_123,U_12)+I(U_2,U_12,U_23,U_123;Y_2), 
                I(U_1,U_12;Y_1|U_123,U_13)+I(U_3,U_13,U_23,U_123;Y_3)}
       2R_123+R_1≤ I(U_1;Y_1|U_12,U_13)+ I(U_2,U_12,U_23,U_123;Y_2)+I(U_3,U_13,U_23,U_123;Y_3)
       2R_123+2R_1≤ I(U_1;Y_1|U_12,U_13)+  I(U_1,U_12,U_13;Y_1|U_123)+
    
                    I(U_2,U_12,U_23,U_123;Y_2)+I(U_3,U_13,U_23,U_123;Y_3)
 for some p(u_123)p(u_12|u_123)p(u_13|u_123)p(u_23|u_123)p(u_1|u_12,u_13,u_123)p(u_2|u_12,u_23,u_123)p(u_3|u_13,u_23,u_123), with X a deterministic function of U_𝖯, are achievable. By setting U_1=X and setting U_2, U_3 and U_23 to be uninformative constants, the above rate region reduces to that in Example <ref>. But more generally, we  allow X to be a function of U_𝖯 and exploit the additional degrees of freedom U_2, U_3 and U_23 provide to the common receivers so as to likely get an enlarged rate region (this can be almost certainly made to be the case per coding distribution).
Next, we give a detailed account of the encoding and decoding functions associated with the above rate region, which we denote as R(K=3, 𝖤={1,123}, 𝖥=𝖯).










In the coding scheme of Theorem <ref> for the choice 𝖥=𝖯, illustrated in the Hasse diagram of Fig. <ref>, we generate codewords associated with all possible auxiliary random variables U_1,U_2,U_3,U_12,U_13,U_23,U_123 even though M_1 is split using (<ref>) into the four split messages as in Example <ref>. Note that, as was the case
in Example <ref>, the choice of 𝖥=𝖯 yields some reconstruction rates equal to zero 
only this time those rates are R̂_2,  R̂_3 and R̂_23. 




Unlike in Example <ref>,


the message pair (m_123, m_1 → 123) in the present example is assigned two codebooks, namely, the U_123 and U_23 codebooks (with joint distribution p(u_23,u_123)), which can also be thought of as the U_23 codebook being a satellite of the U_123 codebook but with a single satellite codeword per cloud codeword. Similarly (also unlike in the cases of Example <ref>) 
the message triple (m_123, m_1 → 123, m_1 → 13) is assigned two codebooks (the U_13 and U_3 codebooks) with U_13 codebook being a satellite of the cloud codebook U_123 (which is one of the two codebooks for the pair (m_123, m_1 → 123)) and the U_3 codebook being a satellite of the U_13  codebook but with one satellite codeword in the U_3 codebook per one codeword in the U_13 codebook. Moreover, the message triple (m_123, m_1 → 123, m_1 → 12) is also assigned two codebooks (the U_12 and U_2 codebooks) with each being a satellite codebook of one of the two “cloud" codebooks U_123 and U_23 for the message pair (m_123, m_1 → 123), where U_23 is itself a one-satellite-per-cloud satellite of the cloud U_123. 

As for decoding, private receiver 1 must decode both messages. To do this, it decodes the reconstructed message set M_𝖶_1^𝖯 = (M̂_1, M̂_12, M̂_13, M̂_123) which contains all of (M_1, M_123) (and nothing more) based on unique joint typicality of the (U_1, U_12, U_13, U_123) codeword-tuple with the received sequence Y_1,1^n. Common Receiver 2, which needs to only decode the common message M_123, will decode the reconstructed message set M_𝖶_2^𝖯 = (M̂_2, M̂_12, M̂_23, M̂_123) by testing for joint typicality of (U_2, U_12, U_23, U_123) codeword-tuple with the received signal Y_2,1^n, but not uniquely as explained next. Now, note that M̂_2 and M̂_23 are empty messages and M̂_12 = M_1 → 12 and M̂_123 = (M_1 → 123, M_123). Hence, Receiver 2 can decode M_123 by jointly decoding M_𝖶_2^𝖯 by testing for joint typicality of the (U_2, U_12, U_23, U_123 ) codeword-tuple with the received sequence Y_2,1^n (thereby making use of the two double codewords) with just unique decoding of M̂_123 (which is sufficient to decode M_123 uniquely) and non-unique decoding of M̂_12 which contains only a part of M_1 which Receiver 2 is not required to decode. A similar explanation can be given for non-unique decoding at Receiver 3.










 
 











 



 
 
 
  

































 §.§ Explicit polyhedral representation for the inner bound with one and two common receivers



It is important to notice that for any two nested messages when we set 𝖥=𝖯 in Theorem <ref> we get 2^K-1 auxiliary random variables and the private message is split into 2^L parts where L is the number of common receivers. Also, we can rewrite (<ref>) as follows

    ∑_S ∈𝖡R_S_p→ S≤ I(U_↓_𝖶_j^𝖯𝖡;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯𝖡,Q)       ∀𝖡∈ℱ_↓(↑_𝖯S_p\ϕ) , j∈  S_p


For one common receiver, we have S_p =K and S_l ={K}. We specialize Theorem <ref> to get a polyhedral description for the inner bound for this case as follows.


An inner bound of K-user DM BC for two nested messages (M_K,M_ϕ) is the set of rate pairs (R_K,R_ϕ) satisfying

    R_ϕ   ≤ I(U_𝖶_K^𝖯;Y_K|Q) 
    
    R_ϕ+R_K   ≤  I(U_𝖶_j^𝖯;Y_j|Q) ∀ j∈ S_p 
    
    R_ϕ+R_K   ≤ I(U_↓_𝖶_j^𝖯{K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K},Q) + I(U_𝖶_K^𝖯;Y_K|Q)  ∀ j∈ S_p

for some p(q,u_𝖯)= p(q) ∏_S∈𝖯p(u_S|u_↑_𝖯 S\{ S },q) and X as a deterministic function of (Q, U_𝖯).


The proof follows from Theorem <ref> when 𝖥=𝖯. In this case, we only split the private message M_K into two sub-messages M_K→K, M_K→ϕ. By applying FME procedure, we project away the sub-rates and obtain the achievable rate region in the statement of the corollary. 



On the other hand, for two common receivers case, we have S_p ={1,2,⋯,K-2} and S_l ={K-1,K}. In the next corollary, we specialize Theorem <ref> to this case and obtain an explicit polyhedral description for the inner bound.


An inner bound of K-user DM BC for two nested messages (M_K-1.K,M_ϕ) is the set of rate pairs (R_K-1.K,R_ϕ) satisfying

    R_ϕ   ≤ I(U_𝖶_i^𝖯;Y_i|Q)  ∀ i∈ S_l 
    
    R_ϕ+R_K-1.K   ≤  I(U_𝖶_j^𝖯;Y_j|Q) ∀ j∈ S_p 
    
    R_ϕ+R_K-1.K   ≤ I(U_↓_𝖶_j^𝖯{K-1};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K-1},Q)  + I(U_𝖶_K-1^𝖯;Y_K-1|Q) 
    ∀ j∈ S_p 
    
    R_ϕ+R_K-1.K   ≤  I(U_↓_𝖶_j^𝖯{K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K},Q)  + I(U_𝖶_K^𝖯;Y_K|Q) 
    ∀ j∈ S_p 
    
    
    2R_ϕ+R_K-1.K   ≤ I(U_↓_𝖶_j^𝖯{K-1.K};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{K-1.K},Q)+I(U_𝖶_K-1^𝖯;Y_K-1|Q)+ I(U_𝖶_K^𝖯;Y_K|Q)
    ∀ j∈ S_p 
    
    
    2R_ϕ+2R_K-1.K   ≤  
    I(U_↓_𝖶_j_1^𝖯{K-1.K};Y_j_1|U_𝖶_j_1^𝖯\↓_𝖶_j_1^𝖯{K-1.K},Q)
    +
    I(U_↓_𝖶_j_2^𝖯{K-1,K};Y_j_2|U_𝖶_j_2^𝖯\↓_𝖶_j_2^𝖯{K-1,K},Q)
           
    +I(U_𝖶_K-1^𝖯;Y_K-1|Q)  + I(U_𝖶_K^𝖯;Y_K|Q)∀ j_1,j_2∈ S_p

for some p(q, u_𝖯)= p(q) ∏_S∈𝖯p(u_S|u_↑_𝖯 S\{ S },q) and X as a deterministic function of (Q, U_𝖯).


The proof follows from Theorem <ref> when 𝖥=𝖯. We split M_K-1.K into four sub-messages M_K-1.K→K-1.K, M_K-1.K→K, M_K-1.K→K-1, M_K-1.K→ϕ. Then, by using the FME procedure, we project away the sub-rates and obtain an explicit polyhedral description of the achievable rate region in the statement of the corollary.  




















§ CAPACITY REGIONS FOR THE COMBINATION NETWORK



In this section, we establish the capacity region for combination network for each of three different message sets considered in Corollaries <ref>, <ref> and <ref>. Throughout this section, we forgo coded time-sharing by setting Q to be an uninformative constant in those corollaries. In particular, we will consider (a) two messages each required by K-1 receivers, i.e., 𝖤={K,K-1} by specializing Corollary <ref> (b) two nested messages with one common receiver and any number of private receivers, i.e., 𝖤={K,ϕ} by specializing Corollary <ref> and (c) two nested messages with two common receivers and any number of private receivers, i.e., 𝖤={K-1.K,ϕ} by specializing Corollary <ref>. The capacity for each message set is presented separately in different subsections. Note that in each of those corollaries we exploit the full generality of the coding scheme proposed in Theorem <ref> and <ref> by letting 𝖥=𝖯. We will show that the benefit of this generality is that a single distribution suffices to achieve capacity independently of which of the three message sets is considered. In particular, choosing the auxiliary random variables U_S for all S∈𝖯 to be independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S is capacity-achieving in each case. We prove the converses using mainly the submodularity of entropy.    

We define next a function we will use throughout this section. Let the modular function (over all subsets of 𝖯) C_𝖶≜∑_S∈𝖶C_S for any 𝖶⊆𝖯. 




Since the proof of the capacity region for combination networks with different message sets depends on the use of certain general identities, we state them in the following lemma for easy reference. 


The following two identities hold:
























  * For any set S=i_1i_2⋯ i_N ⊂{1,2,⋯, K} and i∈ [1:K] 

    C_𝖶_i^𝖯   = C_↓_𝖶_i^𝖯{i_1,i_2,⋯, i_N} +C_↑_𝖶_i^𝖯{S}
    
    C_𝖶_i^𝖯   = C_↓_𝖶_i^𝖯{S} +C_↑_𝖶_i^𝖯{i_1,i_2,⋯ ,i_N}


  * In the K-receiver combination network where Y_i=V_𝖶_i^𝖯 for all i∈{1,2,⋯,K}, if the random variables U_S for all S∈𝖯 are independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S, then for any 𝖶⊆𝖶_i^𝖯,

    I(U_𝖶;Y_i|U_𝖶_i^𝖯\𝖶,Q)= C_𝖶
 where Q is a time sharing random variable.




The proof of (<ref>) and (<ref>) follows directly from (<ref>)-(<ref>) and (<ref>)-(<ref>), respectively, in Lemma <ref>. In equation (<ref>), let |Q|=1 so that no coded time sharing is used. Then, we get

    I(U_𝖶;Y_i|U_𝖶_i^𝖯\𝖶)   =H(U_𝖶|U_𝖶_i^𝖯\𝖶)-H(U_𝖶|Y_i,U_𝖶_i^𝖯\𝖶)
        = H(U_𝖶|U_𝖶_i^𝖯\𝖶) 
        = ∑_S∈𝖶H(U_S) 
        = ∑_S∈𝖶log_2|𝒱_S| 
        = ∑_S∈𝖶 C_S=C_𝖶

where (<ref>) follows from Y_i=U_𝖶_i^𝖯 since V_S=U_S for all S∈𝖯, (<ref>) from the independence of the auxiliary random variables, and (<ref>) from U_S being uniformly distributed over 𝒱_S where |𝒱_S| =2^C_S.









 §.§ The capacity for 𝖤={K,K-1}




In the following theorem, we establish the capacity region of the K-user combination network for P=K-2, L_1=1, and L_2=1. 


The capacity region of the K-user combination network with two messages M_K,M_K-1 is the set of rate pairs (R_K,R_K-1) satisfying

    R_K-1≤ C_𝖶_K^𝖯
       R_K≤ C_𝖶_K-1^𝖯
       R_K-1+R_K≤ C_𝖶_j^𝖯∀ j ∈  S_p  
       R_K-1+R_K≤ C_↓_𝖶_K-1^𝖯{K}+C_𝖶_K^𝖯
    
    
       2R_K-1+2R_K≤ C_↓_𝖶_j^𝖯{K-1,K} + C_𝖶_K^𝖯 + C_𝖶_K-1^𝖯 j∈  S_p
  

Note that (<ref>) is also equivalent to 
    R_K-1+R_K≤ C_↓_𝖶_K^𝖯{K-1}+C_𝖶_K-1^𝖯


 The inequalities (<ref>)-(<ref>) follow from applying (<ref>) in Lemma <ref> to the inequalities (<ref>)-(<ref>),
(<ref>) for j=K-1, or equivalently, (<ref>) for j=K, and (<ref>) in Corollary <ref>, respectively. On the other hand, when we apply (<ref>) in Lemma <ref> to the inequalities (<ref>) and (<ref>) for j∈ S_p, we obtain the following two redundant inequalities

    R_K-1+R_K≤ C_↓_𝖶_j^𝖯{K}+C_𝖶_K^𝖯 j∈  S_p  
       R_K-1+R_K≤ C_↓_𝖶_j^𝖯{K-1}+C_𝖶_K-1^𝖯 j∈  S_p

In particular, (<ref>) is redundant since for any j∈ S_p, we have 

    C_𝖶_j^𝖯   =C_↓_𝖶_j^𝖯{K}+C_↑_𝖶_j^𝖯{K}
       <C_↓_𝖶_j^𝖯{K}+C_𝖶_K^𝖯

where (<ref>) follows from (<ref>) in Lemma <ref> and (<ref>) from ↑_𝖶_j^𝖯{K}⊂𝖶_K^𝖯. Similarly, (<ref>) is redundant, thereby proving achievability. 

For the converse proof, note that the inequalities (<ref>)-(<ref>) are just cutset bounds. That inequality (<ref>) is an outer bound on the capacity region follows from the following:

    nR_K   =H(M_K)
       = I(M_K;Y_K-1^n,M_K-1)
          +H(M_K|Y_K-1^n,M_K-1)
       = I(M_K;Y_K-1^n|M_K-1)+nϵ_n 
       =H(Y_K-1^n|M_K-1)+nϵ_n
       ≤ H(Y_K^n,Y_K-1^n|M_K-1)+nϵ_n
       = H(Y_K^n,Y_K-1^n,M_K-1)-nR_K-1+nϵ_n
       = H(Y_K^n,Y_K-1^n)+H(M_K-1|Y_K^n,Y_K-1^n)
          -nR_K-1+nϵ_n
       ≤ H(Y_K^n,Y_K-1^n) -nR_K-1+2nϵ_n 
        =H(V_𝖶_K^𝖯^n,V_𝖶_K-1^𝖯^n) -nR_K-1+2nϵ_n 
        =H(V_𝖶_K^𝖯^n)+H(V_𝖶_K-1^𝖯^n)-H(V_↑_𝖶_K-1^𝖯{K}^n) 
          -nR_K-1+2nϵ_n 
       ≤ nC_𝖶_K^𝖯+nC_𝖶_K-1^𝖯-nC_↑_𝖶_K-1^𝖯{K}
          -nR_K-1+2nϵ_n 
        = nC_𝖶_K^𝖯+nC_↓_𝖶_K-1^𝖯{K}
    -nR_K-1+2nϵ_n

where (<ref>) follows from Fano's inequality and independence between messages, (<ref>) from chain rule of entropy, (<ref>) from Fano's inequality, (<ref>) from the fact that Y_i^n=V_𝖶_i^𝖯^n for all i∈[1:K], (<ref>) from the submodularity of entropy where 𝖶_K^𝖯∩𝖶_K-1^𝖯= ↑_𝖶_K-1^𝖯{K}=↑_𝖶_K^𝖯{K-1}, and (<ref>) from the fact that the uniform distribution maximizes entropy. Finally, (<ref>) follows from Lemma <ref> such that C_𝖶_K-1^𝖯= C_↓_𝖶_K-1^𝖯{K}+C_↑_𝖶_K-1^𝖯{K}.


























Lastly, for (<ref>), observe that for all j∈ S_p 

    n(R_K   +R_K-1)=H(M_K)+H(M_K-1)
       ≤ I(M_K;Y_j^n,M_K-1)
         +I(M_K-1;Y_K^n,M_K)+2nϵ_n 
       = I(M_K;Y_j^n|M_K-1)
         +I(M_K-1;Y_K^n|M_K)+2nϵ_n 
       = H(Y_j^n|M_K-1)+H(Y_K^n|M_K)+2nϵ_n 
       ≤ H(Y_j^n|M_K-1)
         +H(Y_K^n,Y_K-1^n|M_K)+2nϵ_n 
       = H(Y_j^n,M_K-1)-nR_K-1+2nϵ_n
         +H(Y_K^n,Y_K-1^n,M_K)-nR_K
       ≤ H(Y_j^n)+H(Y_K^n,Y_K-1^n)
         -nR_K-1-nR_K+4nϵ_n 
       = H(V_𝖶_j^𝖯^n)+H(V_𝖶_K^𝖯^n,V_𝖶_K-1^𝖯^n)
         -nR_K-1-nR_K+4nϵ_n 
       = H(V_𝖶_j^𝖯^n)+H(V_𝖶_K^𝖯^n)+H(V_𝖶_K-1^𝖯^n)
         -H(V_𝖶_K^𝖯^n∩ V_𝖶_K-1^𝖯^n )-nR_K-1
          -nR_K+4nϵ_n 
       ≤ H(V_𝖶_j^𝖯^n)+H(V_𝖶_K^𝖯^n)+H(V_𝖶_K-1^𝖯^n)
         -H(V_𝖶_K^𝖯^n∩ V_𝖶_K-1^𝖯^n ∩ V_𝖶_j^𝖯^n)-nR_K-1
          -nR_K+4nϵ_n 
       = H(V_𝖶_j^𝖯^n)+H(V_𝖶_K^𝖯^n)+H(V_𝖶_K-1^𝖯^n)
         -H(  V_↑_𝖶_j^𝖯{K-1.K}^n)-nR_K-1
          -nR_K+4nϵ_n 
       ≤ nC_𝖶_j^𝖯+nC_𝖶_K^𝖯+nC_𝖶_K-1^𝖯
         -nC_↑_𝖶_j^𝖯{K-1.K}-nR_K-1
          -nR_K+4nϵ_n 
       = nC_↓_𝖶_j^𝖯{K,K-1}+nC_𝖶_K^𝖯+nC_𝖶_K-1^𝖯
         -nR_K-1 -nR_K+4nϵ_n

where (<ref>) follows from Fano's inequality, (<ref>) from independence between messages, (<ref>) from Fano's inequality and chain rule, (<ref>) from Y_i^n=V_𝖶_i^𝖯^n for all i∈[1:K], (<ref>) from the submodularity of entropy, and (<ref>) from the following

    V_𝖶_K^𝖯^n∩ V_𝖶_K-1^𝖯^n ∩ V_𝖶_j^𝖯^n   =↑_𝖯{j.K-1.K}
       = ↑_𝖯{K-1.K}∩𝖶_j^𝖯
       =↑_𝖶_j^𝖯{K-1.K}

Moreover, (<ref>) follows from the fact that the uniform distribution maximizes entropy and (<ref>) from Lemma <ref> from which we have C_𝖶_j^𝖯= C_↓_𝖶_j^𝖯{K,K-1}+ C_↑_𝖶_j^𝖯{K-1. K}. This completes the converse proof of Theorem <ref>.




If we set K= 3 in Theorem <ref>, we get the capacity region for 𝖤={12,13}. It is left to the reader to verify that it is a special case of <cit.> (see also <cit.>) where the capacity region for combination network with general message set 𝖤=𝖯 is established for K=2 and K=3. 



The capacity region of the combination network for K> 3 is not known in general. We consider K=4 with 𝖤 = { 123, 124} in this example. Using Theorem <ref>, the capacity region of the four-receiver combination network for this message set is 

the set of rate pairs (R_123,R_124) satisfying 

    R_124≤ C_4+C_14+C_24+C_34+
                C_124+C_134+C_234+C_1234
       R_123≤ C_3+C_13+C_23+C_34+
                C_123+C_134+C_234+C_1234
       R_123+R_124≤ C_1+C_12+C_13+C_14+
                C_123+C_124+C_134+C_1234
       R_123+R_124≤ C_2+C_12+C_23+C_24+
                C_123+C_124+C_234+C_1234
       R_123+R_124≤ C_3+C_13+C_23+C_123+ 
                 C_4+C_14+C_24+C_34+
                C_124+C_134+C_234+C_1234
       2R_123+2R_124≤ C_1+C_12+C_13+C_14+C_123+C_124 + 
                C_3+C_13+C_23+C_34+
                C_123+C_134+C_234+C_1234+ 
                C_4+C_14+C_24+C_34+
                C_124+C_134+C_234+C_1234
       2R_123+2R_124≤ C_2+C_12+C_23+C_24+C_123+C_124 + 
                C_3+C_13+C_23+C_34+
                C_123+C_134+C_234+C_1234+ 
                C_4+C_14+C_24+C_34+
                C_124+C_134+C_234+C_1234
  
















 §.§ Recovering the capacity regions for 𝖤={K,ϕ} and 𝖤={K-1.K,ϕ} of <cit.> via Theorem <ref> 




We recover the capacity regions of the combination network with two nested messages for the one and two common receivers cases next. These results were first obtained in <cit.>. While in <cit.> achievability was shown using rate-splitting and linear superposition coding tailored to the combination network we show it using a top-down approach by specializing Corollaries <ref> and <ref> on the DM BC to the combination network, which is indicative of the strength of the inner bound of Theorem <ref> on the DM BC (from which Corollaries <ref> and <ref> were obtained using FME). These regions can be shown to coincide with those obtained in <cit.> where they were shown to be the capacity regions. We provide the proof of converses here as well for the sake of completeness since the notation here is quite different from that in <cit.>.


The capacity region of the K-user combination network with 𝖤={K,ϕ} is the set of rate pairs (R_K,R_ϕ) satisfying

    R_ϕ   ≤ C_𝖶_K^𝖯
    
    R_ϕ+R_K   ≤ C_𝖶_j^𝖯∀ j∈ [1:K-1]
  
where C_𝖶=∑_S∈𝖶 C_S for any 𝖶⊆𝖯.


The proof of the converse follows from the receiver cutset bounds since the common receiver desires only the common message M_ϕ and the private receivers desire both messages. The proof of achievability follows from using (<ref>) of Lemma <ref> 
in the inequalities (<ref>) and (<ref>) in the achievable region of Corollary <ref>. We show next that the inequality (<ref>) of that region is redundant because of (<ref>). From (<ref>) of Lemma <ref>, we have C_𝖶_j^𝖯= C_↓_𝖶_j^𝖯{K}+C_↑_𝖶_j^𝖯{K } for any j∈ [1:K-1]. Moreover, from the definition of C_𝖶,  we have C_↑_𝖶_j^𝖯{K }<  C_𝖶_K^𝖯. Hence, C_𝖶_j^𝖯< C_↓_𝖶_j^𝖯{K}+ C_𝖶_K^𝖯 for any j∈ [1:K-1] and so (<ref>) is redundant. 





<cit.>

The capacity region of the K-user combination network with 𝖤={K-1.K,ϕ} is the set of rate pairs (R_K-1.K,R_ϕ) satisfying

    R_ϕ   ≤ C_𝖶_i^𝖯∀ i∈  S_l 
    
    R_ϕ+R_K-1.K   ≤ C_𝖶_j^𝖯∀ j∈ S_p 
    
    2R_ϕ + R_K-1.K   ≤ C_↓_𝖶_j^𝖯{K-1.K} + C_𝖶_K-1^𝖯 + C_𝖶_K^𝖯∀ j∈ S_p
  



The three inequalities of (<ref>)-(<ref>) follow from applying (<ref>) of Lemma <ref> to inequalities (<ref>), (<ref>),  and (<ref>) in Corollary <ref>. We next show that the inequalities that result from (<ref>), (<ref>) and (<ref>) will be redundant. 


First, (<ref>) is redundant when j_1= j_2=j∈ [1:K-2] because it is the sum of (<ref>) and (<ref>) due to the modularity of C_𝖶 for any 𝖶⊆𝖯 so that C_↓_𝖶_j^𝖯{K-1}+C_↓_𝖶_j^𝖯{K}= C_↓_𝖶_j^𝖯{K-1, K}+C_↓_𝖶_j^𝖯{K-1.K}. 
While, for j_1≠j_2, (<ref>) is still redundant from (<ref>) since from (<ref>) and (<ref>), we have

    C_𝖶_j_1^𝖯= C_↓_𝖶_j_1^𝖯{K-1,K}+C_↑_𝖶_j_1^𝖯{K-1.K}
    
        C_𝖶_j_2^𝖯=C_↓_𝖶_j_2^𝖯{K-1.K}+C_↑_𝖶_j_2^𝖯{K-1,K}

and C_↑_𝖶_j_1^𝖯{K-1.K}+C_↑_𝖶_j_2^𝖯{K-1,K}≤  C_𝖶_K-1^𝖯+C_𝖶_K^𝖯.

Moreover, we can show that (<ref>) and (<ref>) are redundant because of (<ref>) by following exactly the same argument that we used to show that (<ref>) is redundant because of (<ref>). Hence, (<ref>) is redundant since C_𝖶_j^𝖯< C_↓_𝖶_j^𝖯{K-1}+ C_𝖶_K-1^𝖯 for any j∈ [1:K-2] and (<ref>) is redundant since C_𝖶_j^𝖯< C_↓_𝖶_j^𝖯{K}+ C_𝖶_K^𝖯 for any j∈ [1:K-2].

The inequalities (<ref>) and (<ref>) are cutset outer bounds since the common receivers Y_i (i∈ S_l) desire only the common message M_ϕ and the private receivers Y_j (j∈  S_p) desire both messages. More interestingly, the converse proof of (<ref>) again uses the sub-modularity of entropy as in <cit.>. Assume that the transmission is done over a block of length n. Then, for any j∈  S_p, we have

    nR_K-1.K    = H(M_K-1.K)
         = I(M_K-1.K;Y_j^n,M_ϕ) + H(M_K-1.K|Y_j^n,M_ϕ)
       ≤ I(M_K-1.K;Y_j^n|M_ϕ)+nϵ_n 
         = H(Y_j^n|M_ϕ)+nϵ_n 
       ≤ H(Y_K-1^n,Y_K^n,Y_j^n|M_ϕ)+ nϵ_n
         = H(V_𝖶_K-1^𝖯^n,V_𝖶_K^𝖯^n,V_𝖶_j^𝖯^n|M_ϕ)+nϵ_n 
       ≤ H(V_𝖶_K-1^𝖯^n|M_ϕ)+ H(V_𝖶_K^𝖯^n|M_ϕ)
            + H(V_𝖶_j^𝖯^n|V_𝖶_K-1^𝖯^n,V_𝖶_K^𝖯^n,M_ϕ)+ nϵ_n
         = H(V_𝖶_K-1^𝖯^n,M_ϕ)-nR_ϕ
            + H(V_𝖶_K^𝖯^n,M_ϕ)-nR_ϕ
            + H(V_𝖶_j^𝖯^n|V_𝖶_K-1^𝖯^n,V_𝖶_K^𝖯^n,M_ϕ)+ nϵ_n
       ≤ H(V_𝖶_K-1^𝖯^n)+ H(V_𝖶_K^𝖯^n)-2nR_ϕ
           + H(V_𝖶_j^𝖯^n|V_𝖶_K-1^𝖯^n,V_𝖶_K^𝖯^n,M_ϕ)+ 3nϵ_n 
       ≤ H(V_𝖶_K-1^𝖯^n)+ H(V_𝖶_K^𝖯^n)-2nR_ϕ
                + H(V_𝖶_j^𝖯^n|V_𝖶_K-1^𝖯^n,V_𝖶_K^𝖯^n)+ 3nϵ_n
        = H(V_𝖶_K-1^𝖯^n)+ H(V_𝖶_K^𝖯^n)-2nR_ϕ
                + H(V_↓_𝖶_j^𝖯{K-1.K}^n)+ 3nϵ_n
       ≤ nC_𝖶_K-1^𝖯+ nC_𝖶_K-1^𝖯 + nC_↓_𝖶_j^𝖯{K-1.K}
               -2nR_ϕ + 3nϵ_n

where (<ref>) follows from Fano's inequality and the independence between the messages, (<ref>) from the chain rule of entropy, (<ref>) from the fact that Y_i^n=V_𝖶_i^𝖯^n for any i∈[1:K], (<ref>) from the submodularity of entropy, (<ref>) from Fano's inequality, (<ref>) from conditioning reduces entropy, (<ref>) from the fact that 𝖶_j^𝖯\{𝖶_K-1^𝖯∪𝖶_K^𝖯}= ↓_𝖶_j^𝖯{K-1.K} for any j∈  S_p, and (<ref>) from the fact that the uniform distribution maximizes entropy. This completes the proof of Proposition <ref>.  




In Theorem <ref>, 
and in Propositions <ref> and <ref>, we prove achievability top-down by specializing random coding in the DM BC to the combination network. This is in contrast to the proof in <cit.> for nested messages which is tailored to the combination network via explicit linear network coding. Also, our descriptions for the rate regions are more stream-lined, thanks to the use of order theory,

as are the proofs of the converses, even though the main ingredient, besides standard information inequalities, in the proof of the converses for Theorem <ref> and Proposition <ref> is the sub-modularity of entropy as it is in <cit.>. 



In this example, we show the importance of choosing the message index superset 𝖥=𝖯 in Theorem <ref> via the example of K=3,L=1, i.e., 𝖤={1,123}. From Proposition <ref>, the capacity region for this case is given by

    R_123   ≤min{C_2+C_12+C_23+C_123,  C_3+C_13+C_23+C_123}
    
    R_123+R_1   ≤ C_1+C_12+C_13+C_123
    
    2R_123+R_1    ≤ C_1+C_2+C_3+C_12+C_13+2C_23+2C_123

Consider next the coding scheme commonly used in the  literature which effectively sets 𝖥=↑_𝖯𝖤

in Theorem <ref>, i.e., 𝖥={1,12,13,123}. It is not hard to show that the achievable rate region is the set of rate pairs 
satisfying

    R_123   ≤min{I(U_12,U_123;Y_2),I(U_13,U_123;Y_3)}
    
    R_123+R_1   ≤min{I(U_1;Y_1), 
                I(U_1;Y_1|U_123,U_12)+I(U_12,U_123;Y_2), 
                I(U_1;Y_1|U_123,U_13)+I(U_13,U_123;Y_3)}
    
    2R_123+R_1   ≤ I(U_1;Y_1|U_12,U_13)+ I(U_12,U_123;Y_2)+I(U_13,U_123;Y_3)
    
    2R_123+2R_1   ≤ I(U_1;Y_1|U_12,U_13)+I(U_1;Y_1|U_123)+
                I(U_12,U_123;Y_2)+I(U_13,U_123;Y_3)
 for some p(u_123)p(u_12|u_123)p(u_13|u_123)p(u_1|u_12,u_13). It can be shown that the above region does not become the capacity region by choosing independent auxiliary random variables with a single distribution for any choice of the channel input component V_S (where S∈𝖯). 

By examining the capacity region in (<ref>)-(<ref>), an intuitive choice for the channel input components V_S (S∈𝖯) and the auxiliary random variables U_S (S∈𝖥) to achieve (<ref>) and (<ref>) is (V_123,V_23)=U_123, (V_2,V_12)=U_12, (V_3,V_13)=U_13, and V_1=U_1 where the auxiliary random variables U_123,U_13,U_12,U_1 are uniform distributions over 𝒱_123×𝒱_23, 𝒱_13×𝒱_3, 𝒱_12×𝒱_2 and 𝒱_1, respectively. For this choice, following the same analysis as in Proposition <ref>, we can show that the rate pairs (R_1, R_123) that satisfy 

    R_123   ≤min{C_2+C_12+C_23+C_123,  C_3+C_13+C_23+C_123}
    
    R_123+R_1   ≤ C_1
    
    2R_123+R_1    ≤ C_1+C_2+C_3+C_12+C_13+2C_23+2C_123

are achievable.
Note that the last inequality is redundant. Obviously, the above region is strictly smaller than the capacity region given in (<ref>)-(<ref>).

A different choice that achieves (<ref>) is V_23=U_123, V_2=U_12, V_3=U_13, and (V_1,V_12,V_13,V_123)=U_1 where the auxiliary random variables U_123,U_13,U_12,U_1 are uniform distributions according to 𝒱_23, 𝒱_3, 𝒱_2 and 𝒱_123×𝒱_13×𝒱_12×𝒱_1, respectively.
For this choice, the rate pairs (R_1, R_123) that satisfy

    R_123   ≤min{C_2+C_23, C_3+C_23}
    
    R_123+R_1    ≤ C_1+C_12+C_13+C_123
    
    2R_123+R_1    ≤ C_1+C_2+C_3+C_12+C_13+2C_23+C_123
 are achievable. Note that the last inequality is redundant and the above region is also strictly smaller than the capacity region.  

In Fig. <ref>, we show that even the convex hull of the union of the two inner bounds, given in (<ref>)-(<ref>) and (<ref>)-(<ref>), is strictly contained in the capacity region. 







Example <ref> illustrates the importance of choosing the message index superset 𝖥=𝖯. Although, this choice adds complexity to the coding scheme, it simplifies the choice of the coding distribution that achieves capacity. In particular, independent auxiliary random variables with uniform distribution are extremal. 

Nevertheless, we show in Section <ref> that choosing 𝖥⊂𝖯 can also achieve the capacity of the combination network, provided 𝖥 is chosen appropriately depending on the message set. Moreover, independent auxiliary random variables with uniform distribution do not suffice. A certain dependency has to be introduced in them. 











 §.§ Other Message Sets

In the three scenarios of Sections <ref> and <ref> for which we were able to establish the capacity region for combination networks, we had a polygonal description for the inner bound by applying FME to project away the split rates. This was possible because in these three cases, there are only up to four split rates under up-set rate splitting. For other choices of message pairs (with K>3) we would have many more split rates which would render FME too tedious or intractable. 
Nevertheless, we suspect that the achievable rate region of Theorem <ref> is large enough to be the capacity of the combination network for other message pairs (such as say nested messages with L≥ 3). 

Moreover, it is likely that our approach leads to the capacity region for combination networks for more than just two messages as well. For instance, it can be shown that by using a similar analysis as in Proposition <ref>, we can establish the capacity region for three degraded messages, i.e., 𝖤={M_ϕ,M_K,M_K-1.K}. Hence, discovering all  message sets (ideally, the message set 𝖤=𝖯) for which our approach leads to the capacity region for the combination network is a topic of future research.  






§ FURTHER EVIDENCE OF THE STRENGTH OF THEOREM <REF> 






In this section, we provide further evidence of the strength of the inner bound of Theorem <ref> by specializing it to the combination network to recover, with a single universal coding distribution, the entire achievable rate region of <cit.>, the latter being obtained via rate-splitting and linear superposition coding in <cit.>. Note that that region further specialized to the cases of one or two common receivers yielded the capacity region for those cases as was shown in <cit.> and we recovered those capacity results in Propositions <ref> and <ref>, with achievability in a top-down manner via Theorem <ref>, in Section <ref>.




Moreover, the authors in <cit.> showed that the achievable region in <cit.>, which is achieved by adding a pre-encoder to the rate-splitting and linear superposition coding scheme of <cit.>, is strictly larger than that of <cit.> through <cit.> with K=6 with three common receivers, i.e., there is an achievable rate pair achieved by <cit.> but not by <cit.>. Moreover, through <cit.> in which K=7 and four common receivers, it was shown that the achievable region in <cit.>, achieved via a block Markov coding scheme, is strictly larger than that in <cit.>. 
In this section, we specialize the rate region of Theorem <ref> to the combination network and
identify the auxiliary random variables that achieve the rate pairs achievable by <cit.> and <cit.> in the key examples <cit.> and <cit.>, respectively. 


We begin by recovering the rate region of <cit.> in the following proposition in a top-down manner via the more general Theorem <ref>.
<cit.>

The rate pair (R_S_p, R_ϕ) is achievable over the K-user combination network if  there exist real numbers R_S_p → S for all S ∈↑_𝖯{S_p} such that the following inequalities are satisfied:

    R_S_p   =∑_S ∈↑_𝖯{S_p} R_S_p → S
    
        R_S_p → S   ≥ 0  ∀ S ∈↑_𝖯{S_p}
    
    
    
        R_ϕ+R_S_p≤  C_𝖶_j^𝖯∀ j∈ S_p 
    
       ∑_S∈𝖡  R_S_p→ S≤ C_𝖡    ∀𝖡∈ℱ_↓(𝖶_j^𝖯\ϕ),  ∀ j∈ S_p  
     
       R_ϕ+∑_S∈↑_𝖯{ 1 2 ⋯ Pi} R_S_p→ S≤ C_𝖶_i^𝖯∀ i∈ S_l
 



From Theorem <ref>, we set 𝖥=𝖯 and choose the random variables U_S for all S∈𝖯 to independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S. For this specific choice, we can apply (<ref>) in Lemma <ref> to Theorem <ref> to get (<ref>) from (<ref>), (<ref>) from (<ref>), and (<ref>) from 
(<ref>).






The region in Proposition <ref> is obtained in <cit.> by rate-splitting of the private message and linear superposition coding scheme where the transmitted signal is obtained by the multiplication of the information symbols vector by the so-called zero-structured matrix <cit.>. Here, Proposition <ref> 
is obtained
by specializing the inner bound on the achievable rate region for the DM BC of Theorem <ref> (which is a union of polytopes over all admissible coding distributions given therein) to the combination network and by restricting the distribution of the auxiliary random variables to be a single distribution. Hence, it is possible that the entire rate region of our coding scheme of Theorem <ref> is much larger than the one given by <cit.>.


We address this important point in Examples <ref> and <ref> to follow.





The authors in <cit.> define Superset Saturated Subsets <cit.>, which is equivalent to up-sets in our notation, to be able to describe the inequality in (<ref>) without using order theory. 

Note that the complement of any down-set is an upset, and hence, (<ref>) can be described using the family of down-sets or the family of upsets. In fact, (<ref>) can be written as 

    R_S_p-∑_S∈𝖡R_S_p→ S≤ C_𝖶_j^𝖯\𝖡 ∀ 𝖡∈ℱ_↑(𝖶_j^𝖯) \𝖶_j^𝖯, ∀ j∈ S_p




Before proceeding to the three common receivers example in <cit.>, we specialize first Theorem <ref> to the three common receiver case in the following corollary. 




An inner bound of K-user DM BC for two nested messages with three common receivers (M_S_p,M_ϕ) where S_p={1,2,⋯,K-3} is the set of rate pairs (R_S_p,R_ϕ) satisfying the following for l_1=K,l_2=K-1,l_3=K-2 and all j ∈ S_p

    R_ϕ+R_S_p→l_2l_3+R_S_p→l_2+R_S_p→l_3+R_S_p→ϕ≤ I(U_𝖶_l_1^𝖯;Y_l_3|Q)
        
       R_ϕ+R_S_p→l_1l_3+R_S_p→l_1+R_S_p→l_3+R_S_p→ϕ≤ I(U_𝖶_l_2^𝖯;Y_l_3|Q)
        
       R_ϕ+R_S_p→l_1l_2+R_S_p→l_1+R_S_p→l_2+R_S_p→ϕ≤ 
        I(U_𝖶_l_3^𝖯;Y_l_3|Q)
        
       R_l_1l_2l_3≤ 
        I(U_↓_𝖶_j^𝖯{l_1l_2l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_2l_3},Q)
        
       R_S_p→l_1l_2l_3+R_S_p→l_1l_2≤ I(U_↓_𝖶_j^𝖯{l_1l_2};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_2},Q)
        
       R_S_p→l_1l_2l_3+R_S_p→l_1l_3≤ I(U_↓_𝖶_j^𝖯{l_1l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_3},Q)
        
       R_S_p→l_1l_2l_3+R_S_p→l_2l_3≤ I(U_↓_𝖶_j^𝖯{l_2l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_2l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3≤ I(U_↓_𝖶_j^𝖯{l_1l_2,l_1l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_2,l_1l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_2l_3≤ I(U_↓_𝖶_j^𝖯{l_1l_2,l_2l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_2,l_2l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3≤ I(U_↓_𝖶_j^𝖯{l_1l_3,l_2l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_3,l_2l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3≤ I(U_↓_𝖶_j^𝖯{l_1l_2,l_1l_3,l_2l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1l_2,l_1l_3,l_2l_3},Q)
        
        R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_1≤ I(U_↓_𝖶_j^𝖯{l_1};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_1≤ I(U_↓_𝖶_j^𝖯{l_1,l_2l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1,l_2l_3},Q)
        
        R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_2l_3
        +R_S_p→l_2≤ I(U_↓_𝖶_j^𝖯{l_2};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_2},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_2≤ I(U_↓_𝖶_j^𝖯{l_2,l_1l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_2,l_1l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_3≤ I(U_↓_𝖶_j^𝖯{l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_3≤ I(U_↓_𝖶_j^𝖯{l_3,l_1l_2};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_3,l_1l_2},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_1
        +R_S_p→l_2≤ I(U_↓_𝖶_j^𝖯{l_1,l_2};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1,l_2},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_1
        +R_S_p→l_3≤ I(U_↓_𝖶_j^𝖯{l_1,l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1,l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_2
        +R_S_p→l_3≤ I(U_↓_𝖶_j^𝖯{l_2,l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_2,l_3},Q)
        
       R_S_p→l_1l_2l_3
        +R_S_p→l_1l_2
        +R_S_p→l_1l_3
        +R_S_p→l_2l_3
        +R_S_p→l_1
        +R_S_p→l_2
        +R_S_p→l_3≤
       
        I(U_↓_𝖶_j^𝖯{l_1,l_2,l_3};Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{l_1, l_2,l_3},Q)
        
       R_ϕ+R_S_p≤ 
        I(U_𝖶_j^𝖯;Y_j|Q)

for some p(q,u_𝖯)= p(q) ∏_S∈𝖯p(u_S|u_↑_𝖯 S\{ S },q) and X as a deterministic function of (Q, U_𝖯) where

    R_S_p→ S   ≥ 0  ∀ S∈↑_𝖯{S_p}
    
    R_S_p   = R_S_p→ϕ+R_S_p→l_1+R_S_p→l_2+R_S_p→l_3+R_S_p→l_1l_2+R_S_p→l_1 l_3+R_S_p→l_2l_3+R_S_p→l_1l_2l_3

    




We obtain the achievable rate region in the statement of the corollary by setting 𝖥=𝖯 in Theorem <ref>. Note that we split the private message M_S_p into eight sub-messages M_S_p→ϕ, M_S_p→l_1, M_S_p→l_2, M_S_p→l_3, M_S_p→l_1l_2, M_S_p→l_1l_3, M_S_p→l_2l_3, M_S_p→l_1l_2l_3 since there are 3 common receivers. Hence, we obtain (<ref>)-(<ref>) from (<ref>), (<ref>)-(<ref>) from (<ref>), and  (<ref>) from (<ref>). 


In the following example, we consider the example in <cit.> wherein it was shown that the rate-splitting and linear coding scheme of <cit.> does not achieve capacity. However, when a linear pre-encoder is used together with that scheme a strictly larger rate region is obtained in <cit.> which achieves capacity in <cit.>. We show that the capacity region of <cit.> can actually be recovered in a top-down fashion from Corollary <ref>, but two distributions of the auxilary random variables are needed.

[Example 2 of <cit.>]

We consider K=6 with three common receivers, i.e., 𝖤={123,123456} where S_p={1,2,3} and S_l={4,5,6}. Moreover, we set C_124=C_135=C_236=1 and C_S=0 for all S∈𝖯\{124,135,236} so that we have only three intermediate nodes. Clearly, for such a connection, the capacity region is a line between the two corner points (R_S_p,R_ϕ)=(2,0) and (R_S_p,R_ϕ)=(0,1). By choosing the random variables U_S for all S∈{124,135,236} to be independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S with |Q|=1 and U_S=const. for S∈𝖯\{124,135,236} in the region given in Corollary <ref>, we get that the rate pair (R_S_p,R_ϕ) is achievable if there exists non-negative numbers R_S_p→ S≥ 0  ∀ S∈↑_𝖯{S_p} with R_S_p= R_S_p→ϕ+R_S_p→6+R_S_p→5+R_S_p→4+R_S_p→56+R_S_p→46+R_S_p→45+R_S_p→456 such that the following inequalities are satisfied:

    R_ϕ+R_S_p→45+R_S_p→5+R_S_p→4+R_S_p→ϕ   ≤ 1
        
    
        R_ϕ+R_S_p→46+R_S_p→6+R_S_p→4+R_S_p→ϕ   ≤ 1 
        
    
        R_ϕ+R_S_p→56+R_S_p→6+R_S_p→5+R_S_p→ϕ   ≤ 1 
        
    
        R_456   ≤ 0 
        
    
        R_S_p→456+R_S_p→56   ≤ 0 
        
    
        R_S_p→456+R_S_p→46   ≤ 0 
        
    
        R_S_p→456+R_S_p→45   ≤ 0 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→45   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→46
        +R_S_p→45   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→6   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6   ≤ 2 
        
    
         R_S_p→456
        +R_S_p→56
        +R_S_p→45
        +R_S_p→5   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→5   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→46
        +R_S_p→45
        +R_S_p→4   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→4   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6
        +R_S_p→5   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6
        +R_S_p→4   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→5
        +R_S_p→4   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6
        +R_S_p→5
        +R_S_p→4   ≤ 2 
        
    
        R_ϕ+R_S_p   ≤ 2

Clearly, for this choice of the auxiliary random variable, the rate pair (R_S_p,R_ϕ)=(0,1) is achievable since the above linear program is feasible. However, the rate pair (R_S_p,R_ϕ)=(2,0) is not achievable. To achieve the rate pair (R_S_p,R_ϕ)=(2,0), we have to set, for instance, R_S_p→46=R_S_p→56=1. By doing so, we see that the above linear program is infeasible due to the inequalities (<ref>), (<ref>), (<ref>), and (<ref>). However, the inequality (<ref>) has a right hand side equal to 1 with left hand side equal 0. This inequality is the reliability condition for the common receiver Y_6. In fact, this common receiver does not benefit from setting U_236=V_236 since it does not have to decode any information. Hence, we have to change the choice of the auxiliary random variable to make the private receivers exploit V_236 to relax the inequalities (<ref>), (<ref>), (<ref>), and (<ref>) and make the linear program feasible. To do so, we choose the auxiliary random variables U_135,U_124,U_123 to be independent and uniformly distributed over 𝒱_135,𝒱_124,𝒱_236, respectively, and set U_135=V_135,U_124=V_124,U_123=V_236 with |Q|=1 and U_S=const. for S∈𝖯\{123,124,135}. With this second choice of the random variable, we get from Corollary <ref> that the rate pair (R_S_p,R_ϕ) is achievable if there exist non-negative numbers R_S_p→ S≥ 0  ∀ S∈↑_𝖯{S_p} with R_S_p= R_S_p→ϕ+R_S_p→6+R_S_p→5+R_S_p→4+R_S_p→56+R_S_p→46+R_S_p→45+R_S_p→456 that satisfy the following inequalities


    R_ϕ+R_S_p→45+R_S_p→5+R_S_p→4+R_S_p→ϕ   ≤ 0
        
    
        R_ϕ+  R_S_p→46+R_S_p→6+R_S_p→4+R_S_p→ϕ   ≤ 1 
        
    
        R_ϕ+R_S_p→56+R_S_p→6+R_S_p→5+R_S_p→ϕ   ≤ 1 
        
    
        R_456   ≤ 0 
        
    
        R_S_p→456+R_S_p→56   ≤ 1 
        
    
        R_S_p→456+R_S_p→46   ≤ 1 
        
    
        R_S_p→456+R_S_p→45   ≤ 0 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→45   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→46
        +R_S_p→45   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→6   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6   ≤ 2 
        
    
         R_S_p→456
        +R_S_p→56
        +R_S_p→45
        +R_S_p→5   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→5   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→46
        +R_S_p→45
        +R_S_p→4   ≤ 1 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→4   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6
        +R_S_p→5   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6
        +R_S_p→4   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→5
        +R_S_p→4   ≤ 2 
        
    
        R_S_p→456
        +R_S_p→56
        +R_S_p→46
        +R_S_p→45
        +R_S_p→6
        +R_S_p→5
        +R_S_p→4   ≤ 2 
        
    
        R_ϕ+R_S_p   ≤ 2

It can be verified that the rate pair (R_S_p,R_ϕ)=(2,0) is now indeed achievable since  R_S_p→46=R_S_p→56=1 satisfy the above inequalities.

Note that this is not the only possible choice of auxiliary random variables. We can set R_S_p→46=R_S_p→45=1 or R_S_p→45=R_S_p→56=1 and change the choice of the random variables accordingly to keep the linear program feasible. 



Since by choosing the random variables U_S for all S∈𝖯 to be independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S with |Q|=1 in Theorem <ref>, we obtain the rate region of <cit.> which is not optimal for more than two common receivers as shown by the above example. 
Unlike in our approach, the right hand side of the linear program in <cit.> (equivalent here to (<ref>)-(<ref>)) is function only of the network connections and hence it cannot be changed to make the linear program feasible as we did in (<ref>)-(<ref>). This is why the authors in <cit.> add a pre-encoder to the linear code to relax the left hand side of the linear program to get <cit.> that allows the value of R_S_p→ S_p to be negative, i.e., relaxing the inequality in (<ref>) to be R_S_p→ S≥ 0  ∀ S∈↑_𝖯{S_p}\{S_p}. However, in our approach, we do not have to change our coding scheme, i.e., superposition coding with up-set rate splitting suffices. We have to just choose suitable auxiliary random variables to achieve the corner point (R_S_p,R_ϕ)=(2,0).


  


In the following example, we consider the same example as in <cit.> where the authors showed that their linear coding scheme even with the pre-encoder cannot achieve the rate pair (R_S_p,R_ϕ)=(3,1) for a network with K=7 and four common receivers. Hence, a block Markov coding scheme was proposed therein to relax the left hand side of the linear program, and consequently, achieve the rate pair  (R_S_p,R_ϕ)=(3,1). However, as suggested by Example <ref>, instead of changing our coding scheme, we might be able to achieve the rate pair under consideration by finding a suitable choice of the auxiliary random variables in Theorem <ref> to achieve this rate pair. This is what we do in the next example.


[Example 4 of <cit.>]

We consider K=7 with four common receivers, i.e., 𝖤={123,1234567} where S_p={1,2,3} and S_l={4,5,6,7}. Moreover, we have only six intermediate nodes, i.e., C_1245=C_1257=C_1346=C_1347=C_2356=C_2367=1 and C_S=0 for all S∈𝖯\{1245,1346,1347,2356,1257,2367}. Let us start by choosing U_S for all S∈𝖯 to be independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S with |Q|=1. Hence, from (<ref>) in Theorem <ref>, assuming that 𝖥=𝖯, we know that we have the following four inequalities in the feasibility problem (with R_S_p= ∑_S∈↑_𝖯{S_p} R_S_p→ S)

    R_ϕ+ R_S_p→ 1234+ R_S_p→ 12347+    R_S_p→ 12346+ R_S_p→ 12345+ R_S_p→5+ R_S_p→6+ R_S_p→7+ R_S_p→ϕ   ≤ 3 
        
    
        R_ϕ+ R_S_p→ 1235+ R_S_p→ 12357+ R_S_p→ 12356+ R_S_p→ 12345+ R_S_p→4+ R_S_p→6+ R_S_p→7+ R_S_p→ϕ   ≤ 3 
        
    
        R_ϕ+ R_S_p→ 1236+ R_S_p→ 12367+ R_S_p→ 12356+ R_S_p→ 12346+ R_S_p→4+ R_S_p→5+ R_S_p→7+ R_S_p→ϕ   ≤ 3 
        
    
        R_ϕ+ R_S_p→ 1237+ R_S_p→ 12367+ R_S_p→ 12357+ R_S_p→ 12347+ R_S_p→4+ R_S_p→5+ R_S_p→6+ R_S_p→ϕ   ≤ 3

To achieve the rate pair  (R_S_p,R_ϕ)=(3,1), we do not need to have 3 on the right hand side of all four inequalities (<ref>)-(<ref>). Here, the private message is split into 16 sub-messages since we have four common receivers. We have to set the sum rate of a subset of these sub-messages equal 3 in a way that allows us to restrict at least one of the above inequalities. Clearly, we cannot set the sum rate of M_S_p→4,M_S_p→5,M_S_p→6,M_S_p→7 to be 3 while the sum rate of each three of them is upper bounded by 2 from (<ref>)-(<ref>). Hence, let set R_S_p→ 12345=R_S_p→ 12347=R_S_p→ 12357=1. This is one possible choice from many other choices. Obviously, for this choice we can restrict the inequality (<ref>), i.e., make its right hand side equal 1 instead of 3. To do so, we set 

    U_1346= V_1346
    
        U_2356= const.
    
        U_2367= const.
 instead of the original choice which was U_S= V_S for S∈{1246,2356,2367}. 
To make sure that all private receivers Y_1,Y_2,Y_3 benefit from this restriction, we set 

    U_1235=V_2356
    
        U_1237=V_2367







We have only three sub-messages with non-zero rates, namely, R_S_p→ 12345=R_S_p→ 12347=R_S_p→ 12357=1 and hence, we have only seven 𝖡's from (<ref>) in Theorem <ref> that give non-redundant inequalities. Thus, the achievable rate region, from Theorem <ref>, is the set of rate pairs (R_123, R_ϕ) satisfying for all j∈ S_p

    R_ϕ+R_123≤  I(U_𝖶_j^𝖯;Y_j|Q)  
        R_123≤ I( U_↓_𝖶_j^𝖯{12345,12347,12357} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12345,12347,12357} )
    
        R_123→ 12345+R_123→ 12347≤ I( U_↓_𝖶_j^𝖯{12345,12347} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12345,12347} )
    
        R_123→ 12345+R_123→ 12357≤ I( U_↓_𝖶_j^𝖯{12345,12357} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12345,12357} )
    
       R_123→ 12347+R_123→ 12357≤ I( U_↓_𝖶_j^𝖯{12347,12357} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12347,12357} )
    
        R_123→ 12345≤ I( U_↓_𝖶_j^𝖯{12345} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12345} )
    
        R_123→ 12347≤ I( U_↓_𝖶_j^𝖯{12347} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12347} )
    
        R_123→ 12357≤ I( U_↓_𝖶_j^𝖯{12357} ;Y_j|U_𝖶_j^𝖯\↓_𝖶_j^𝖯{12357} )
    
       R_ϕ+R_123→ 12345+R_123→ 12347≤  I(U_𝖶_4^𝖯;Y_4|Q) 
    
       R_ϕ+R_123→ 12345+R_123→ 12357≤  I(U_𝖶_5^𝖯;Y_5|Q) 
    
       R_ϕ≤  I(U_𝖶_4^𝖯;Y_6|Q) 
    
       R_ϕ+R_123→ 12347+R_123→ 12357≤  I(U_𝖶_7^𝖯;Y_7|Q) 
    
       R_123=R_123→ 12345+R_123→ 12347+R_123→ 12357

for some p(q,u_𝖯)=p(q) ∏_S∈𝖥p(u_S|u_↑_𝖯 S\{S},q) and some deterministic function X of the time sharing and auxiliary random variables (Q,U_𝖯). Besides (<ref>)-(<ref>), we have to assign V_1245,V_1347,V_1257 to the auxiliary random variable such that all the above inequalities (<ref>)-(<ref>) are satisfied simultaneously for (R_S_p,R_ϕ)=(3,1). We choose the random variables U_12345,U_12347,U_12357,U_1235,U_1237,U_1346 to be independent and uniformly distributed over 𝒱_1245,𝒱_1347,𝒱_1257,𝒱_2356,𝒱_2367,𝒱_1346, respectively, and set 

    U_12345=V_1245
       U_12347=V_1347
       U_12357=V_1257
       U_1235=V_2356
       U_1237=V_2367
       U_1346=V_1346
 
while setting the rest of the auxiliary random variable to const. with |Q|=1. For this particular choice of auxiliary random variables, we can show that the linear program is (<ref>)-(<ref>) is feasible for the rate pair (R_S_p,R_ϕ)=(3,1) with R_S_p→ 12345=R_S_p→ 12347=R_S_p→ 12357=1, and hence, achievable. It is worth noting that there are other choices for the auxiliary random variables that lead to a feasible linear program (<ref>)-(<ref>) for the rate pair (R_S_p,R_ϕ)=(3,1) with R_S_p→ 12345=R_S_p→ 12347=R_S_p→ 12357=1. 












We showed in Example <ref> and <ref> that Theorem <ref> achieves the rate pairs that needed a pre-encoder along with rate-splitting and linear superposition coding <cit.> or the proposed block Markov coding scheme <cit.> in <cit.> by just changing the choice of the auxiliary random variables. We did not have to include any dependency among the auxiliary random variables (which is admissible as seen in the allowable distributions in Theorem <ref>). Note that in Example <ref>, Theorem <ref> achieves a rate pair that is not achieved by <cit.> which is known to be capacity achieving for three common receivers <cit.>. This leads us to conjecture that the achievable region in Theorem <ref> is also capacity achieving for three common receivers. In fact, it might subsume the region obtained from linear coding, i.e., the transmitted signal is a linear combination of the information symbols since the region in Theorem <ref> is the union of feasibility regions over all admissible coding distributions as specified therein.





 Example <ref> is the only example given in <cit.> that shows that block Markov coding might be needed for the more general DM BCs. This was the reason for the authors in <cit.> to have extended their block Markov coding scheme to the general DM BC in <cit.>. However, we showed in Example <ref> that in that example, our coding scheme of Theorem <ref> is enough to achieve the rate pair that needed the block Markov coding scheme of <cit.>. This Example <ref> leaves us with no example that motivates the block Markov coding scheme of <cit.>, leading us to suggest that perhaps the block Markov coding scheme of <cit.> is never needed. To strengthen this suggestion, further work is needed.





§ IS 𝖥=𝖯 NECESSARY?



We have shown that by using a single coding scheme corresponding to 𝖥=𝖯, we can achieve the capacity region of general (asymmetric) combination networks for three different message sets with uniform independent auxiliary random variables and a specification of the channel input via the simple relation V_S=U_S. In this part, we  consider the question of whether the capacity region be can achieved with a simpler coding scheme, i.e., with 𝖥⊂𝖯? The answer to this question, as we show here, is yes. However, both 𝖥, the expanded message set, and the coding distribution (i.e., the distribution of U_𝖥) and the function X(U_𝖥) must be tailored to the message set. We summarize the results of this section next.


For two order-(K-1) messages, the coding scheme of Theorem <ref> associated with 𝖥=↑_𝖯𝖤∪{S_p} is sufficient to achieve capacity. For two nested messages with one and two common receivers, the coding scheme of Theorem <ref> corresponding to 𝖥=𝖤 and 𝖥=↑_𝖯𝖤, respectively, are sufficient to achieve capacity. In particular, we show that these respective smaller 𝖥's can be used to achieve the capacity region provided the distribution of the auxiliary random variables U_𝖥 and the function X(U_𝖥) are chosen accordingly. In particular, a dependent set of auxiliary random variables must be considered. Hence, both the coding scheme and the coding distribution must be tailored to the message set under consideration. 



 §.§ 𝖤={K,ϕ}


For two nested messages with one common receiver, we choose 𝖥=𝖤={K,ϕ}. With this specific choice, we get from Theorem <ref> (with |Q|=1) that the rate pairs

    R_ϕ≤   I(U_ϕ;Y_K) 
    
    R_ϕ+R_K≤   I(U_K;Y_j)  j∈ S_p 
    
    R_ϕ+R_K≤   I(U_K;Y_j|U_ϕ)+ I(U_ϕ;Y_K)  j∈ S_p

for some p(u_ϕ)p(u_K|u_ϕ) are achievable where X is a deterministic function of the auxiliary random variables. Note that the above region is the direct extension of that in <cit.> from K=2 to arbitrary K. To achieve the capacity region of the combination network given by Proposition <ref>, 

we choose U_ϕ to be  uniformly distributed over ∏_S∈𝖶_K^𝖯𝒱_S and U_K to be uniformly distributed over ∏_S∈𝖯𝒱_S where | 𝒱_S|=2^C_S for any S∈𝖯. We set the channel input components V_S for all S∈𝖯 to be independent and uniformly distributed over 𝒱_S where V_𝖶_K^𝖯=U_ϕ and V_𝖯=U_K. It is clear that for this specific choice of the channel input components V_S, we have 
    H(V_𝖶)=C_𝖶
 for any 𝖶⊆𝖯 since the channel input components V_S are independent and uniform distributed over 𝒱_S.

Next, we compute the bounds in (<ref>)-(<ref>).
Following a similar analysis as in Proposition <ref>, we have 
    I(U_ϕ;Y_K) =C_𝖶_K^𝖯
 and for each j ∈ S_p we have

    I(U_K;Y_j)    =H(Y_j)
       =H(V_𝖶_j^𝖯)
       = C_W_j^𝖯

where (<ref>) follows directly from (<ref>). Hence, substituting (<ref>) and (<ref>) into (<ref>) and (<ref>), we obtain the capacity region given in Proposition <ref>. Moreover, we show that (<ref>) is redundant because for all j ∈ S_p

    I(U_K;Y_j|U_ϕ)   =H(Y_j|U_ϕ) 
       =H(V_𝖶_j^𝖯|V_𝖶_K^𝖯)
       =H(V_𝖶_j^𝖯\𝖶_K^𝖯|V_𝖶_K^𝖯)
       =H(V_↓_𝖶_j^𝖯{K}) 
       = C_↓_𝖶_j^𝖯{K}

where (<ref>) follows from that fact that Y_j=V_𝖶_j^𝖯 and U_ϕ=V_𝖶_K^𝖯, (<ref>) from 
 𝖶_j^𝖯\𝖶_K^𝖯= ↓_𝖶_j^𝖯{K} and the independence among the channel input components, and (<ref>) from (<ref>). Note that for any j ∈ S_p

    C_𝖶_j^𝖯   = C_↓_𝖶_j^𝖯{K}+ C_↑_𝖶_j^𝖯{K}
       ≤ C_↓_𝖶_j^𝖯{K}+C_𝖶_K^𝖯

where (<ref>) follows from Lemma <ref> when S=K and (<ref>) from ↑_𝖶_j^𝖯{K}⊆𝖶_K^𝖯. The last inequality proves the redundancy of (<ref>). 




 §.§ 𝖤={ϕ,K-1.K}



For two common receivers, i.e., 𝖤={ϕ,K-1.K}, we choose 𝖥=↑_𝖯𝖤={ϕ,K,K-1,K-1.K}. Hence, from Theorem <ref> (setting |Q|=1), we can show that for j∈ S_p the set of rate pairs (R_ϕ,R_K-1.K) satisfying 

    R_ϕ   ≤min{I(U_K,U_ϕ;Y_K-1),I(U_K-1,U_ϕ;Y_K)}
    
    R_ϕ+R_K-1.K   ≤min{I(U_K-1.K;Y_j), 
                I(U_K-1.K;Y_j|U_ϕ,U_K)+I(U_K,U_ϕ;Y_K-1), 
                I(U_K-1.K;Y_j|U_ϕ,U_K-1)+I(U_K-1,U_ϕ;Y_K)}
    
    2R_ϕ+R_K-1.K   ≤ I(U_K-1.K;Y_j|U_K,U_K-1)+
                I(U_K,U_ϕ;Y_K-1)+I(U_K-1,U_ϕ;Y_K)
    
    2R_ϕ+2R_K-1.K   ≤ I(U_K-1.K;Y_j|U_K,U_K-1)+  I(U_K-1.K;Y_j|U_ϕ)+
                I(U_K,U_ϕ;Y_K-1)+I(U_K-1,U_ϕ;Y_K)
 for some p(u_ϕ)p(u_K|u_ϕ)p(u_K-1|u_ϕ)p(u_K-1.K|u_K,u_K-1) and with X a deterministic function U_𝖥, is achievable. The above region is the extension of the region in <cit.> without binning from K=3,L=2 to arbitrary K with two common receivers. In fact, as we mentioned before, the above region, with K=3,L=2, was shown in <cit.> to be the capacity region when Y_1 is less noisy than Y_2 or Y_3. Here, we show that the above region is the capacity region for general combination networks with two common receivers and arbitrary K. 
We choose the dependent auxiliary random variables U_ϕ, U_K, U_K-1, and  U_K-1.K to be uniformly distributed over ∏_S∈↑_𝖶_K-1^𝖯{K}𝒱_S, ∏_S∈𝖶_K-1^𝖯𝒱_S, and ∏_S∈𝖶_K^𝖯𝒱_S, and ∏_S∈𝖯𝒱_S,  respectively. On the other hand, we set the channel input components V_S for all S∈𝖯 to be independent and uniformly distributed over 𝒱_S where 

    V_↑_𝖶_K^𝖯{K-1}=V_↑_𝖶_K-1^𝖯{K}=U_ϕ
       V_↑_𝖶_K-1^𝖯{K} , V_↓_𝖶_K-1^𝖯{K}=V_𝖶_K-1^𝖯=U_K
       V_↑_𝖶_K^𝖯{K-1} , V_↓_𝖶_K^𝖯{K-1}= V_𝖶_K^𝖯=U_K-1
       V_𝖯=U_K-1.K
 Note that the first equality in (<ref>) follows from the fact that ↑_𝖶_K-1^𝖯{K}=↑_𝖶_K^𝖯{K-1} and that in (<ref>) and (<ref>) directly from (<ref>) and (<ref>).


For this choice of auxiliary random variables and channel input components and following similar analysis as in the one common receiver case, we have

    I(U_K,U_ϕ;Y_K-1)   =C_𝖶_K-1^𝖯
    
    I(U_K-1,U_ϕ;Y_K)   = C_𝖶_K^𝖯
    
    I(U_K-1.K;Y_j)   =C_𝖶_j^𝖯
    
    I(U_K-1.K;Y_j|U_ϕ,U_K)   =C_↓_𝖶_j^𝖯{K-1}
     I(U_K-1.K;Y_j|U_ϕ,U_K-1)=    C_↓_𝖶_j^𝖯{K}
    
    I(U_K-1.K;Y_j|U_ϕ)   =C_↓_𝖶_j^𝖯{K-1, K}
    
    I(U_K-1.K;Y_j|U_K,U_K-1)     = C_↓_𝖶_j^𝖯{K-1.K}




Notice that (<ref>) follows from 

    I(U_K-1.K;Y_j|U_ϕ)   =H(Y_j|U_ϕ)
        = H(V_𝖶_j^𝖯|V_↑_𝖶_K-1^𝖯{K})
       = H(V_𝖶_j^𝖯|V_↑_𝖯{K-1.K})
       = H(V_𝖶_j^𝖯|V_↑_𝖯{K-1.K}∩𝖶_j^𝖯)
       = H(V_𝖶_j^𝖯|V_↑_𝖶_j^𝖯{K-1.K})
       = H(V_𝖶_j^𝖯\↑_𝖶_j^𝖯{K-1.K})
       =H(V_↓_𝖶_j^𝖯{K-1,K})
        = C_↓_𝖶_j^𝖯{K-1,K}

where (<ref>) follows from (<ref>), (<ref>) and (<ref>) from the independence of the channel input components V_S for all S∈𝖯, (<ref>) from (<ref>) and (<ref>). Finally, (<ref>) follows directly from (<ref>). 
 

On the other hand, (<ref>) can be shown as follows. For any j∈ S_p, we have

    I(U_K-1.K;Y_j|U_K,U_K-1)   =H(Y_j|U_K,U_K-1)
        = H(V_𝖶_j^𝖯|V_𝖶_K-1^𝖯,V_𝖶_K^𝖯) 
        = H(V_𝖶_j^𝖯\𝖶_K-1^𝖯∪𝖶_K^𝖯) 
        = H(V_↓_𝖶_j^𝖯{K-1.K})
        = C_↓_𝖶_j^𝖯{K-1.K}
 where (<ref>) follows from the independence of the channel input components V_S for all S∈𝖯, (<ref>) from removing from 𝖶_j^𝖯 all the sets that contain K or K-1, and (<ref>) from (<ref>).   




When we substitute (<ref>)-(<ref>) in (<ref>)-(<ref>), we get an equivalent region to (<ref>)-(<ref>) for the choice of independent auxiliary random variables U_S for all S∈𝖯 uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S. More precisely, the inequality in (<ref>) becomes equivalent to (<ref>), (<ref>) equivalent to (<ref>)-(<ref>), (<ref>) equivalent to (<ref>) and (<ref>) equivalent to (<ref>). Hence, the region in (<ref>)-(<ref>) achieves the capacity region established in Proposition <ref>.





 


 §.§ 𝖤={K,K-1}



For the case two messages each required by K-1 receivers 𝖤={K,K-1}, we set 𝖥=↑_𝖯𝖤∪{S_p}={ϕ,K-1,K,K-1.K}, where S_p=K-1.K. Since we are choosing 𝖥 strictly bigger that ↑_𝖯𝖤, we have one zero reconstruction rate as we mentioned before in Remark <ref>. From Theorem <ref>, the inner bound of K-user DM BC for the message index set 𝖤={K,K-1} is the set of rate pairs (R_K,R_K-1) satisfying

    R_K-1≤ I(U_K-1,U_ϕ;Y_K) 
       R_K≤  I(U_K,U_ϕ;Y_K-1)
       R_K-1+R_K≤ I(U_K-1.K;Y_j)
    
       R_K-1+R_K≤ I(U_K-1.K;Y_j|U_ϕ,U_K)+I(U_K,U_ϕ;Y_K-1) 
    
       R_K-1+R_K≤ I(U_K-1.K;Y_j|U_ϕ,U_K-1)+I(U_K-1,U_ϕ;Y_K)
    
       R_K-1+R_K≤ I(U_K;Y_K-1|U_ϕ)+I(U_K-1,U_ϕ;Y_K)
    
       R_K-1+R_K≤ I(U_K-1;Y_K|U_ϕ)+I(U_K,U_ϕ;Y_K-1)  
       2R_K-1+2R_K≤   I(U_K-1.K;Y_j|U_ϕ)+ I(U_K,U_ϕ;Y_K-1)+I(U_K-1,U_ϕ;Y_K)
 for all j∈ S_p and some p(u_ϕ) p(u_K|u_ϕ) p(u_K-1|u_ϕ) p(u_K-1.K|u_K,u_K-1) and X a deterministic function of U_𝖥 is achievable. To achieve the capacity given in Theorem <ref>, we choose the auxiliary random variables and the channel input components exactly as in the two common receivers case. Hence, the equalities in (<ref>)-(<ref>) hold. Moreover, we have 

    I(U_K;Y_K-1|U_ϕ)   =H(Y_K-1|U_ϕ)
       =H(V_𝖶_K-1^𝖯|V_↑_𝖶_K-1^𝖯{K})
       = H(V_𝖶_K-1^𝖯\↑_𝖶_K-1^𝖯{K})
       = H(V_↓_𝖶_K-1^𝖯{K})
       = C_↓_𝖶_K-1^𝖯{K}
 where (<ref>) follows from (<ref>), (<ref>) from all channel input components are independent, (<ref>) from (<ref>) and (<ref>), and (<ref>) from (<ref>).

Similarly, we can show that 
    I(U_K-1;Y_K|U_ϕ)=C_↓_𝖶_K^𝖯{K-1}


By substituting (<ref>)-(<ref>), (<ref>), (<ref>), and (<ref>), in the region (<ref>)-(<ref>), we get exactly equivalent region to the one obtained from (<ref>)-(<ref>), when the auxiliary random variables U_S for all S∈𝖯 are chosen to be independent and uniformly distributed over 𝒱_S where |𝒱_S|=2^C_S and V_S=U_S, which is the capacity region of the combination network given in Theorem <ref>. More precisely, the inequalities (<ref>)-(<ref>) and (<ref>) become equivalent to (<ref>)-(<ref>) and (<ref>). Also, (<ref>) and (<ref>) become equivalent to (<ref>). Finally, (<ref>) and (<ref>) become equivalent to (<ref>).


The most commonly used coding scheme for DM BCs for any message index set 𝖤 is the one corresponding to 𝖥= ↑_𝖯𝖤. If we restrict ourselves here to this kind of coding scheme, it is unclear how we can find the optimal distribution for the auxiliary random variables to achieve the capacity region for general combination networks with 𝖤={K,K-1}. However, with a slight increase in the complexity of the coding scheme, i.e., setting 𝖥=↑_𝖯𝖤∪{S_p}, we were able to identify the optimal distribution for the auxiliary random variables.



In this section, we showed that there is a trade-off between the complexity of the coding scheme by changing 𝖥 and that of the distribution of the auxiliary random variables and the encoding function that must be chosen to achieve the capacity region in three scenarios. We needed to consider dependent auxiliary random variables when we choose 𝖥⊂𝖯 while independent auxiliary random variables were enough when 𝖥=𝖯 as in Theorem <ref> and Propositions <ref>, and <ref>. It is interesting to ask if it is always true that using the most complex coding scheme by setting 𝖥=𝖯 compensates for the need for dependent auxiliary random variables? This is possible to be true depending on Theorem <ref> and Propositions <ref>, and <ref> and Examples <ref> and <ref>. If this is true, then finding the optimal distribution for the auxiliary random variables to achieve a corner point is the capacity region could be much simpler than finding it over all admissible dependent distributions for the auxiliary random variables. This question needs further investigation.     




§ CONCLUSION



In this paper, we propose a novel and general achievable scheme for the K-receiver DM BC with two groupcast messages that involves new twists and generalizations of the techniques of message splitting, superposition coding and indirect decoding. The language of order theory is used to describe it succinctly and to characterize its achievable rate region. To demonstrate the efficacy of this scheme we obtain its specialization to the combination network and show that in the three special cases of (a) nested messages with one common receiver, (b) nested messages with two common receivers and (c) with two messages each required by K-1 receivers the proposed achievable rate region coincides with the capacity region. In particular, the descriptions of the capacity regions are given as explicit polygons that reveals their combinatorial structure.

It remains to be seen if Theorem <ref>, when specialized to the K-user combination network, yields its capacity region for any two nested groupcast messages. More generally, we are curious to know if Theorem <ref> might yield the capacity region of the combination network for any two arbitrary groupcast messages. In future work, it is also of interest to generalize the results of this work in the direction of expanding message sets to contain more than two messages.







§ PROOF OF (<REF>) AND (<REF>) IN LEMMA <REF> 


For any set S=i_1i_2⋯ i_N ⊂{1,2,⋯, K} and i∈ [1:K] , we have

    𝖶_i^𝖯   = 𝖶_i^𝖯\↑_𝖶_i^𝖯{S}∪𝖶_i^𝖯∩↑_𝖶_i^𝖯{S}
       = 𝖶_i^𝖯\↑_𝖶_i^𝖯{S}∪↑_𝖶_i^𝖯{S}
       = ↓_𝖶_i^𝖯{1,2,⋯ ,K}\↑_𝖶_i^𝖯{S}∪↑_𝖶_i^𝖯{S}
       = ↓_𝖶_i^𝖯{1,⋯ ,i-1,i+1,⋯, K}\↑_𝖶_i^𝖯{S}∪↑_𝖶_i^𝖯{S}
       = ↓_𝖶_i^𝖯{i_1,i_2,⋯, i_N}\↑_𝖶_i^𝖯{S}∪↑_𝖶_i^𝖯{S}
       = ↓_𝖶_i^𝖯{i_1,i_2,⋯, i_N}∪↑_𝖶_i^𝖯{S}

where (<ref>) follows from ↑_𝖶_i^𝖯{S}⊆𝖶_i^𝖯. For (<ref>), we know that the set 12⋯ K∈↑_𝖶_i^𝖯{S} for any S=i_1i_2⋯ i_N ⊆{1,2,⋯, K}. Also, 𝖶_i^𝖯={12⋯ K}∪↓_𝖶_i^𝖯{1,2,⋯ , K}, in words, this means that 𝖶_i^𝖯 is the union of the down-set of all K sets with cardinality K-1 and the set with cardinality K (i.e, {1,2,⋯, K}). Hence, we can replace 𝖶_i^𝖯 by ↓_𝖶_i^𝖯{1,2,⋯ , K} since 12⋯ K∈↑_𝖶_i^𝖯{S}. Then, (<ref>) follows from the fact that ∪_S∈𝖶↓_𝖶_i^𝖯{S}= ↓_𝖶_i^𝖯{∪_S∈𝖶} for any 𝖶⊆𝖯 and ↓_𝖶_i^𝖯{i}=ϕ. In (<ref>), we remove all the sets in {1, 2,⋯ ,K} that are available in ↑_𝖶_i^𝖯{S} for N<K. Note that we have K sets with cardinality K-1 in 𝖯 and K-N sets with cardinality K-1 contains S=i_1 i_2 ⋯ i_N. Finally, (<ref>) follows from ↓_𝖶_i^𝖯{i_1,i_2,⋯, i_N}∩↑_𝖶_i^𝖯{i_1i_2⋯ i_N}=ϕ. 



In a similar manner, we can prove (<ref>) as follows


    𝖶_i^𝖯   = 𝖶_i^𝖯\↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}∪𝖶_i^𝖯∩↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}
       = ↓_𝖶_i^𝖯{ 123⋯ K}\↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}∪↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}
       = ↓_𝖶_i^𝖯{S}\↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}∪↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}
       = ↓_𝖶_i^𝖯{S}∪↑_𝖶_i^𝖯{i_1,i_2,⋯,i_N}

where (<ref>) from the fact that 𝖶_i^𝖯= ↓_𝖶_i^𝖯{ 123⋯ K}, and (<ref>) from (<ref>) where  ↓_𝖶_i^𝖯{S}∩↑_𝖶_i^𝖯{i_1,i_2,⋯, i_N}=ϕ. 



§ PROOF OF THEOREM <REF> 




Fix 𝖥 (𝖤⊆𝖥⊆𝖯) to be ordered by set inclusion such that S^'≤ S only if S^'⊆ S. For this choice of 𝖥, we do the following: (a) split the messages M_S S∈𝖤 using the up-set splitting technique proposed in <cit.> such that 

    M_S= ( M_S → S^',   S^'∈↑_𝖥 S )

(b) create the reconstruction messages M̂_S S∈𝖥 with rates given in (<ref>) such that 

    M̂_S= ( M_S^'→ S,  S^'∈↓_𝖤S )

and (c) fix the coded time-sharing, auxiliary and input random variables (Q, U_𝖥, X) such that X is a deterministic function of Q, U_𝖥 whose joint distribution is given by 

    p(q, u_𝖥)= p(q) ∏_S∈𝖥p(u_S|u_↑_𝖥,q S\{S },q)





Then, we enumerate the sets in 𝖥 in non-increasing order such that 𝖥={S_i_1,S_i_2,...,S_i_N}, where N=|𝖥|. Generate a random time-sharing sequence q^n according to ∏_o=1^n p_Q(q_i). For each j∈ [1:N] and collection of reconstruction messages m̂_↑_𝖥S_i_j, generate 2^nR̂_S_i_j codewords u_S_i_j^n(m̂_↑_𝖥S_i_j) according to ∏_t=1^n p(u_S_i_j|u_↑_𝖥 S_i_j,q_i). This process can be done for all j from j=1 to j=N. 



Receivers Y_j (j∈  S_p) jointly decode the reconstruction messages M̂_𝖶_j^𝖥 which contain both desired messages (M_S_1,M_S_2). Using the result in <cit.>, we can show that the probability of error vanishes if 

    ∑_S^'∈𝖡R̂_S^'≤ I(U_𝖡; Y_j|U_𝖶_j^𝖥\𝖡,Q)   ∀𝖡∈ℱ_↓(𝖶_j^𝖥),j∈ S_p



On the other hand, the receiver Y_j, with j∈ S_l_1∪ S_l_2, only needs one message M_𝖶_j^𝖤, 
and hence, non-unique decoding can be employed. To analyze the error probabilities and obtain the conditions such that these probabilities vanish in the limit of large block length when non-unique decoding is used, we use the following two steps; (a) obtain the conditions such that the probabilities of error vanish when unique decoding is used, and then (b) remove all the inequalities that contain only the rates of the undesired messages. For part (a), we know that the probability of error vanishes if 

    ∑_S^'∈𝖡R̂_S^'≤ I(U_𝖡; Y_j|U_𝖶_j^𝖥\𝖡,Q)   ∀𝖡∈ℱ_↓(𝖶_j^𝖥),j∈ S_l_1∪ S_l_2

Since each non-private receiver Y_j desires only the message M_𝖶_j^𝖤 
which is part of the reconstruction messages M̂_S with S∈↑_𝖥𝖶_j^𝖤 as shown in (<ref>) and (<ref>). Hence, from (<ref>), we need to remove from 𝖡 all the sets that do not contain ↑_𝖥𝖶_j^𝖤. Since all the sets in  𝖡 are down-sets, then if none of these sets contain 𝖶_j^𝖤, they must also do not contain any of ↑_𝖥𝖶_j^𝖤. Thus, replacing 𝖡∈ℱ_↓(𝖶_j^𝖥) in (<ref>) by 𝖡∈ℱ_↓_{S_1}(𝖶_j^𝖥) for j∈ S_l_1 and 𝖡∈ℱ_↓_{S_2}(𝖶_j^𝖥) for j∈ S_l_2 removes all the inequalities that contain only the rates of the undesired messages. Hence, all receivers can reliably decode their desired messages if (<ref>) and (<ref>) are satisfied. This completes the proof of Theorem <ref>.
















§ PROOF OF THE CONVERSE FOR THEOREM <REF>

   
 The converse proofs in this section use the information inequality of <cit.>, and hence, we state it here for easy reference.


Let X  (Y,Z) be a DM BC without feedback and Y  ≽   Z. Consider M to be any random variable such that
M X^n  (Y^n,Z^n) forms a Markov chain. Then, we have 
    I(Y^i-1;Z_i|M)≥    I(Z^i-1;Z_i|M)  1≤ i≤ n 
    
    I(Y^i-1;Y_i|M)≥    I(Z^i-1;Y_i|M)  1≤ i≤ n




In this part, we establish the converse proof for only (<ref>)-(<ref>). In particular, we show that for every sequence of (2^nR_K-1, 2^nR_K, n) codes with lim_n →∞ P_e^(n) = 0 the inequalities in (<ref>)-(<ref>) hold for the given classes of channels for some p(u,x) for which U  X  (Y_1,Y_2, ⋯ , Y_K).

For the first class of channels where Y_j  ⊒  Y_K-1⊒ Y_K for all j∈ S_p, we show that the optimal choice of U_i= M_K-1,Y_K-1,1^i-1,Y_K,i+1^n. While for the second class where Y_i ≽ Y_K for all i∈ S_p ∪{K-1}, the optimal choice of U_i=M_K-1 Y_K,1^i-1. 

The converse proof of (<ref>) is straightforward for both classes of channels and hence is omitted. 







For the first class of channels where Y_j  ⊒  Y_K-1⊒ Y_K for all j∈ S_p, the converse proof for (<ref>) depends on Csiszar sum lemma as that in <cit.>, i.e., 

    n (R_K-1 + R_K)     = H(M_K-1)+H(M_K) 
       ≤ I(M_K;Y_K-1^n) + I(M_K ; M_K-1,Y_K^n) +  2n ϵ_n 
     
        = ∑_i=1^n  I(M_K;Y_K-1,i|Y_K-1,i+1^n) + I(M_K-1;Y_K,i|M_K,Y_K,1^i-1)+ 2n ϵ_n
     
       ≤∑_i=1^n I(M_K,Y_K-1,i+1^n;Y_K-1,i) + I(M_K-1;Y_K,i|M_K,Y_K,1^i-1) +2 n ϵ_n 
       ≤∑_i=1^n I(M_K,Y_K,1^i-1,Y_K-1,i+1^n;Y_K-1,i)- I(Y_K,1^i-1;Y_K-1,i|M_K,Y_K-1,i+1^n)  
          + ∑_i=1^n I(M_K-1;Y_K,i|M_K,Y_K,1^i-1,Y_K-1,i+1^n) + I(Y_K-1,i+1^n;Y_K,i|M_K,Y_K,1^i-1) 
    +2 n ϵ_n  
       =  ∑_i=1^n I(M_K,Y_K,1^i-1,Y_K-1,i+1^n;Y_K-1,i)+ I(M_K-1;Y_K,i|M_K,Y_K,1^i-1,Y_K-1,i+1^n)  +2n ϵ_n 
       ≤∑_i=1^n I(W_i;Y_K-1,i)+ I(X_i;Y_K,i|W_i) + 2n ϵ_n 
       ≤∑_i=1^n I(W_i;Y_K-1,i)+ I(X_i;Y_K-1,i|W_i) + 2n ϵ_n 
        = ∑_i=1^n I(X_i;Y_K-1,i) + 2n ϵ_n

where W_i=M_K,Y_K,1^i-1,Y_K-1,i+1^n. The inequality (<ref>) follows from Fano's inequality, (<ref>) from the chain rule for mutual information and the independence between M_K and M_K. Inequality (<ref>) is true since I(W;V) ≤ I(W;V|U)+I(U;V), (<ref>) is due to the Csiszar sum lemma, (<ref>) follows from the fact that M_K-1,M_K,Y_K-1,1^i-1,Y_K,i+1^n  X_i Y_K-1,i forms a Markov chain, and (<ref>) from the condition Y_K-1⊒ Y_K.


While, for the converse of (<ref>), we have 

    n (R_K-1 + R_K)     = H(M_K-1)+H(M_K) 
       ≤ I(M_K-1;Y_K^n) + I(M_K ; M_K-1,Y_K-1^n) +  2n ϵ_n 
     
        = ∑_i=1^n  I(M_K-1;Y_K,i|Y_K,i+1^n) + I(M_K;Y_K-1,i|M_K-1,Y_K-1,1^i-1)+ 2n ϵ_n
     
    
    
    
    
    
    
       ≤∑_i=1^n I(M_K-1,Y_K-1,1^i-1,Y_K,i+1^n;Y_K,i)+ I(M_K;Y_K-1,i|M_K-1,Y_K-1,1^i-1,Y_K,i+1^n)  +2n ϵ_n 
       ≤∑_i=1^n I(U_i;Y_K,i)+ I(X_i;Y_K-1,i|U_i) + 2n ϵ_n

where U_i=M_K-1,Y_K-1,1^i-1,Y_K,i+1^n. The inequality (<ref>) follows from Fano's inequality, (<ref>) from the chain rule for mutual information and the independence between M_K and M_K. Inequality (<ref>) follows from using the Csiszar sum lemma as in (<ref>)-(<ref>).


On the other hand, for the second class where Y_i ≽ Y_K for all i∈ S_p ∪{K-1}, for the converse of (<ref>), we have for any j∈ S_p ∪{K-1}

    n (R_K-1 + R_K)    ≤∑_i=1^n  I(M_K-1;Y_K,i|Y_K,1^i-1) + I(M_K;Y_j,i|M_K-1,Y_j,1^i-1)+ 2n ϵ_n
    
       ≤∑_i=1^n  I(M_K-1, Y_K,1^i-1 ;Y_K,i) + I(M_K, Y_j,1^i-1;Y_j,i|M_K-1)- I( Y_j,1^i-1;Y_j,i|M_K-1) + 2n ϵ_n
     
       ≤∑_i=1^n  I(M_K-1, Y_K,1^i-1 ;Y_K,i) + I(M_K, Y_j,1^i-1;Y_j,i|M_K-1)- I( Y_K,1^i-1;Y_j,i|M_K-1) + 2n ϵ_n
     
       ≤∑_i=1^n  I(M_K-1, Y_K,1^i-1 ;Y_K,i) + I(X_i;Y_j,i|M_K-1)- I( Y_K,1^i-1;Y_j,i|M_K-1) + 2n ϵ_n
     
       ≤∑_i=1^n  I(M_K-1, Y_K,1^i-1 ;Y_K,i) + I(X_i;Y_j,i|M_K-1,Y_K,1^i-1)+ 2n ϵ_n
     
       = ∑_i=1^n  I(U_i ;Y_K,i) + I(X_i;Y_j,i|U_i)+ 2n ϵ_n
 
where (<ref>) follows from the chain rule for mutual information, (<ref>) from Lemma <ref> where Y_j≽ Y_K for all j∈ S_p∪{K-1}, and (<ref>) from the chain rule and the non-negativity of conditional mutual information,



The rest of the proof proceeds along standard lines. Define a time-sharing uniform random variable Q over [1:n] that is independent of all other involved random variables. Identify U=(U_Q,Q) and Y_i=Y_iQ for all i∈ [1:K] and take the limit as n →∞, so that ϵ_n → 0.







IEEEtran


