Simple proof links group theory to advanced entropy inequalities
A simple proof of the group-theoretic Zhang-Yeung inequality
Information Theory
Summary
Some mathematical rules about measuring information, called entropy inequalities, are tricky to prove. Zhang and Yeung found a special inequality that wasn't explained by older rules. The authors solved a puzzle that translates this special rule into a group theory context, using basic group math and counting. This direct proof was missing for over twenty years and strengthens the connection between abstract algebra and information theory.
What this means in practice
- •For cryptography engineers: Use the group-theoretic form of entropy inequalities to design or analyze cryptographic protocols relying on algebraic structures.
- •For network coding developers: Incorporate the group-theoretic Zhang-Yeung inequality to better understand limitations and capabilities in network information flow designs.
A theory result. No direct application yet.
Authors
Harold Nieuwboer, Lubashan Pathirana
Abstract
Zhang and Yeung (IEEE Trans. Inf. Theory, 1998) established the first non-Shannon-type inequality that holds for all entropic vectors. Chan and Yeung (IEEE Trans. Inf. Theory, 2002) showed that there is a one-to-one relation between linear entropy inequalities and multiplicative inequalities involving cardinalities of subgroups of a finite group. The Shannon inequality admits a simple proof in the group theoretic setting, but a direct proof of the translation of Zhang--Yeung's inequality to the group-theoretic setting remained elusive. We resolve this open problem, giving a direct proof of the group-theoretic Zhang--Yeung inequality for cardinalities of subgroups of finite groups, using elementary group-theoretic and counting arguments.