Violating the Ingleton Inequality with Finite Groups

Wei Mao, Babak Hassibi

Introduction

In information theory, the characterization of entropy vectors is a fundamental challenge. These vectors represent the possible joint entropies of a set of random variables and define the capacity limits of communication networks. While all entropy vectors are submodular, linear network codes—the standard for practical implementation—must satisfy an additional constraint known as the Ingleton inequality.

It has been established that linear codes are insufficient for certain network problems. To surpass this "linear ceiling," researchers seek mathematical structures that violate the Ingleton inequality. Given the known correspondence between entropy vectors and finite groups, this research focuses on identifying non-abelian groups capable of producing Ingleton-violating vectors.

Mathematical Framework and Notation

The analysis relies on specific notations from abstract algebra to describe group orders, isomorphisms, and subgroup relations. These definitions are essential for identifying the specific subgroup configurations that lead to Ingleton violations.

Standard abstract algebra notations used in the group-theoretic analysis.

Methodology: Algorithmic Search and Pruning

The researchers utilized the GAP (Groups, Algorithms, and Programming) system to systematically explore the "Small Group" library. The search encompassed all finite groups with orders up to 2000 (excluding order 1024).

To manage the computational complexity, the team developed "negative conditions"—theoretical properties that guarantee a group will satisfy the Ingleton inequality. For instance, abelian groups and groups with specific subgroup hierarchies were pruned from the search space, allowing the algorithm to focus on promising non-abelian candidates.

The Smallest Violator: $S_5$

The search identified the symmetric group $S_5$, with an order of 120, as the smallest finite group to violate the Ingleton inequality. This represents a significant improvement over previous examples, which involved groups of prohibitively large orders (such as factorials of 203).

The violation in $S_5$ arises from a specific configuration of four subgroups, $G_1, G_2, G_3, G_4$, which form what the authors term a "flower" structure. This arrangement mimics the non-linear dependencies required to break the Ingleton bound.

Subgroup structure and orders for the smallest Ingleton-violating group, $S_5$.

Generalization to the $PGL(2, p)$ Family

By recognizing that $S_5$ is isomorphic to the Projective General Linear group $PGL(2, 5)$, the researchers generalized their findings to the entire $PGL(2, p)$ family. They proved that $PGL(2, p)$ violates the Ingleton inequality for all primes $p \ge 5$.

The quantitative violation for this family was calculated as $2(p-1)(4-p)$. For $p \ge 5$, this value is strictly negative, confirming the violation. Further computational tests showed that while $PGL(2, 4)$ (or $PGL(2, 2^2)$) does not violate the inequality, $PGL(2, 8)$ and $PGL(2, 9)$ do, suggesting the existence of even broader classes of violating groups.

Conclusion and Future Directions

This work identifies $S_5$ as the minimal non-abelian structure needed to outperform linear network codes. While these findings provide a theoretical foundation for non-linear coding, practical implementation remains a challenge. Future research will focus on developing concrete algorithms to translate these group structures into functional codes and addressing the increased decoding complexity associated with non-abelian frameworks.

Summary updated

BibTeX
@inproceedings{mao2009violating,
  author = {Wei Mao and Babak Hassibi},
  title = {{Violating the Ingleton Inequality with Finite Groups}},
  booktitle = {Allerton},
  year = {2009},
  doi = {10.1109/allerton.2009.5394878},
}
Figure