Violating the Ingleton inequality with finite groups

Abstract

It is well known that there is a one-to-one correspondence between the entropy vector of a collection of n random variables and a certain group-characterizable vector obtained from a finite group and n of its subgroups [1]. However, if one restricts attention to abelian groups then not all entropy vectors can be obtained. This is an explanation for the fact shown by Dougherty et al [2] that linear network codes cannot achieve capacity in general network coding problems (since linear network codes form an abelian group). All abelian group-characterizable vectors, and by fiat all entropy vectors generated by linear network codes, satisfy a linear inequality called the Ingleton inequality. In this paper, we study the problem of finding non-abelian finite groups that yield characterizable vectors which violate the Ingleton inequality. Using a refined computer search, we find the symmetric group S_5 to be the smallest group that violates the Ingleton inequality. Careful study of the structure of this group, and its subgroups, reveals that it belongs to the Ingleton-violating family PGL(2, p) with primes p ≥ 5, i.e., the projective group of 2 × 2 nonsingular matrices with entries in F_p. This family of groups is therefore a good candidate for constructing network codes more powerful than linear network codes.

Files

Additional details