Information theory simplifies sumset inequalities in groups
From an entropic inequality for sums in abelian groups to the theorems of Ruzsa and Plünnecke
Information Theory
Summary
This work shows how certain mathematical inequalities about adding sets in groups can be proven using ideas from information theory, which studies information and randomness. The authors use a simple approach based on maximizing entropy, a way to measure uncertainty, rather than relying on complicated or indirect methods. Their approach applies to various types of groups, including those where the order of elements matters. This gives clearer and more direct proofs of important known results in group theory and combinatorics.
What this means in practice
- •For combinatorial optimizers: Use the entropy-based proof to guide design of algorithms for analyzing sumset sizes in additive combinatorics problems.
- •For cryptography engineers: Incorporate entropy-focused techniques to better understand group operations relevant to cryptographic protocol security.
A theory result. No direct application yet.
Authors
Chandra Nair, Aref Namayandeh, Zhaobang Zhu
Abstract
We give a direct information-theoretic proof of the Plünnecke--Ruzsa inequalities for finite subsets of abelian groups. The argument rests on an elementary coupling inequality proved by maximizing joint entropy, without tensor powers or asymptotic constructions. It also yields Ruzsa's sumset triangle inequality and an extension to non-abelian groups.