Groups and information inequalities in 5 variables
Date of Issue2013
Annual Allerton Conference on Communication, Control, and Computing (51st : 2013 : Monticello, USA)
School of Physical and Mathematical Sciences
Linear rank inequalities in 4 subspaces are characterized by Shannon-type inequalities and the Ingleton inequality in 4 random variables. Examples of random variables violating these inequalities have been found using finite groups, and are of interest for their applications in nonlinear network coding . In particular, it is known that the symmetric group S5 provides the first instance of a group, which gives rise to random variables that violate the Ingleton inequality. In the present paper, we use group theoretic methods to construct random variables which violate linear rank inequalities in 5 random variables. In this case, linear rank inequalities are fully characterized  using Shannon-type inequalities together with 4 Ingleton inequalities and 24 additional new inequalities. We show that finite groups which do not produce violators of the Ingleton inequality in 4 random variables will also not violate the Ingleton inequalities for 5 random variables. We then focus on 2 of the 24 additional inequalities in 5 random variables and formulate conditions for finite groups which help us eliminate those groups that obey the 2 inequalities. In particular, we show that groups of order pq, where p; q are prime, always satisfy them, and exhibit the first violator, which is the symmetric group S4.
© 2013 IEEE. This is the author created version of a work that has been peer reviewed and accepted for publication by 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton), IEEE. It incorporates referee’s comments but changes resulting from the publishing process, such as copyediting, structural formatting, may not be reflected in this document. The published version is available at: [DOI:http://dx.doi.org/10.1109/Allerton.2013.6736607].