Alphabeta Math
ExampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generated
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 Y=X1⊕X2, the independent-private-message capacity region is the triangle R1,R2≥0, R1+R2≤ln⁡2. Independent uniform inputs attain the maximum sum information ln⁡2. A fixed-Q correlated law X1=X2∼Bern⁡(1/2) 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 Q.

Facts & Assumptions

Given: The no-feedback independent-private-message DM-MAC model and the binary XOR kernel.

[F1]

No-feedback independent-private-message DM-MAC code: messages are independent private messages and the encoders are separate message-only maps, so X1i and X2i are independent at each fixed coordinate.

[F2]

Independent-private-message DM-MAC capacity region: the region is the closure of the union over finite Q and conditional product input laws of the three MAC mutual-information inequalities.

[F3]

Finite mutual information: mutual information is the finite KL sum, equivalently I(A;B)=H(B)−H(B∣A) for finite variables.

[F4]

Finite conditional mutual information: conditional mutual information averages the conditional finite-law informations over positive-mass conditioning values.

[F5]

Finite conditional mutual information identities and equality: I(A;B∣C)=H(B∣C)−H(B∣A,C) for finite variables.

[F6]

Finite entropy and mutual-information chain rules: finite information satisfies the chain rule and I(A;B)=H(B)−H(B∣A).

Proof

1.1F1F3F4F5F6algebra

For independent Bernoulli inputs with parameters p,q, given X2 the XOR is a bijective relabeling of X1, and given (X1,X2) the output is fixed. Thus [F4]–[F5] give I(X1;Y∣X2)=H(X1∣X2)=hb(p); interchanging users gives hb(q). The deterministic output and [F3], [F6] give I(X1,X2;Y)=H(Y)=hb(p+q−2pq).

2.1F2step 1.1algebra

For any finite time-sharing variable, the sum bound is I(X1,X2;Y∣Q)=H(Y∣Q)≤ln⁡2, because each conditional output is binary. With Q constant and p=q=1/2, both individual informations and the sum information equal ln⁡2. Hence every nonnegative pair with sum at most ln⁡2 is in the closed region, and no pair with larger sum is.

3.1F1F2F5algebra∎

The diagonal joint law has probability 1/2 on (0,0) and (1,1), so it is not a product law: its marginals are uniform but their product puts positive mass on (0,1) and (1,0). More generally, suppose a finite mixture PQPX1∣QPX2∣Q equals this diagonal law. For every positive-mass q, nonnegativity and zero total off-diagonal mass force P(X1=0∣q)P(X2=1∣q)=P(X1=1∣q)P(X2=0∣q)=0. If X1 had positive conditional mass on both bits, these equalities would force P(X2=0∣q)=P(X2=1∣q)=0, impossible; hence X1 is deterministic given q, and the two equalities then force X2 to be the same deterministic bit. Thus any such public time-sharing representation uses deterministic diagonal product components. With Q selecting (0,0) or (1,1), [F5] gives I(X1;Y∣X2,Q)=I(X2;Y∣X1,Q)=0; 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