CCapacity Atlas
sun-jafar-six-message-groupcast-index-coding

Sun-Jafar six-message groupcast index-coding instance

A six-message, ten-receiver groupcast instance has linear capacity 5/13 and a non-Shannon nonlinear upper bound 11/28.

Index coding Finite alphabet Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-only result

Channel and question

Input
Six independent equal-length messages held by one broadcaster.
Output
Ten receivers demand messages \((1,1,2,3,4,5,6,6,6,6)\) in source order.
Law
The one-based interference rows are \(\{2,4\},\{4,5\},\{5\},\varnothing,\varnothing,\{2\},\{1,3\},\{2,3\},\{3,4\},\{3,5\}\).
Quantity
Zero-error nonlinear symmetric capacity \(C_{\mathrm{sym}}\), measured in message symbols per broadcast symbol.

Criterion. Zero error for every message tuple and receiver, with arbitrary finite alphabet and blocklength.

  • Messages are uniform, independent, and use one common finite alphabet.
  • Decoding error is exactly zero and arbitrary blocklength nonlinear codes are allowed.

Current status

\[\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\]

Global vector-linear symmetric capacity is exactly 5/13; Shannon inequalities alone stop at 2/5.

ResultRelationMethodYear
Lower\(C_{\mathrm{sym}}\ge\frac5{13}\)Explicit vector-linear subspace alignment.2015
Upper\(C_{\mathrm{sym}}\le\frac{11}{28}\)Zhang-Yeung non-Shannon information inequality.2015
Linear Exact\(C_{\mathrm{sym}}^{\mathrm{linear}}=\frac5{13}\)Vector-linear construction and Ingleton converse.2015

Research frontier

Prove the nonlinear capacity is 5/13 or construct a zero-error nonlinear code above it.

Why it remains open. Known non-Shannon inequalities improve the converse but do not meet the linear construction.

What would count as progress

  • Improve either endpoint with an auditable certificate.

Lean formalization

Canonical statementStatement

Version 1 · Lean. Demands and interference rows are machine-checked translations of the one-based primary-source figure.

Substantial proofs0 linked

No external Lean proof is registered. Proofs longer than roughly 50 lines or requiring problem-specific infrastructure should live in a dedicated repository and link back to this statement version.

References

  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.2418289.
  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.

Discussion

Thread key: capacityatlas:sun-jafar-six-message-groupcast-index-coding

Find discussionStart discussion

Related problems

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

A multiple-unicast instance where the exact nonlinear symmetric capacity is separated from the known linear answer.

Index coding Finite alphabet Multiple unicast Non-Shannon inequalities Nonlinear coding Symmetric capacity Bounds only Linear-only result
Open \(\frac5{13}\le C_{\mathrm{sym}}\le\frac{11}{28}\)
Binary deletion channel BDC

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

Point-to-point Binary Finite alphabet Memory Deletion Capacity Bounds only
Open \(0.1221(1-d)<C_{\mathrm{del}}(d)\le0.3578(1-d)\)
Binary random-insertion channel

In the fixed iid random-insertion model, each transmitted bit may be followed by one independent fair inserted bit and exact capacity is unknown.

Point-to-point Finite alphabet Binary Memory Capacity Bounds only
Open \(0\le C_{\mathrm{ins}}(p)\le1\)
Binary skew-symmetric broadcast channel BSSC

This minimal binary-input broadcast channel isolates a persistent gap between Marton-type inner bounds and UV-type outer bounds.

Broadcast Finite alphabet Discrete memoryless Binary Asymmetric Capacity region Bounds only
Open \(\mathcal R_{\mathrm{Marton}}\subseteq\mathcal C_{\mathrm{BSSC}}\subseteq\mathcal R_{\mathrm{UV}}\)