Entropy Functions on Two-Dimensional Faces of Polymatroidal Region of Degree Four: Part I: Problem Formulation and More

Shaocheng Liu, Qi Chen

TL;DR

This paper provides a geometric roadmap of the entropy region for four random variables by characterizing entropy functions on the two-dimensional faces of the Shannon outer bound. The authors identify 59 distinct types of these faces and successfully determine the "entropic" portions of 49 of them, revealing where Shannon-type inequalities are tight and where non-Shannon-type constraints emerge.

What Problem Does This Paper Address?

In information theory, a central challenge is characterizing the entropy region ($\Gamma^*_n$)—the set of all possible entropy values that a collection of $n$ random variables can take. For $n=2$ or $3$, this region is perfectly described by basic Shannon-type inequalities (like "entropy is non-negative" and "conditioning reduces entropy"). However, for $n \ge 4$, we know "non-Shannon" inequalities exist, meaning the traditional Shannon outer bound ($\Gamma_n$) is too loose.

Instead of searching for new inequalities globally, this paper takes a geometric approach: it looks at the faces of the Shannon outer bound. By studying these faces, researchers can understand exactly where the Shannon bound fails and what specific structures (like combinatorial designs) are required to "fill" the entropy region. This paper specifically tackles the 2D faces of the 4-variable region ($\Gamma_4$), which serves as a critical stepping stone toward understanding higher-dimensional information structures.

Methods

The authors employ a mix of computational geometry and discrete mathematics:

  1. Algorithmic Enumeration: They developed an algorithm (Algorithm 1) to identify all 2D faces of the polyhedral cone $\Gamma_4$. Since $\Gamma_4$ has 41 extreme rays, they checked all possible pairs to see which ones form a valid 2D face. This resulted in 510 faces, categorized into 59 distinct types based on symmetry.
  2. Graph-Coloring Technique: To prove whether a point on a face is "entropic" (i.e., corresponds to actual random variables), they used a technique pioneered by František Matúš. This involves representing the relationships between variables as bipartite or tripartite graphs and using coloring properties to determine if a valid probability distribution exists.
  3. V-Representation: They characterize the faces as the convex hull of extreme rays. For each face, they determine the "entropic region" $E^*$, which is the intersection of the face with the true entropy region.

Datasets

As a theoretical paper in information theory, it does not use external datasets. Instead, it operates on the mathematical structure of the Polymatroidal Region of Degree Four, defined by the 28 elemental Shannon inequalities for four variables.

Key Insights and Ideas

  • The "All-Entropic" vs. "Non-Entropic" Divide: Of the 59 face types, 13 are "all-entropic" (every point on the face is a valid entropy function), while 7 are completely "non-entropic" (except for the origin). The non-entropic faces are those that "violate" known non-Shannon inequalities like the Zhang-Yeung inequality.
  • Combinatorial Requirements: For many non-trivial faces, a point is only entropic if it corresponds to specific combinatorial structures. For example, some faces require the variables to form Latin Squares, Orthogonal Arrays, or Latin Cubes.
  • Discrete vs. Continuous: While the Shannon bound is a continuous cone, the true entropy region on certain faces is restricted to discrete points (e.g., $a = \log v$ for integer $v$) or specific sub-regions, highlighting the "gap" between polymatroids and actual entropy functions.
  • Symmetry Matters: The 510 faces are highly redundant; by using permutations of the four variables, the authors reduced the problem to just 59 types, making the characterization task manageable.

Key Results

The paper provides a comprehensive classification in Table 4, which acts as a reference for the 49 characterized face types. Key findings include:

  • 49 types fully characterized: This includes 13 all-entropic types, 7 non-entropic types, 17 types inherited from the 3-variable case ($\Gamma_3$), and 12 new non-trivial types.
  • Quantitative Bounds: For several face types, the authors proved that the entropic region is defined by conditions like $a + b \ge \log \lceil 2^a \rceil$, showing a non-linear boundary even on a 2D face.
  • Geometric Visualization: The paper provides 2D plots for each face type, showing exactly which $(a, b)$ coordinates are achievable.

Limitations and Future Work

  • The Remaining 10: This is "Part I." Ten face types remain uncharacterized here; the authors note that 8 will be solved in Part II, while 2 remain only partially characterized due to their extreme combinatorial complexity.
  • Higher Dimensions: While 2D faces are a major step, $\Gamma_4$ is a 15-dimensional space. Characterizing 3D faces or the interior remains an open, significantly harder problem.
  • Scaling to $n > 4$: The number of extreme rays and faces grows exponentially with the number of variables, suggesting that the manual/algorithmic approach used here will need even more sophisticated automation for $n=5$.

Summary updated

Abstract

Characterization of entropy functions is of fundamental importance in information theory. By imposing constraints on their Shannon outer bound, i.e., the polymatroidal region, one obtains the faces of the region and entropy functions on them with special structures. In this series of two papers, we characterize entropy functions on the 2-dimensional faces of the polymatroidal region of degree 4. In Part I, we formulate the problem, enumerate all 59 types of 2-dimensional faces of the region by an algorithm, and fully characterize entropy functions on 49 types of them. Among them, those non-trivial cases are mainly characterized by the graph-coloring technique. The entropy functions on the remaining 10 types of faces will be characterized in Part II, among which 8 types are fully characterized, and 2 types are partially characterized.
BibTeX
@misc{liu2023entropy,
  author = {Shaocheng Liu and Qi Chen},
  title = {{Entropy Functions on Two-Dimensional Faces of Polymatroidal Region of Degree Four: Part I: Problem Formulation and More}},
  year = {2023},
  eprint = {2305.06250},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2305.06250},
}

Loading related content...

Figure