Information Inequalities for Five Random Variables
E. P. Csirmaz ∗, L. Csirmaz ∗† · 2025
Read Information Inequalities for Five Random Variables by E. P. Csirmaz ∗, L. Csirmaz ∗† (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-23316.txt.
Introduction
E. P. Csirmaz and L. Csirmaz push at an open frontier of information theory: the entropy region for five random variables. For a set of distributed variables, every subcollection has a Shannon entropy, and the set of all achievable entropy vectors forms a region whose boundary is cut out by entropy inequalities. With four or more variables the structure is mostly unknown, and the hard part is finding the non-Shannon inequalities that simple rules miss.
Their tool is a maximum entropy variant that adds copies of variables in successive generations. Symmetry arguments and reductions tamed the computation enough to extract every five-variable non-Shannon inequality the method yields in its nine generations. From those results the authors define two infinite families of inequalities and prove them valid. They then develop an algorithm enumerating the extremal ones. They conjecture the set characterizes what their method can produce.
Catalog record
| CREATOR | E. P. Csirmaz ∗, L. Csirmaz ∗† |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 103 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-23316
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Information Inequalities for Five Random Variables E. P. Csirmaz ∗, L. Csirmaz ∗† Abstract . The entropic region is formed by the collection of the Shannon entropies of all subvectors of finitely many jointly distributed discrete random variables. For four or more variables the structure of the entropic region is mostly unknown. We utilize a variant of the Maximum Entropy Method to delimit the five-variable entropy region. This method adds copies of some of the random variables in generations. A significant reduction in computational complexity, achieved through theoretical considerations and by harnessing the inherent symmetries, allowed us to calculate all five-variable non-Shannon inequalities provided by the first nine generations. Based on the results, we define two infinite collections of such inequalities, and prove them to be entropy inequalities. We investigate downward closed subsets of non-negative lattice points that parameterize these collections, based on which we develop an algorithm to enumerate all extremal inequalities. The discovered set of entropy inequalities is conjectured to characterize the applied method completely. Keywords: Entropy; information inequalities; polymatroid; polyhedral geometry. Classification numbers: 05B35, 26A12, 52B12, 90C29, 94A17, 52B40, 90C27 1. Introduction Many important mathematical problems can be reduced to the following question: does a collection of finite random variables exist such that the entropies of the variable subsets satisfy certain linear constraints? Examples include, but are not limited to, channel coding [ 13 ] and network coding in particular [ 36 ] , estimating the efficiency of secret sharing schemes [ 3 , 4 , 20 ] , questions about matroid representations [ 2 ] , guessing games [ 32 ] , extracting information from common strings in cryptography [ 17 ] , additive combinatorics [ 23 ] , and finding conditional independence inference rules [ 34 ] . The entropy function of finitely many discrete random variables \langle\xi_{i}:i\in N\rangle indexed by the fixed finite set N maps the non-empty subsets I\subseteq N to the Shannon entropy \mathbf{H}(\xi_{I}) of the variable set \xi_{I}=\langle x_{i}:i\in I\rangle , see [ 35 ] . The entropy region , denoted by \Gamma^{*}_{\!N} , is the range of the entropy function; it is a part of the 2^{|N|}\mkern 1.5mu{-}\mkern 1.5mu1 -dimensional Euclidean space where the coordinates are labeled by non-empty subsets of N . Entropies are non-negative real numbers, and thus the entropy region lies in the non-negative orthant of this Euclidean space. It is delimited by a collection of homogeneous linear inequalities corresponding to the non-negativity of basic Shannon information measures [ 35 ] . Points satisfying all these inequalities form the Shannon-bound ; the Shannon-bound is denoted by \Gamma_{\!N} . N. Pippenger argued in [ 31 ] that linear inequalities bounding the entropic region \Gamma^{*}_{\!N} encode the fundamental laws of Information Theory and determine the limits of information transmission and data compression. The long-standing problem of whether a linear information inequality can properly cut into the Shannon bound was settled in 1998 by Zhang and Yeung [ 37 ] by exhibiting the first example of such a non-Shannon information inequality. Their discovery initiated intensive research. The phrase Copy Lemma was coined by Dougherty et al. [ 15 ] to describe the general method distilled from the original Zhang–Yeung construction. The Copy Lemma has been applied successfully to generate several hundred sporadic and a couple of infinite families of non-Shannon entropy inequalities for \Gamma^{*}_{\!4} , see [ 8 , 15 , 28 ] . A different method, utilizing an information-theoretic lemma attributed to Ahlswede and Körner [ 1 ] , was proposed in [ 24 ] ; later it was shown to be equivalent to a special case of the Copy Lemma [ 21 ] . Our method to obtain five-variable non-Shannon entropy inequalities is based on a more general paradigm of which the Copy Lemma is a special case [ 12 ] . Derived from the principle of maximum entropy [ 18 ] , it is called MEM , short for Maximum Entropy Method. For more details, see Section 3 . Previous works on generating and applying non-Shannon entropy inequalities, such as [ 4 , 8 , 9 , 15 , 29 , 34 ] , focused on the four-variable case, and only a few sporadic five-variable non-Shannon inequalities have been discovered, such as the MMRV inequality from [ 24 ] . This is the first work that provides a method which generates an infinite collection of non-Shannon bounds on the five-variable entropy region \Gamma^{*}_{\!5} . Compared to the four-variable case, there are significant challenges, both theoretical and computational. The four-variable entropy region \Gamma^{*}_{\!4} sits in the 15 -dimensional Euclidean space, while the five-variable region \Gamma^{*}_{\!5} is 31 -dimensional. The structure of the Shannon bound \Gamma_{\!4} is well-understood: it has 41 extremal directions, and only 6 of them have no entropic points. The entropy region \Gamma^{*}_{\!4} has an inner polyhedral cone where it fills its Shannon bound, and has six isomorphic “protrusions” towards the six exceptional extremal directions, each protrusion surrounded by 15 hyperplanes of which 14 come from the Shannon bound [ 25 ] . Only the protrusions contribute to new entropy inequalities, and their dimension can be reduced to 10 . Computational results about \Gamma^{*}_{\!4} can be obtained by computing vertices and facets of numerous implicitly defined 10 -dimensional polyhedra [ 9 ] . In contrast, the Shannon bound \Gamma_{\!5} of the five-variable entropy region has 117,983 extremal directions [ 33 ] , and for a few of them it is not even known whether they contain an entropic point or not. No structural reduction similar to the four-variable case is available, and it is not known whether such a reduction exists or not. Computations about \Gamma^{*}_{\!5} can still be reduced to 25 -dimensional polyhedral enumeration problems (although with significantly larger number of constraints than in the 4 -variable case). The complexity of enumeration problems typically doubles when the dimension increases by one, making such high-dimensional enumeration problems practically intractable. We overcome this computational difficulty by applying a particular variant of the Maximum Entropy Method. This variant, working in generations, first reduces the problem dimension from 31 to 19 , and then, at each generation, adds extra copies of some of the random variables increasing the problem dimension again. Theoretical considerations and harnessing the inherent symmetry allowed us to complete the associated polyhedral computations up to nine generations. The output was the complete list of five-variable non-Shannon inequalities provided by the first nine generations. Based on the experimental results, we define an infinite collection of five-variable inequalities that we prove to be provided by this MEM variant—in particular, they are valid non-Shannon entropy inequalities—, and conjecture this collection to be complete, that is, no additional inequalities are yielded by this MEM variant. The collection of the inequalities is parametrized by finite, downward closed subsets of the non-negative lattice points of the plane. Some of the inequalities in our collection are consequences of the others; those that are not, are called extremal . We developed an incremental algorithm that enumerates, from generation to generation, the parameters yielding the extremal inequalities, in complete agreement with the computational results. Finally, we have looked at the large-scale behavior of the extremal inequalities, and pictured how these inequalities delimit a 3 -dimensional