Capacity Atlas Channel-capacity problems
Multi-user

General discrete memoryless relay channel

A relay assists communication from a source to a destination. Decode-forward and the cut-set bound do not coincide in general.

Open Lean: not started
01 · Model

Channel specification

Input

\(Source input X and relay input X_r.\)

Output

\(Relay observation Y_r and destination observation Y.\)

Law

A memoryless transition law p(y,y_r\mid x,x_r).

Assumptions

  • The relay acts causally on its past observations.
  • Average probability of error vanishes with blocklength.
02 · Capacity

Shannon capacity

bits per channel use bounds
\[R_{\mathrm{DF}}\le C\le R_{\mathrm{cut}}\]

The bounds coincide for important subclasses, including degraded and reversely degraded relay channels, but not for the general model.

Best lower boundOpen gapBest upper bound
\(R_{\mathrm{DF}}=\max_{p(x,x_r)}\min\{I(X;Y_r\mid X_r),I(X,X_r;Y)\}\)\(R_{\mathrm{cut}}=\max_{p(x,x_r)}\min\{I(X;Y,Y_r\mid X_r),I(X,X_r;Y)\}\)
Symbol
\(C\)
Error criterion
Average-error source-to-destination capacity.
03 · Evidence

Known bounds and characterizations

TypeClaimMethodSource
lower \(C\ge R_{\mathrm{DF}}\) The relay decodes the source message and cooperatively forwards it. 1979 [1]
upper \(C\le R_{\mathrm{cut}}\) Apply a converse across each cut separating source and destination. 1979 [1]
04 · History

Bound timeline

  1. 1979

    Cover and El Gamal established the principal coding theorems and capacity for major relay subclasses.

    Reference
05 · Frontier

What remains open?

Central question

Find a computable exact capacity characterization for the unrestricted discrete memoryless relay channel.

Why the gap remains

The relay can mix partial decoding, compression, and coherent cooperation across blocks, while standard cut-set arguments ignore the causal structure that limits these strategies.

What would count as progress

  • Identify a new nontrivial subclass where an inner and outer bound coincide.
  • Strengthen the converse using relay causality without introducing an intractable multiletter expression.
  • Produce a channel family with a certified quantitative gap between standard bounds and a new scheme or converse.

Concrete subproblems

open

Formalize the causal relay code model and the classical cut-set statement.

open

Curate exact-capacity subclasses as separate atlas entries.

06 · Lean

Formalization status

Lean: not started

Not started

A reusable causal network-code layer is needed before formalizing relay bounds.

  1. Definitions
  2. Statement
  3. Partial proof
  4. Complete proof

No Lean file is linked yet. A contribution should begin by reusing the shared definitions under lean/CapacityAtlas.

References

Primary sources

  1. Thomas M. Cover and Abbas El Gamal (1979). Capacity theorems for the relay channel. IEEE Transactions on Information Theory. doi:10.1109/TIT.1979.1056084
Keep exploring

Related entries

Channels with memory Updated 2026-08-09

Binary deletion channel

Open Lean: not started

Each input bit is independently deleted without an erasure marker. The exact capacity is unknown for every nontrivial deletion probability.

\(0.1221(1-d)<C_{\mathrm{del}}(d)\le 0.3578(1-d)\)
2 bounds Open entry
Point-to-point Updated 2026-08-09

Binary symmetric channel

Solved Lean: definitions

Each bit is independently flipped with probability p. This is the canonical finite noisy channel.

\(C_{\mathrm{BSC}}(p)=1-h_2(p)\)
2 bounds Open entry