gpt 6 astra ultra attempt on CS-82

Capacity Region of General 3-Receiver Discrete Memoryless Broadcast Channels

Definitions and mathematical statement

A three-receiver discrete memoryless broadcast channel has finite alphabets and transition law $W(y_1,y_2,y_3\mid x)$. Over $n$ uses, conditional output probabilities factor as the product of these single-use laws. An encoder maps independent messages $(M_1,M_2,M_3)$ to $X^n$, and receiver $i$ estimates $M_i$ from $Y_i^n$. A rate triple is achievable if a sequence of codes has vanishing average probability of decoding error and $n^{-1}\log_2|\mathcal M_i|$ approaching the corresponding rates.

Find a computable single-letter description of the closure of all achievable triples for every such channel, without degradedness assumptions. Single-letter means a finite-dimensional characterization in terms of one channel use and auxiliary variables with effective cardinality bounds, rather than a limit of arbitrary-block coding problems. The standard independent-private-message interpretation is used; adding common messages would require an additional rate specification not given in the record.

Formulation and concept references: [S1].

Short English statement

What computable one-use information formula describes all achievable private-message rates for an arbitrary three-receiver broadcast channel?

Research attempt

Scope and source audit (27 September 2026).

There are three independent private messages, no feedback, and no receiver side information. "Private" specifies the intended decoder; it does not impose secrecy from the other receivers. In particular a valid scheme may let several receivers decode extra messages. Gaussian channels, common-message problems, secrecy regions, and physically degraded special cases are not substitutes for the finite-alphabet target here.

The publisher link [S1] was not retrievable. The authors' archived lecture notes [E1] were inspected as a primary source for the standard broadcast model and coding ingredients; their current arXiv notice identifies the published book as the expanded replacement. Tang--Xie--Wu [E2] provide an inner bound for general private-message broadcast channels with any number of receivers. An inner bound, even in a finite closed form, is not an exact capacity characterization without a matching converse. No inspected source supplies the selected general three-receiver formula.

The attack below derives a computable family of necessary one-use inequalities, proves exact capacity regions for two structured classes, and checks how changing the joint coupling of the receiver noises affects the converse. The last issue is important because the receivers cannot cooperate, whereas many simple converse bounds give them cooperation.

Lemma 458.1: capacity depends only on the three marginals.

Suppose $W$ and $\widetilde W$ have the same channels $W_i(y_i\mid x)$ for $i=1,2,3$, but possibly different joint output laws. Their private-message capacity regions are equal.

Proof. Fix any block encoder and three decoders. For receiver $i$, the distribution of $(M_1,M_2,M_3,Y_i^n)$ depends only on the encoder, the message law, and $\prod_tW_i(y_{it}\mid x_t)$. Its individual error probability is therefore identical under the two joint couplings. If $e_i$ are those probabilities, then \[ \max_i e_i\le\Pr\{\text{at least one decoder errs}\}\le\sum_i e_i. \] Consequently a sequence has vanishing error for one channel exactly when it does for the other. The same codes and rates work in both directions. $\square$

The proof relies on the absence of feedback and receiver cooperation. It does not say that the joint output laws are equal or that a cooperative decoder has the same information in both models. That distinction will produce a concrete test of the naive sum-rate converse below.

Lemma 458.2: a common-input outer bound for every receiver subset.

Every achievable rate triple belongs to the set of nonnegative triples for which some probability distribution $p(x)$ satisfies \begin{equation}\label{wsref-0-61-34-35-38-3a-63-75-74-73} \sum_{i\in S}R_i\le I_p(X;Y_S), \qquad\varnothing\ne S\subseteq\{1,2,3\}, \end{equation} where $Y_S=(Y_i:i\in S)$. The same input distribution must satisfy all seven inequalities.

Proof. Give a joint decoder all the observations $Y_S^n$. It can run the original decoders and recover $M_S$ with error at most the sum of their errors. Independence and uniformity of the messages, followed by Fano's inequality, give \[ \sum_{i\in S}\log_2|\mathcal M_i| \le I(M_S;Y_S^n)+1+e_S\sum_{i\in S}\log_2|\mathcal M_i|. \] Here $e_S\to0$. Rates of a convergent achievable sequence are bounded, so the last two terms divided by $n$ are $o(1)$. The Markov chain $M_S-X^n-Y_S^n$ and memorylessness imply \begin{align*} I(M_S;Y_S^n)&\le I(X^n;Y_S^n)\\ &=H(Y_S^n)-\sum_{t=1}^nH(Y_{S,t}\mid X_t)\\ &\le\sum_{t=1}^n I(X_t;Y_{S,t}). \end{align*} The equality for conditional entropy holds even when the coordinates of $X^n$ are correlated. Let $p_t$ be their single-time distributions. Mutual information for a fixed channel is concave in the input law, because the output entropy is concave and the conditional entropy is linear. Hence the last average is at most $I_{\bar p_n}(X;Y_S)$ for $\bar p_n=n^{-1}\sum_tp_t$. A subsequence of these input laws converges in the finite-dimensional simplex. Continuity of finite-alphabet mutual information gives all seven inequalities for its common limit $p$. $\square$

