ExampleConstruction: AI-adaptedVerification: AI-generatedPipeline-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.

The binary additive interference channel in the strong regime

Example

Let $X_{1} = X_{2} = Y_{1} = Y_{2} = {0, 1}$ and set $Y_{1} = X_{1} \oplus X_{2}, Y_{2} = X_{1} \oplus X_{2},$ where $\oplus$ is addition modulo two. The capacity region is $R_{1} \geq 0, R_{2} \geq 0, R_{1} \leq 1, R_{2} \leq 1, R_{1} + R_{2} \leq 1$ bits per use.

Facts & Assumptions

Given: All information quantities in this example are measured in bits: $I_{2} = I / \ln 2$ and $H_{2} = H / \ln 2$ for the nats-valued supplier conventions. Independent messages sent over the binary channel in the example.

[F1]

Finite two-user interference channel and strong-interference regime: strong interference requires the two conditional mutual-information inequalities for every product input law.

[F2]

Capacity region of a finite two-user interference channel under strong interference: under those universal inequalities, capacity is the intersection of the two multiple-access regions with time sharing.

Proof

1.1F1givenalgebra

For every product input law, conditioning on $X_{2}$ makes both $Y_{1}$ and $Y_{2}$ equal to $X_{1}$ plus the same fixed bit; hence $I_{2} (X_{1}; Y_{1} ∣ X_{2}) = I_{2} (X_{1}; Y_{2} ∣ X_{2})$ . Conditioning on $X_{1}$ gives $I_{2} (X_{2}; Y_{2} ∣ X_{1}) = I_{2} (X_{2}; Y_{1} ∣ X_{1})$ . Thus [F1] holds with equality.

1.2F2givenalgebra

Each receiver's output is one bit, so its multiple-access sum mutual information is at most $H_{2} (Y_{i}) \leq 1$ . Also, given the other input, each user sees a noiseless binary channel, whose mutual information is at most one bit. Therefore the region in [F2] is contained in the stated triangle.

2.1F1F2step 1.2algebra∎

With independent uniform inputs, $Y_{i}$ is uniform, and $I_{2} (X_{1}; Y_{1} ∣ X_{2}) = I_{2} (X_{2}; Y_{2} ∣ X_{1}) = I_{2} (X_{1}, X_{2}; Y_{i}) = 1$ . The MAC intersection contains the two corner points $(1, 0)$ and $(0, 1)$ ; the zero pair is achieved by singleton messages. Time sharing among these three points achieves every nonnegative pair with sum at most one. Together with step 1.2 this proves the capacity region.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

7 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)