Tightening Information Bounds with Non-Shannon Inequalities

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 230 papers45 conceptsfrozen 2026-10-04

For decades, the "rules" of information theory were thought to be simple. If you have a set of random variables, their joint entropies must obey basic properties like non-negativity and submodularity (e.g., $H(X, Y) \leq H(X) + H(Y)$). These are known as Shannon-type inequalities. However, as we move from simple point-to-point communication to complex networks and distributed systems, researchers have discovered that these basic rules are insufficient. There is a hidden layer of constraints—non-Shannon inequalities—that define the true physical limits of information.

The Gap in the Entropy Region

To understand why this matters, imagine the "entropy region": a high-dimensional space where every point represents a possible set of entropy values for a group of variables. Shannon-type inequalities define a "polytope" (a flat-sided geometric shape) that acts as an outer bound for this region.

For a long time, it was assumed this outer bound was tight. But as Shaocheng Liu demonstrates in Entropy Functions on Two-Dimensional Faces of Polymatroidal Region of Degree Four, once you have four or more variables, the actual entropic region starts to pull away from the Shannon bound. There are "gaps" where Shannon's rules say a certain information distribution is possible, but in reality, no such distribution can exist. Non-Shannon inequalities are the mathematical tools required to describe these tighter, more accurate boundaries.

Why Shannon-Type Rules Fail in Networks

The insufficiency of standard entropy rules is most visible in multi-user communication. In The two-unicast problem, Sudeep Kamath, Venkat Anantharam, and Chih-Chun Wang show that traditional "edge-cut" analysis—which relies on Shannon-type logic to find bottlenecks—fails to characterize the capacity of even simple networks.

Standard tools treat information like a fluid flowing through pipes. But information in a network has complex dependencies. As CAO DAMING and Yinfei Xu argue in their work on Coded Caching, Shannon-type inequalities fail to capture the structural requirements of practical coding schemes. Without non-Shannon constraints, we overestimate what these systems can achieve, leading to a persistent gap between theoretical bounds and what is actually achievable.

Automating the Discovery of Limits

Because non-Shannon inequalities are notoriously difficult to derive by hand, researchers have turned to computational methods. Chao Tian and colleagues developed the CAI toolbox, which translates information-theoretic problems into Linear Programming (LP) models. By treating entropy bounds as optimization constraints, these tools can automatically find the fundamental limits of systems like Private Information Retrieval (PIR).

Similarly, Ido B. Gattegno, Ziv Goldfeld, and Haim H. Permuter introduced FME-IT, a tool that uses Fourier-Motzkin Elimination to strip away redundant Shannon constraints. These automated frameworks are essential because, as Carles Padró and Leonor Vázquez found in their study of Secret Sharing Schemes, incorporating even a few non-Shannon inequalities can significantly tighten the lower bounds on how much data must be stored to keep secrets secure.

Toward a Unified Theory

While many non-Shannon inequalities seem like isolated mathematical curiosities, there is a push toward unification. Efe Aras and Thomas A. Courtade have proposed a framework based on Gaussian Comparisons, suggesting that many disparate entropy inequalities are actually specific instances of a single geometric principle.

By bridging the gap between the algebraic manipulation of entropy and the convex geometry of the entropy region, this research direction is moving us toward a complete map of information. Whether it is solving Cover's Open Problem on relay channels or breaking bottlenecks in Locally Correctable Codes, the path forward lies in looking beyond Shannon's original rules to the more complex, high-order interdependencies of information.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 14 papers
  2. Version 1 · 2026-10-04 · 30 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_shannon_information_constraints_6789f19b,
  title = {non-Shannon information constraints},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-shannon-information-constraints/rdr_6789f19b04e344f99c2bd10beaa7c915},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_tightening_information_bounds_with_non_s_6789f19b_v1,
  title = {Tightening Information Bounds with Non-Shannon Inequalities},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/tightening-information-bounds-with-non-shannon-inequalities/rdr_6789f19b04e344f99c2bd10beaa7c915/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}