Capacity Atlas Channel-capacity problems
Network coding

Sun-Jafar 11-message multiple-unicast index-coding instance

This is the smallest multiple-unicast instance identified by Sun and Jafar where Shannon inequalities do not give the best known converse.

Open Lean: definitions SJ11
01 · Model

Channel specification

Input

\(Eleven independent messages W_1 through W_11 held by one broadcaster.\)

Output

\(Receiver j must recover W_j from the common broadcast and its side information.\)

Law

The unknown interferers at receivers 1 through 11 are respectively {W_4,W_5}, {W_5}, {}, {}, {W_2}, {W_2,W_3}, {W_1,W_3}, {W_2,W_4}, {W_3,W_4}, {W_3,W_5}, and {W_4,W_6}. Every other nonrequested message is side information.

Assumptions

  • All messages have the same rate.
  • Arbitrary blocklength and nonlinear codes are allowed.
  • Each receiver has zero-error or asymptotically vanishing-error decoding under the stated capacity convention.
02 · Capacity

Nonlinear symmetric capacity

message symbols per broadcast symbol bounds
\[\frac{5}{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\]

The linear symmetric capacity is exactly 5/13. Whether nonlinear coding improves it remains open.

Best lower boundOpen gapBest upper bound
\(\frac{5}{13}\)Conjectured: \(\frac{5}{13}\)\(\frac{11}{28}\)
Symbol
\(C_{\mathrm{sym}}\)
Error criterion
Symmetric multiple-unicast index-coding capacity.
03 · Evidence

Known bounds and characterizations

TypeClaimMethodSource
lower \(C_{\mathrm{sym}}\ge\frac{5}{13}\) Explicit vector linear interference-alignment code. 2015 [1]
upper \(C_{\mathrm{sym}}\le\frac{11}{28}\) Entropic converse using the Zhang-Yeung non-Shannon information inequality. 2015 [1] [2]
linear exact \(C_{\mathrm{sym}}^{\mathrm{linear}}=\frac{5}{13}\) Achievability plus an Ingleton linear-rank converse. 2015 [1]
04 · History

Bound timeline

  1. 1998

    Zhang and Yeung discovered the first non-Shannon information inequality used in the converse.

    Reference
  2. 2015

    Sun and Jafar established the 5/13 linear capacity and the 11/28 nonlinear outer bound.

    Reference
05 · Frontier

What remains open?

Central question

Prove the nonlinear symmetric capacity is 5/13, or construct a nonlinear code with rate strictly above 5/13 and determine the resulting capacity.

Why the gap remains

Linear-rank inequalities close the linear problem, while known entropic inequalities have not reduced the nonlinear upper bound to the achievable rate.

What would count as progress

  • Improve either endpoint with a fully specified code or auditable entropy certificate.
  • Rule out a concrete family of nonlinear codes or bounded blocklengths.
  • Formalize the existing 5/13 code, the Ingleton converse, or the 11/28 entropic converse in Lean.

Concrete subproblems

done

Formalize the exact 11-receiver instance from the interference sets.

open

Formalize the explicit 5/13 vector linear code.

open

Formalize the 11/28 Zhang-Yeung converse.

06 · Lean

Formalization status

Lean: definitions

Definitions

The shared multiple-unicast model and exact interference sets are formalized. No capacity bound is yet machine-checked.

  1. Definitions
  2. Statement
  3. Partial proof
  4. Complete proof
CapacityAtlas.IndexCoding.sunJafar11 Exact 11-message instance encoded by its receiver interference sets. lean/CapacityAtlas/Network/IndexCoding.lean
References

Primary sources

  1. Hua Sun and Syed A. Jafar (2015). Index Coding Capacity: How Far Can One Go With Only Shannon Inequalities?. IEEE Transactions on Information Theory. doi:10.1109/TIT.2015.2418289arXiv:1303.7000
  2. Zhen Zhang and Raymond W. Yeung (1998). On characterization of entropy function via information inequalities. IEEE Transactions on Information Theory. doi:10.1109/18.681320
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
Multi-user Updated 2026-08-09

General discrete memoryless relay channel

Open Lean: not started

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

\(R_{\mathrm{DF}}\le C\le R_{\mathrm{cut}}\)
2 bounds Open entry