TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck pending

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Capacity region of a finite two-user interference channel under strong interference

Statement

For the channel and universal strong-interference assumptions of Finite two-user interference channel and strong-interference regime, the capacity region is the closure of the union over finite $Q$ and laws $P_{Q} P_{X_{1} ∣ Q} P_{X_{2} ∣ Q}$ of rate pairs satisfying $R_{1} \leq I (X_{1}; Y_{1} ∣ X_{2}, Q), R_{2} \leq I (X_{2}; Y_{2} ∣ X_{1}, Q),$ $R_{1} + R_{2} \leq \min {I (X_{1}, X_{2}; Y_{1} ∣ Q), I (X_{1}, X_{2}; Y_{2} ∣ Q)} .$

Facts & Assumptions

Given: A finite interference channel satisfying the universal inequalities in [F1].

[F1]

Finite two-user interference channel and strong-interference regime: the two mutual-information orderings hold for every product input law.

[F2]

Strong-interference information inequalities tensorize over product code inputs: these orderings tensorize for independent codeword vectors.

[F3]

Finite-alphabet Fano inequality: decoding with error $P_{e}$ gives conditional message entropy at most $\ln 2 + P_{e} \ln ∣ M ∣$ .

[F4]

Independent-private-message DM-MAC capacity region: for each finite product input law with public time sharing, the no-feedback DM-MAC capacity region has the two individual mutual-information bounds and the joint sum bound; its achievability proof uses independent random codebooks with the stated product law.

[F5]

Finite entropy and mutual-information chain rules: finite entropy chain rules and conditioning identities give the coordinatewise entropy bound in the converse.

Proof

1.1F1F3givenalgebra

For any length- $n$ code, independence of the messages makes the induced vectors $X_{1}^{n}, X_{2}^{n}$ independent. Fano at receiver 1 and the fact that revealing $M_{2}$ cannot reduce mutual information give $n R_{1} \leq I (X_{1}^{n}; Y_{1}^{n} ∣ X_{2}^{n}) + o (n)$ . The analogous receiver-2 bound is $n R_{2} \leq I (X_{2}^{n}; Y_{2}^{n} ∣ X_{1}^{n}) + o (n)$ .

1.2F1F4given

Fix finite $Q$ and product conditional input laws. Apply [F4] to the marginal MAC at receiver 1 and to the marginal MAC at receiver 2. Both uses of [F4] generate the same ensemble of independent sender codebooks, because the input laws and time-sharing sequence are the same; only the two decoders differ. Under the strong-interference inequalities [F1], receiver 2's individual bound for sender 1 is at least receiver 1's intended individual bound, and receiver 1's individual bound for sender 2 is at least receiver 2's intended bound. The intersection of the two MAC regions is therefore exactly the three inequalities in the statement.

2.1F1F2F5step 1.1algebra

For the first individual bound, the finite entropy chain rule [F5] and memorylessness give $I (X_{1}^{n}; Y_{1}^{n} ∣ X_{2}^{n}) = H (Y_{1}^{n} ∣ X_{2}^{n}) - H (Y_{1}^{n} ∣ X_{1}^{n}, X_{2}^{n}) \leq \sum_{i} I (X_{1, i}; Y_{1, i} ∣ X_{2, i}),$ where the first entropy is at most $\sum_{i} H (Y_{1, i} ∣ X_{2, i})$ by the chain rule and conditioning, and the second entropy is exactly $\sum_{i} H (Y_{1, i} ∣ X_{1, i}, X_{2, i})$ by the memoryless channel. The same calculation applies to user 2.

2.2F1F2F3step 1.1algebra

By the block-lift inequality [F2], $I (X_{2}^{n}; Y_{1}^{n} ∣ X_{1}^{n}) \geq I (X_{2}^{n}; Y_{2}^{n} ∣ X_{1}^{n})$ . Since $M_{2}$ is independent of $M_{1}$ , Fano at receiver 2 implies $H (M_{2} ∣ Y_{1}^{n}, M_{1}) = H (M_{2} ∣ M_{1}) - I (M_{2}; Y_{1}^{n} ∣ M_{1}) \leq H (M_{2} ∣ M_{1}) - I (M_{2}; Y_{2}^{n} ∣ M_{1}) = o (n) .$ Fano at receiver 1 gives $H (M_{1} ∣ Y_{1}^{n}) = o (n)$ . Thus $n (R_{1} + R_{2}) \leq I (M_{1}, M_{2}; Y_{1}^{n}) + o (n) \leq I (X_{1}^{n}, X_{2}^{n}; Y_{1}^{n}) + o (n) \leq \sum_{i} I (X_{1, i}, X_{2, i}; Y_{1, i}) + o (n)$ . Exchanging receivers gives the corresponding sum bound at $Y_{2}$ .

3.1step 2.1step 2.2algebra

Let $Q$ be uniform on $[n]$ and let $(X_{1}, X_{2})$ have the time- $Q$ input law; since the message vectors are independent, $P_{X_{1}, X_{2} ∣ Q} = P_{X_{1} ∣ Q} P_{X_{2} ∣ Q}$ . Combining steps 2.1, 2.2 gives the stated inequalities for this $Q$ . Taking limits and closure proves the converse.

4.1F4step 1.2algebra∎

The [F4] random-coding proof gives ensemble-average error tending to zero at each receiver under the strict MAC inequalities. The expected sum of the two receiver errors is at most the sum of those two vanishing bounds, so a deterministic codebook pair exists for which both errors tend to zero. Closure removes strictness and the finite variable $Q$ supplies time sharing.

Depends on

Used by

Outside the strong regime, the MAC intersection can be too small Counterexample
The binary additive interference channel in the strong regime Example

Dependency tree · two levels

17 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Abbas El Gamal and Young-Han Kim, Lecture Notes on Network Information Theory, arXiv:1001.3404v4 (standard reference, not scraped)
M. H. M. Costa and Abbas A. El Gamal, The Capacity Region of the Discrete Memoryless Interference Channel with Strong Interference, IEEE Transactions on Information Theory 33(5), 1987 (standard reference, not scraped)