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.
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.
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