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 XOR MAC exposes the independent private-input law
Statement
For the deterministic binary XOR channel , the independent-private-message capacity region is the triangle , . Independent uniform inputs attain the maximum sum information . A fixed- correlated law is not a product input law; it can be represented only by mixing deterministic product laws with a public time-sharing variable, and that common variable supplies no private-message rate conditional on .
Facts & Assumptions
Given: The no-feedback independent-private-message DM-MAC model and the binary XOR kernel.
No-feedback independent-private-message DM-MAC code: messages are independent private messages and the encoders are separate message-only maps, so and are independent at each fixed coordinate.
Independent-private-message DM-MAC capacity region: the region is the closure of the union over finite and conditional product input laws of the three MAC mutual-information inequalities.
Finite mutual information: mutual information is the finite KL sum, equivalently for finite variables.
Finite conditional mutual information: conditional mutual information averages the conditional finite-law informations over positive-mass conditioning values.
Finite conditional mutual information identities and equality: for finite variables.
Finite entropy and mutual-information chain rules: finite information satisfies the chain rule and .
Proof
For independent Bernoulli inputs with parameters , given the XOR is a bijective relabeling of , and given the output is fixed. Thus [F4]–[F5] give ; interchanging users gives . The deterministic output and [F3], [F6] give .
For any finite time-sharing variable, the sum bound is , because each conditional output is binary. With constant and , both individual informations and the sum information equal . Hence every nonnegative pair with sum at most is in the closed region, and no pair with larger sum is.
The diagonal joint law has probability on and , so it is not a product law: its marginals are uniform but their product puts positive mass on and . More generally, suppose a finite mixture equals this diagonal law. For every positive-mass , nonnegativity and zero total off-diagonal mass force . If had positive conditional mass on both bits, these equalities would force , impossible; hence is deterministic given , and the two equalities then force to be the same deterministic bit. Thus any such public time-sharing representation uses deterministic diagonal product components. With selecting or , [F5] gives ; the mixture adds no private-message rate.
Depends on
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
16 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, Network Information Theory, Lecture Notes 4, binary additive MAC examples (standard reference, not scraped)
- Thomas M. Cover and Joy A. Thomas, Elements of Information Theory, 2nd ed., Chapter 15, §15.3 (standard reference, not scraped)