This is a computable single-letter outer bound with no auxiliaries. It is not proved sufficient. In particular, satisfying three separate inequalities $R_i\le\max_p I_p(X;Y_i)$ does not ensure that their maximizing input laws are compatible or that the messages can share the same channel uses at those rates.

By Lemma 458.1 one may apply (a458:cuts) under every alternative joint coupling having the same three marginals. This gives the further valid outer bound \[ \mathcal C\subseteq \bigcap_{\widetilde W:\ \widetilde W_i=W_i} \bigcup_p\{R\ge0:\ \sum_{i\in S}R_i \le I_{p,\widetilde W}(X;Y_S)\text{ for every }S\}. \] The order of intersection and union is retained: the proof does not permit silently exchanging the quantifiers over coupling and input law. Nor does this expression become an achievability theorem just because each factor is a valid converse.

A complete subcase: identical marginal channels.

Suppose all three output alphabets agree and all three marginal laws are the same channel $V(y\mid x)$. Write $C=\max_p I_p(X;Y)$. Then \begin{equation}\label{wsref-0-61-34-35-38-3a-69-64-65-6e-74-69-63-61-6c} \mathcal C=\{R\ge0:R_1+R_2+R_3\le C\}. \end{equation} The actual joint noises may be independent, identical, or otherwise correlated; only their three marginal laws are assumed identical.

Converse. Replace the joint law by one drawing a single $Y$ from $V$ and giving that same output to all three receivers. Capacity is unchanged by Lemma 458.1. A decoder observing this common sequence can run all three message decoders. The $S=\{1,2,3\}$ inequality is therefore $\sum_iR_i\le I_p(X;Y)\le C$.

Achievability. For a sum rate strictly less than $C$, regard the message triple as one message and use an ordinary point-to-point channel code for $V$. Each receiver applies that same decoder and extracts its own component. Each individual error tends to zero, hence so does the union error. The point-to-point coding theorem used in this step is the standard attributed theorem in [E1]; it is not reproved here. Taking closures gives the boundary.$\square$

For a noiseless alphabet of size $q$, this proof is completely explicit: inject the set of message triples into the $q^n$ possible channel words. Every receiver reads the word and inverts that injection, with zero error. The only rate restriction is $\prod_i|\mathcal M_i|\le q^n$.

An erasure example that tests receiver cooperation.

Take a binary input and let each of receivers 1 and 2 have a binary erasure channel with erasure probability $1/2$; receiver 3 is constant. Consider three couplings of the first two erasures: they are identical, independent, or complementary so that exactly one receiver sees the bit. Each is a valid memoryless broadcast law with the same marginals.

For a uniform input the cooperative informations are respectively \[ I(X;Y_1,Y_2)=\tfrac12,\qquad\tfrac34,\qquad1. \] Indeed a cooperative observer learns the input exactly unless both observations are erased, and the probabilities of that event are $1/2,1/4,0$. Yet all three private-message capacity regions are \[ R_3=0,\qquad R_1+R_2\le\tfrac12, \] by the preceding identical-marginal argument applied to the two active receivers. A sum-rate bound computed from the given complementary coupling alone would allow twice the actual sum capacity. This explicitly refutes sufficiency of that cooperative cut in general. The missing resource is communication between the separate receivers, which the problem does not provide.

The example also checks the interpretation of "private": the scheme achieving the boundary may decode both messages at each receiver, which is permitted. A secrecy requirement would be a different problem.

A second complete subcase: one common and three private bit pipes.

Let the input be $(C,P_1,P_2,P_3)$, where $C$ is a binary string of length $k_0$ and $P_i$ is a binary string of length $k_i$, and let $Y_i=(C,P_i)$ deterministically. The $k_i$ are fixed nonnegative integers. Although the hardware has a common pipe, the information messages remain the three private messages of the statement. The capacity region is \begin{equation}\label{wsref-0-61-34-35-38-3a-70-69-70-65-73} \mathcal C=\left\{R\ge0:\sum_{i=1}^3(R_i-k_i)_+\le k_0\right\}. \end{equation}

