Source-linked AI summary
From an entropic inequality for sums in abelian groups to the theorems of Ruzsa and Pl\"unnecke
Chandra Nair, Aref Namayandeh, Zhaobang Zhu
TL;DR
Sumset and entropy inequalities both describe growth under addition, yet direct entropic counterparts for key additive-combinatorial inequalities remained incomplete. The paper proves a stronger maximal-coupling entropy inequality, derives entropic Plünnecke–Ruzsa inequalities, and obtains Ruzsa’s sumset triangle inequality and a non-abelian extension.
Problem
Direct entropic proofs of cornerstone additive-combinatorial inequalities for general abelian groups were missing, while earlier translations relied on asymptotic equivalence arguments and torsion-free groups.
Source: §1 · p. 1Method
Results
The maximal-coupling inequality yields entropic Plünnecke–Ruzsa inequalities, Ruzsa’s sumset triangle inequality, and a non-abelian sumset extension.
Source: §1 · p. 2Takeaways & Limitations
The results make the connections between entropic and additive-combinatorial statements explicit, including the abelian sumset triangle inequality.
Source: §1 · p. 2, Conclusion · p. 9The abelian proof’s recombination uses commutativity; the non-abelian case requires a different ordering.
Source: §2 · p. 3
Abstract
from arXiv · showhide
We give a direct information-theoretic proof of the Pl\"unnecke--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.
1 Introduction
Sumset and entropy inequalities both describe growth under addition, but direct entropic counterparts for cornerstone cardinality inequalities remained incomplete. The paper establishes a stronger maximal-coupling entropy inequality and uses it to connect entropic Plünnecke–Ruzsa results with sumset inequalities.
1 Introduction
- Sumset and entropy inequalities both measure growth under addition, while independent-random-variable analogues need not imply the corresponding additive-combinatorial inequalities.The paper situates its approach within prior translation work, including Ruzsa, Tao, Madiman, Marcus and Tetali, and Kontoyiannis and Madiman [4].Source: §1 · p. 1
- Plünnecke’s inequality and Ruzsa’s magnification-ratio generalization lacked direct entropic proofs for general abelian groups, motivating a conjectured maximal-coupling analogue.Earlier entropic translations relied on equivalence theorems with asymptotic typical-set arguments and a torsion-free ambient group.Source: §1 · p. 1
- The paper proves a stronger maximal-coupling entropy inequality for joint distributions with specified marginals.This inequality is the basis for the entropic sum inequality and subsequent results.Source: §1 · p. 2
- The coupling inequality yields entropic Plünnecke–Ruzsa inequalities, Ruzsa’s sumset triangle inequality, and a non-abelian sumset extension.The paper also establishes a sumset analogue of the maximal-coupling inequality.Source: §1 · p. 2
1.1 Notation and elementary facts
- The notation section fixes finite nonempty sets and sumsets, defines couplings and magnification ratios, and recalls basic entropy properties.Unless otherwise stated, the ambient group is abelian; the section also defines Φ_D for an input distribution supported on A and a channel with output support in D.Source: §1.1 · p. 2
2 The main coupling inequality
The section proves a max-coupling entropy inequality by maximizing joint entropy under fixed marginal and sum-distribution constraints. Its consequences include entropic Ruzsa and Plünnecke–Ruzsa inequalities for finite sets.
2 The main coupling inequality
- Maximizing joint entropy over couplings with fixed marginals and sum distribution yields the max-coupling entropy inequality.At the maximizer, the entropy relation reduces to a sum of nonnegative conditional mutual informations.Source: §2 · pp. 2–3
- The second recombination uses commutativity; a different ordering is needed for the non-abelian extension.The remark notes that the recombination need not preserve the distribution of Y in a non-abelian group.Source: §2 · p. 3
- H(X) + max H(Y + Z) ≤ max H(X + Y) + max H(X + Z) for the coupling maxima in Corollary 2.4.The same corollary also bounds H(X) + H(Y + Z) by those two maxima.Source: §2 · p. 4
- Inequality (4), the distributional max-coupling sum inequality, was conjectured by Lau, Nair and Zhu and is proved here directly.For finitely generated torsion-free abelian groups it was known via the equivalence theorem [6], but no direct proof avoiding that theorem was previously known.Source: §2 · p. 4
- The entropic Ruzsa distance satisfies d(pX, pZ) ≤ d(pX, pY) + d(pY, pZ) for distributions supported on finite subsets of an abelian group.The distance is defined using the maximum coupling entropy H(X + Y) minus 1.Source: §2 · p. 4
- The section states entropic Plünnecke–Ruzsa inequalities for finite set summands, including a version for k summands.Theorem 2.7 gives the two-summand statement, and Corollary 2.8 treats k summands.Source: §2 · p. 5
3 Implications for additive combinatorics
This section derives additive-combinatorial inequalities from the paper’s entropic results. It gives proofs of Ruzsa’s sumset triangle inequality and Plünnecke–Ruzsa inequalities, then states a three-set inequality with a necessary hypothesis.
3.1 Ruzsa’s triangle inequality for sumsets
- Ruzsa’s sumset triangle inequality follows from the entropic inequality for finite nonempty A, B, and C in an abelian group.The proof uses uniform distributions to relate the relevant entropies to the logarithms of the sumset sizes.Source: §3.1 · p. 6
3.2 The Plünnecke–Ruzsa inequality and its strengthening
- The section proves Plünnecke’s inequality and the different-summand Plünnecke–Ruzsa inequality for finite nonempty sets.Theorem 3.3 is the different-summand form; Theorem 3.2 is Plünnecke’s inequality, and the section also states a strengthening of Theorem 3.3.Source: §3.2 · p. 6
- Theorem 3.4 strengthens the different-summand inequality by evaluating its proof’s minimum at unifS for each nonempty S⊆A.The section presents this as a direct entropic proof, following the earlier use of tensor powers in the original route to the triangle inequality.Source: §3.2 · pp. 6–7
3.3 A three-set sumset inequality
- The three-set sumset inequality holds under the stated condition that G(A, B + C) is nonempty.The proof bounds the two relevant sum entropies using their supports in A+B and A+C.Source: §3.3 · p. 7
- The three-set inequality is false in general without its hypothesis; the section gives a counterexample in Z20.For that example, |A|=7, |A+B|=|A+C|=9, and |A+B+C|=13, so |A||A+B+C|=91 exceeds |A+B||A+C|=81.Source: §3.3 · p. 7
4 A non-abelian extension
The paper extends its coupling-entropy argument to non-abelian groups, where the direct analogue of its abelian inequality can fail. A non-abelian entropy inequality nevertheless yields a sumset bound.
4 A non-abelian extension
- The direct analogue of the abelian max-coupling inequality, and the bound involving |A||B◦C|, do not hold in general non-abelian groups.The obstruction is that preserving the specified pairwise marginals under recombination need not preserve the distribution of Y.Source: §4 · p. 7
- The non-abelian max-coupling entropy inequality bounds H(X)+H(Y◦X◦Z) by maxima of the pairwise product entropies over couplings.It applies to finite nonempty A, B, and C in a group and any coupling of marginals supported on those sets.Source: §4 · p. 7
- A non-abelian sumset inequality bounds a sum over x∈A of |B◦x◦C| using |B◦A| and |A◦C|.The paper also gives a minimum bound; in an abelian group the sum inequality reduces to Ruzsa’s sumset triangle inequality.Source: §4 · p. 8
Conclusion
The paper derives and extends known additive-combinatorial inequalities using information-theoretic arguments, contributing to the growing connection between the two fields.
Conclusion
- The paper derives and extends known additive-combinatorial inequalities using information-theoretic arguments.The authors frame this as an addition to the growing body of work linking information theory and additive combinatorics.Source: Conclusion · p. 9
A Alternative proof of Theorem 2.9
An alternative proof of Theorem 2.9 reduces a magnification-ratio bound to max-flow/min-cut, then uses a saturating flow to construct one channel that works for every input distribution.
A Alternative proof of Theorem 2.9
- The proof constructs a source–A–B–sink network with unit capacities on source-to-A and B-to-sink edges and infinite capacities on edges in the bipartite graph.A finite cut placing A′ on the source side must also place every neighbor of A′ there.Source: A Alternative proof of Theorem 2.9 · p. 11
- Since |N(A′)| ≥ μ|A′| and the cut {s} has capacity |A|, the minimum cut has capacity |A|, yielding a flow that saturates every source edge.The maximum-flow/minimum-cut theorem guarantees a flow of this value.Source: A Alternative proof of Theorem 2.9 · pp. 10–11
- Setting WY|X(y|x) = f(x,y) turns the flow into a channel, and Lemma A.2 gives a single such channel that works for every input distribution.The output distribution is induced by applying the channel to the input distribution.Source: A Alternative proof of Theorem 2.9 · pp. 10–11
- For one direction of Theorem 2.9, the proof chooses a minimizing set S* and takes the input uniformly on S* to bound H(X + Y) by log |S* + D|.The passage identifies log μ(A,D) with log |S*|.Source: A Alternative proof of Theorem 2.9 · p. 12
- For the reverse direction, the proof sets B = A + D and joins each a to a + d, then applies Lemma A.2 and minimizes over input distributions.This completes the proof of Theorem 2.9.Source: A Alternative proof of Theorem 2.9 · p. 12
Bibliographic remarks and the use of AI
The research program began with human-conceived goals connecting additive combinatorics to Gaussian optimality. AI systems later contributed to exploration and a proof construction, while the authors retained the mathematical direction and wrote the article.
Bibliographic remarks and the use of AI
- The original human research program sought to use additive-combinatorics ideas toward Gaussian optimality for information functionals in the scalar Gaussian Z-interference channel.The mathematical objectives and overarching strategy were human-conceived.Source: Bibliographic remarks and the use of AI · p. 12
- An AI assistant supported exploration of proof strategies, optimality conditions, numerical experiments, and drafts, while numerous proposed arguments and numerical outputs required correction or rejection.The authors also conducted independent numerical investigations into feasible couplings.Source: Bibliographic remarks and the use of AI · p. 12
- A separate AI system suggested the Markov recombination construction used in the final proof, which bypasses exploratory KKT calculations; the authors wrote the article.AI provided minimal stylistic help with polishing and notation.Source: Bibliographic remarks and the use of AI · p. 12