A relay channel: Markov kernel from joint input (α × α₁) to joint output (β × β₁) (sender input α, relay input α₁, receiver output β, relay observation β₁).

A relay block code of length n with M messages: a sender encoder, a causal relay function (reads past relay observations β₁, emits the next relay input α₁), and a decoder.

The cut-set outer bound in scalar form: the minimum of the broadcast-cut rate Ib = I(X; Y₁, Y | X₁) and the MAC-cut rate Im = I(X, X₁; Y). The outer maximization over joint input pmfs p(x, x₁) is left to callers.

Under a memoryless relay channel (joint input (Xᵢ, X₁ᵢ) to receiver output Yᵢ), the MAC-cut block mutual information I(Xⁿ, X₁ⁿ; Yⁿ) is bounded by the per-letter sum ∑ᵢ I(Xᵢ, X₁ᵢ; Yᵢ). The memoryless structure is a precondition; the inequality (the genuine content) is proven, not assumed. @audit:ok

The broadcast-cut conditional block mutual information I(Xⁿ; Y₁ⁿ, Yⁿ | X₁ⁿ) is bounded by the per-letter sum ∑ᵢ I(Xᵢ; Y₁ᵢ, Yᵢ | X₁ᵢ), under the memoryless relay channel with joint input (Xᵢ, X₁ᵢ) and joint output (Y₁ᵢ, Yᵢ). @audit:ok

The operational outer bound at the MAC cut of a relay channel (Cover–Thomas): for a uniformly distributed message W decoded from the receiver output Yⁿ, the rate is bounded by the per-letter MAC-cut sum plus a Fano slack, log M ≤ ∑ᵢ I(Xᵢ, X₁ᵢ; Yᵢ) + h(Pe) + Pe · log(M - 1), where Pe is the block decoding error probability.

The proof chains destination Fano (shannon_converse_single_shot), the data-processing inequality along the block Markov chain W → (Xⁿ, X₁ⁿ) → Yⁿ (mutualInfo_le_of_markov), and the MAC-cut single-letterization (relay_mac_cut_singleletterize). The Markov and memoryless hypotheses are preconditions (structure / regularity); the per-letter inequality (the genuine content) is proven, not assumed, so neither hypothesis is load-bearing. The outer maximization over joint input pmfs p(x, x₁) — and hence the conversion of the per-letter sum to n · max_p I — is left to callers, which is why the conclusion keeps the explicit per-letter sum. @audit:ok

Message-level telescoping at the broadcast cut of a relay channel (Cover–Thomas): the message–output mutual information I(W; Yⁿ) is bounded directly by the per-letter conditional sum ∑ᵢ I(Xᵢ; Y₁ᵢ, Yᵢ | X₁ᵢ), where Xᵢ = encoder(W)ᵢ is the i-th sender symbol and X₁ᵢ = relay i (Y₁^{<i}) is the i-th relay symbol read causally from the relay's past observations.

The bound cannot be obtained from relay_broadcast_cut_singleletterize (which single-letterizes the block conditional I(Xⁿ; Y₁ⁿ, Yⁿ | X₁ⁿ)), because routing through the block quantity leaves a chain-rule remainder I(W; X₁ⁿ) ≠ 0 (the relay input X₁ⁿ depends causally on W through the feedback). The proof instead telescopes per-letter with the causal conditioner X₁ᵢ:

I(W; Yⁿ) ≤ I(W; (Y₁ⁿ, Yⁿ))                                     -- post-processing
         = ∑ᵢ [H(Vᵢ | V^{<i}) − H(Vᵢ | W, V^{<i})]              -- chain rule, Vᵢ = (Y₁ᵢ, Yᵢ)
         ≤ ∑ᵢ [H(Vᵢ | X₁ᵢ) − H(Vᵢ | Xᵢ, X₁ᵢ)]                  -- per-letter (below)
         = ∑ᵢ I(Xᵢ; Vᵢ | X₁ᵢ).

The per-letter step uses two facts:

• H(Vᵢ | V^{<i}) ≤ H(Vᵢ | X₁ᵢ) — conditioning reduces entropy: X₁ᵢ = relay i (Y₁^{<i}) is a deterministic function of the past pairs V^{<i}, so conditioning on V^{<i} is a refinement of conditioning on X₁ᵢ. Structural, derived (not assumed).
• H(Vᵢ | W, V^{<i}) = H(Vᵢ | Xᵢ, X₁ᵢ) — memorylessness: both Xᵢ = encoder(W)ᵢ (a function of W) and X₁ᵢ (a function of V^{<i}) are deterministic functions of (W, V^{<i}), and given the i-th channel input (Xᵢ, X₁ᵢ) the i-th output Vᵢ is independent of (W, V^{<i}).

The single precondition h_memo is exactly the latter independence, Vᵢ ⫫ (W, V^{<i}) | (Xᵢ, X₁ᵢ), the d-separation property of a memoryless relay channel: the i-th output is conditionally independent of the message and the past output pairs given the i-th channel input. It encodes the channel's memoryless structure, not the conclusion (it is true in the operational setup where Vᵢ is fresh channel noise applied to (Xᵢ, X₁ᵢ)), so it is a regularity precondition, not load-bearing — mirroring the h_memo of bc_input_singleletterize. It is not the false independence W ⫫ X₁ⁿ (which fails for a causal relay): the conditioning here is on the i-th input, not on a fictitious second message. @audit:ok

The operational outer bound at the broadcast cut of a relay channel (Cover–Thomas): for a uniformly distributed message W decoded from the receiver output Yⁿ, the rate is bounded by the per-letter broadcast-cut sum plus a Fano slack, log M ≤ ∑ᵢ I(Xᵢ; Y₁ᵢ, Yᵢ | X₁ᵢ) + h(Pe) + Pe · log(M - 1), where Xᵢ = encoder(W)ᵢ, X₁ᵢ = relay i (Y₁^{<i}), and Pe is the block decoding error probability.

The proof chains destination Fano (shannon_converse_single_shot) with the broadcast-cut message-level telescoping (relay_broadcast_cut_message_telescope). The memoryless d-separation hypothesis is a precondition (channel structure / regularity); the per-letter inequality (the genuine content) is proven, not assumed. The outer maximization over joint input pmfs is left to callers, which is why the conclusion keeps the explicit per-letter sum. @audit:ok

Cut-set outer bound (relay channel, Cover–Thomas): for a uniformly distributed message W decoded from the receiver output Yⁿ, the rate is bounded by the min of the two cut rates, each taken as its per-letter sum plus a common Fano slack:

• the broadcast cut ∑ᵢ I(Xᵢ; Y₁ᵢ, Yᵢ | X₁ᵢ) + h(Pe) + Pe · log(M - 1), and
• the MAC cut ∑ᵢ I(Xᵢ, X₁ᵢ; Yᵢ) + h(Pe) + Pe · log(M - 1),

where Xᵢ = encoder(W)ᵢ, X₁ᵢ = relay i (Y₁^{<i}), and Pe is the block decoding error probability.

The proof combines the two cut bounds (relay_broadcast_cut_outer_bound and relay_mac_cut_outer_bound) via le_min. The memoryless / Markov / causal-relay hypotheses are preconditions (channel structure / regularity); the genuine content is carried by the two single-letterization cut lemmas and is proven, not assumed. The outer maximization over joint input pmfs p(x, x₁) — the textbook n · max_p — is left to callers, which is why the conclusion keeps the explicit per-letter sums. @audit:ok