Converse. A coalition $S$ observes at most $k_0+\sum_{i\in S}k_i$ bits per use. Lemma 458.2 gives \[ \sum_{i\in S}R_i\le k_0+\sum_{i\in S}k_i \quad(\varnothing\ne S\subseteq\{1,2,3\}). \] The largest left side after subtracting $\sum_{i\in S}k_i$ is the sum of the positive numbers among $R_i-k_i$, unless all are nonpositive, in which case (a458:pipes) is automatic. Thus the subset inequalities imply exactly the displayed condition.

Achievability. Split message $i$ into two independent bit strings at rates $u_i=\min(R_i,k_i)$ and $v_i=(R_i-k_i)_+$. Send its first part through its private pipe and allocate $v_i$ of the common pipe's bits per use to its second part. The condition $\sum_i v_i\le k_0$ permits that allocation. At blocklength $n$, use integer floors of the prescribed bit counts, reserve disjoint positions on the common pipe, and fill unused positions with zeros. Each receiver reads its assigned bits with zero error. The rounding loss is $O(1/n)$ per message. Closure gives all real rates in (a458:pipes).$\square$

This example supplies a genuine three-message code and converse. It also tests overly restrictive time sharing. With $k_0=0$ and $k_1=k_2=k_3=1$, the triple $(1,1,1)$ is achievable simultaneously. Serving just one user per use would incorrectly restrict the sum to one. At the other extreme, $k_0=1$ and $k_1=k_2=k_3=0$ gives the shared-link simplex, not the box of individual capacities. Both extremes must be reproduced by any proposed general formula.

Convexity and the irreducible two-receiver difficulty.

The capacity region is downward closed: restricting a message alphabet and selecting an appropriate subcode, or using zero rate for part of a message, cannot force a higher required rate. It is convex after closure: concatenate two long codes in publicly predetermined time proportions, split each independent message into the corresponding two components, and let each decoder run its two decoders. The error probability is at most the sum of the two block error probabilities, and the rates approach the convex combination. Rational proportions suffice by approximation.

These elementary properties constrain candidates but do not identify one. A particularly strong necessary test is to make receiver 3 constant. Then $R_3=0$, and the $(R_1,R_2)$ slice is exactly the capacity region of the original two-receiver channel: any two-receiver code extends by a one-element third message, while a three-receiver code restricts to its two active decoders. Hence a complete general answer here includes the unrestricted two-receiver private-message problem as a special case. Adding a dummy receiver does not create a new coding theorem for it.

The first gap in the attempted general proof.

One could try to turn all cooperative subset inequalities into a coding scheme. The erasure example shows why the raw version fails. Strengthening the converse by all marginal-preserving couplings repairs that example, but this document has no proof that the strengthened bound is achievable. Its inequalities control what coalitions could decode, whereas the code must permit each designated receiver to decode independently.

Alternatively, introducing auxiliaries and message splitting can produce inner bounds such as [E2]. To answer the selected question one still needs both a matching converse for every channel and effective cardinality bounds for the variables in the final exact formula. A sequence of larger block codes or an unbounded union of auxiliary alphabets is not the requested finite-dimensional characterization. No such reduction is derived from the elementary lemmas above.

Verification and outcome.

The companion script checks the three erasure couplings with exact probabilities, verifies identical marginals and the cooperative information values, and exhaustively compares the subset inequalities with (a458:pipes) on a finite rational rate grid for small pipe lengths. It also encodes and decodes finite bit-pipe messages with disjoint common positions. Those checks test the claimed subcases, not a general capacity region inferred from numerical optimization.

Outcome: UNRESOLVED. Complete capacity characterizations are proved for identical marginal channels and the specified common/private bit-pipe family. Marginal invariance and common-input subset converses are proved for every channel. The missing step is a universally matching coding and converse theorem with effective auxiliary cardinalities.

Sources

• S1 A. El Gamal, Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011. https://doi.org/10.1017/CBO9780511978166. Formulation source.
• E1 Abbas El Gamal and Young-Han Kim, Lecture Notes on Network Information Theory, arXiv:1001.3404v4 $2010$, broadcast-channel and point-to-point chapters; superseded by the book [S1], as the authors' current notice states. https://arxiv.org/pdf/1001.3404v4; https://arxiv.org/abs/1001.3404. Primary author text and replacement notice inspected 27 September 2026.
• E2 Rui Tang, Songjie Xie, and Youlong Wu, On the Achievable Rate Region of the $K$-Receiver Broadcast Channels via Exhaustive Message Splitting, Entropy 23 $2021$, 1408. https://www.mdpi.com/1099-4300/23/11/1408. Primary model, theorem scope, and conclusion inspected 27 September 2026; an achievable region, not a general converse.