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.

Noisy network coding inner bound for finite multicast networks

Statement

Consider a finite DMN as in Finite discrete memoryless networks and causal codes. Let $S$ be a source-node set, let $D$ be a destination-node set, and let each source $k \in S$ send an independent message of rate $R_{k}$ to every destination. For a finite time-sharing variable $Q$ , choose $P_{Q} \prod_{k = 1}^{N} P_{X_{k} ∣ Q} \prod_{k = 1}^{N} P_{{\hat{Y}}_{k} ∣ Y_{k}, X_{k}, Q} .$ For every destination $d \in D$ and every nonempty cut set $A \subseteq [N]$ with $A \cap S \neq \emptyset$ and $d \notin A$ , the noisy-network-coding inner bound is $\sum_{k \in A \cap S} R_{k} < I (X_{A}; Y_{d}, {\hat{Y}}_{A^{c}} ∣ X_{A^{c}}, Q) - I (Y_{A}; {\hat{Y}}_{A} ∣ X_{[N]}, Y_{d}, {\hat{Y}}_{A^{c}}, Q) .$ The closure of the union of these rate tuples, together with the all-zero rate tuple, is achievable; the separate zero tuple is attained by singleton message sets even if some cut expression is negative. A constant reconstruction ${\hat{Y}}_{k}$ is permitted at any node.

Facts & Assumptions

Given: The finite DMN, independent source messages, finite $Q$ , product inputs conditional on $Q$ , and finite local reconstruction kernels in the statement.

[F1]

Finite discrete memoryless networks and causal codes: nodes use causal encoders; destinations know their own messages; achievability uses average error over all required estimates.

[F2]

Likelihood-ratio network coding for finite or Euclidean multicast networks: for finite alphabets the square-integrable local and packing likelihood hypotheses give precisely the displayed cut inner region, with finite coded time sharing, constant reconstructions, closure, and a separate singleton-message zero tuple; its finite assertion uses no choice axiom.

[F3]

Finite conditional mutual information: finite conditional mutual information is the finite conditional-KL average, with the same logarithm convention for rates and informations.

Proof

1.1F2F3givenalgebra

For each positive-probability value of $Q$ , use the target law in the statement. Its alphabets are finite. A target-positive joint atom has positive local marginal-reconstruction probability and positive reference probability for every reference law in [F2], because all its displayed marginal factors are positive. Thus every required likelihood ratio is finite on target support; the finitely many log values are bounded and hence square-integrable. All cut informations are finite. No cost constraint is imposed. These observations verify every hypothesis of the finite branch of [F2], including arbitrary zero-probability letters, which can simply be omitted.

2.1F1F2step 1.1given

Apply [F2] with this law and source/destination sets. Its independent messages, causal encoders and destination side information have exactly the conventions of [F1]. Its cut expression is $I (X_{A}; Y_{d}, {\hat{Y}}_{A^{c}} ∣ X_{A^{c}}, Q) - I (Y_{A}; {\hat{Y}}_{A} ∣ X_{[N]}, Y_{d}, {\hat{Y}}_{A^{c}}, Q)$ for every required $A, d$ , so every tuple satisfying the displayed strict inequalities is achievable. A constant reconstruction is allowed in [F2] and contributes zero local and conditional information.

3.1F1F2step 2.1construct∎

The closure-of-union conclusion follows from [F2], or by choosing a sequence of strict-region laws and rate tuples tending to the claimed point and selecting successively longer codes with error tending to zero and rates tending to that point. Independently, singleton message sets at every source and a destination that returns those unique messages have error exactly zero; this realizes the separate zero tuple even when a cut expression is negative.

Depends on

Used by

Dependency tree · two levels

13 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

Sung Hoon Lim, Young-Han Kim, Abbas El Gamal, and Sae-Young Chung, Noisy Network Coding, IEEE Transactions on Information Theory 57(5), 2011 (standard reference, not scraped)
Abbas El Gamal and Young-Han Kim, Lecture Notes on Network Information Theory, arXiv:1001.3404v4 (standard reference, not scraped)