PaperlayerView exact revision on arXiv

Source-linked AI summary

Sumset and inverse sumset theorems for Shannon entropy

Terence Tao

arXiv:0906.4387v5math.COmath.PR

TL;DR

The paper extends sumset and inverse sumset theory from finite sets to discrete random variables, using Shannon entropy in place of cardinality. It characterizes variables with small doubling through coset-progression approximations and identifies the exact structure when the doubling constant is one.

  • Problem

    The paper asks for analogues of sumset relations and small-doubling classifications for discrete random variables, where cardinality is replaced by Shannon entropy.

    Source: §1 · p. 1, §1.1 · p. 1

  • Method

    It develops entropy analogues of sumset and inverse sumset results, including structural approximations by uniform distributions on coset progressions.

    Source: §1 · p. 1, §1.9 · p. 6

  • Results

    If σ[X] ≤ K, X is transport-close to a uniform distribution on a bounded-rank coset progression, while σ[X] = 1 exactly for uniform distributions on cosets of finite subgroups.

    Source: §1.9 · p. 6, §5 · p. 17

  • Takeaways & Limitations

    The results give a structural description of random variables with small doubling, up to constants, in terms of coset progressions.

    Source: §1.9 · p. 6

    The weak Plünnecke–Ruzsa estimate loses an absolute constant relative to the combinatorial bound because the graph-theoretic inequality does not adapt to the entropy setting.

    Source: §1.9 · p. 5

Abstract

from arXiv · show

Let $G = (G,+)$ be an additive group. The sumset theory of Pl\"unnecke and Ruzsa gives several relations between the size of sumsets $A+B$ of finite sets $A, B$, and related objects such as iterated sumsets $kA$ and difference sets $A-B$, while the inverse sumset theory of Freiman, Ruzsa, and others characterises those finite sets $A$ for which $A+A$ is small. In this paper we establish analogous results in which the finite set $A \subset G$ is replaced by a discrete random variable $X$ taking values in $G$, and the cardinality $|A|$ is replaced by the Shannon entropy $\mathrm{Ent}(X)$. In particular, we classify the random variable $X$ which have small doubling in the sense that $\mathrm{Ent}(X_1+X_2) = \mathrm{Ent}(X)+O(1)$ when $X_1,X_2$ are independent copies of $X$, by showing that they factorise as $X = U+Z$ where $U$ is uniformly distributed on a coset progression of bounded rank, and $\mathrm{Ent}(Z) = O(1)$. When $G$ is torsion-free, we also establish the sharp lower bound $\mathrm{Ent}(X+X) \geq \mathrm{Ent}(X) + {1/2} \log 2 - o(1)$, where $o(1)$ goes to zero as $\mathrm{Ent}(X) \to \infty$.

1. Introduction

The introduction develops entropy analogues of Plünnecke–Ruzsa sumset theory and Freiman–Ruzsa inverse sumset theory for discrete random variables in additive groups. It also discusses a proposed but unproved high-entropy lower bound in the torsion-free case and other entropy sumset inequalities of interest in a different regime.

1.1. Sumset and inverse sumset theory: a quick review.

  • Classical inverse sumset theory uses coset progressions to describe finite sets with small doubling, including a theorem placing such sets inside progressions of rank O(K).A coset progression combines a finite subgroup with a generalized arithmetic progression.Source: §1.1 · pp. 2–3

1.5. Shannon entropy.

  • Entropy doubling is noise-tolerant: a small amount of low-probability noise can greatly increase a set’s doubling while barely affecting its uniform distribution’s doubling.The paper illustrates this with an interval augmented by about √N integers in general position.Source: §1.5 · p. 4

1.9. Main results.

  • Entropy sumset estimates extend the Ruzsa triangle inequality, sum-difference inequality, and weak Plünnecke–Ruzsa inequality to random variables.The weak inequality incurs an absolute-constant loss because the graph-theoretic Plünnecke inequality is not adapted to this setting.Source: §1.9 · p. 5
  • Small entropy doubling characterizes random variables close in transport distance to uniform distributions on bounded-rank coset progressions.Doubling is exactly one for a uniform distribution on a coset of a finite subgroup; bounded Ruzsa distance also implies bounded transport distance and doubling.Source: §1.9 · pp. 5–6

1.12. The torsion-free case.

  • For large n, Xn, a sum of n independent variables taking −1 or +1 with equal probability, is approximately Gaussian with mean zero and variance n.Source: §1.12 · p. 6
  • For torsion-free G and sufficiently large H(X), the authors conjecture an entropy lower bound for adding another independent copy, but say their inverse theorem cannot establish it.They nevertheless believe the proposed inequality (21) is true.Source: §1.12 · p. 7
  • Additional entropy sumset inequalities for independent G-random variables were established in, but their bounds mainly concern large doubling constants and are not directly related to those presented here.The passage describes one as an entropy analogue of a three-set sumset inequality.Source: §1.12 · p. 7

2. Sumset estimates

The section develops entropy analogues of sumset estimates using entropy inequalities, arithmetic identities, and independent or conditionally independent trials. These yield bounds for sums and differences, including controlled growth of iterated sums when doubling is small.

2. Sumset estimates

  • For conditionally independent X and Y given Z, H(X + Y | Z) lies between max(H(X | Z), H(Y | Z)) and H(X | Z) + H(Y | Z).Without conditional independence, the upper bound still holds; the section also derives nonnegativity of Ruzsa distance.Source: §2 · p. 8
  • The entropy Ruzsa triangle inequality follows by applying submodularity to jointly determining collections built from independent X, Y, and Z.The proof uses the fact that the collections both determine X − Z and together determine (X, Y, Z).Source: §2 · pp. 8–9
  • Conditionally independent trials and submodularity establish the entropy analogue of the Balog-Szemerédi-Gowers estimate.The proof constructs trials conditioned on a shared difference, then uses entropy identities to derive the claimed inequality.Source: §2 · p. 9
  • For independent trials (X_i,Y_i) of an independent pair (X,Y), with S_i = X_i + Y_i, H(S_0 + ... + S_n) ≤ (2n + 1)H(X + Y) − nH(X) − nH(Y).Source: §2 · pp. 9–10
  • H(X1 + ... + Xn) = H(X) + O(n log σ[X]), so iterated sums grow by at most O(n log σ[X]) beyond H(X).The section also gives corresponding sum-and-difference bounds with an O((n + m) log σ[X]) error.Source: §2 · p. 10

3. An entropy version of the Balog-Szemer´edi-Gowers lemma

The section gives an entropy analogue of the Balog-Szemerédi-Gowers lemma for weakly dependent random variables whose sum has small entropy. It obtains conditionings that retain most of the variables’ entropy while keeping their independent sum’s entropy small.

3. An entropy version of the Balog-Szemerédi-Gowers lemma

  • When weakly dependent X and Y have a sum of small entropy, conditionings can capture most of their entropy while their independent sum still has small entropy.This is the section’s stated entropy counterpart to refining sets in the combinatorial lemma.Source: §3 · p. 10
  • The proof gives an explicit conditioning, deriving its bound through entropy inequalities for sums and differences.An intermediate estimate bounds H(X1 − X2 | Y) in terms of H(X + Y), H(Y), H(X), and H(X, Y).Source: §3 · pp. 10–12
  • The theorem’s construction uses conditionally independent trials to produce X2 and Y′ conditionally independent relative to X1, Y.The theorem states an entropy bound of 2H(Y) + 7 log K for the resulting conditioning.Source: §3 · p. 10
  • The exponent 7 in the entropy lemma matches the combinatorial statement because the proofs are fundamentally the same.The section relates the argument to paths of length three in a regular bipartite graph.Source: §3 · pp. 10–11

4. Uniformisation

The section proves uniformisation results for distributions on finite groups and coset progressions, measuring closeness to uniformity by entropy transport distance. Its coset-progression bound is sharp up to constants and has better constant dependence than the finite-group result.

Uniformisation

  • The section establishes uniformisation bounds on groups and an analogous result for coset progressions.The coset-progression result is obtained by lifting to a finite group and pushing the transport bound back without wraparound effects.Source: §4 · pp. 12, 16
  • The finite-group uniformisation result bounds disttr(p, pU) by O(log K).The paper describes this as a special case of the coset-progression theorem, with significantly better dependence on the constants in the latter.Source: §4 · p. 12
  • The proof reduces transport by flattening high-density regions, then iteratively transporting remaining irregularities to improve L2 closeness to uniform.A Bernoulli convolution step has entropy log 2, and the section states that convergence to uniformity in L2 can be exponential.Source: §4 · pp. 13, 15
  • The coset-progression bound is disttr(p, pU) ≪ log K + d, sharp up to constants.Here pU is uniform on H + P; the theorem is stated for a proper coset progression of rank d under a bounded-entropy hypothesis.Source: §4 · pp. 12, 16

5. The inverse entropy theorem

The inverse entropy theorem characterises exact and bounded small doubling through uniform distributions on finite-group cosets or bounded-rank coset progressions. The proof builds from approximate uniformity to additive structure and transport closeness.

The inverse entropy theorem

  • σ[X] = 1 exactly when X is uniform on a coset of a finite subgroup.At equality, the distribution is invariant under translations in range(X) − range(X), forcing that difference set to be a finite subgroup.Source: §5 · p. 17
  • A partition into sets As serves as a crude approximation to the quotient of G by H + P.This partition is used in the argument that controls the residual entropy outside the structured region.Source: §5 · p. 17
  • If σ[X] ≤ K, X is within bounded Ruzsa distance of uniform on a coset progression of rank O_K(1), and hence within bounded transport distance.The Ruzsa-to-transport implication is stated for a uniform distribution on a coset progression.Source: §5 · pp. 17, 19
  • For bounded doubling, X is approximately uniform on a set A whose cardinality satisfies log |A| = H(X) + O(1).The section describes A as capturing the bulk of X's entropy.Source: §5 · pp. 20, 22
  • The set A has at least ≫_K |A|^3 additive quadruples, leading to concentration on a bounded-rank coset progression.The proof invokes Balog–Szemerédi–Gowers and Freiman’s theorem between the energy bound and the concentration conclusion.Source: §5 · pp. 22, 24

6. Proof of Theorem 1.13

The proof of Theorem 1.13 assumes a sum-entropy increase below the stated threshold and develops a smoothing argument to address that case. It first reduces the random variable to a uniform coset-progression component plus a bounded-entropy remainder.

Proof strategy

  • The contradiction setup assumes H(X1 + X2) < H(X) + 1/2 log 2 − ε.The proof takes H(X) sufficiently large depending on ε before making this assumption.Source: §6 · p. 25

Reduction

  • The inverse theorem represents X as U + Z, with U uniform on a bounded-rank coset progression and H(Z) = O(1).In the torsion-free setting, the finite subgroup component is trivial, so U is uniform on a progression.Source: §6 · p. 25

Smoothing

  • The proof embeds the relevant distribution into a box in Zd and finds a short direction in which the sum distribution changes little in total variation.The smoothness lemma supplies r along the first coordinate direction when H(X) is sufficiently large.Source: §6 · p. 26

Residue-class argument

  • For a general short direction r = mr′, the proof maps it to m and separates the argument by residues modulo m.It introduces W := X′′′ mod m and then applies the smoothing argument within residue classes.Source: §6 · pp. 27–29

Appendix A. Basic properties of entropy

The appendix collects entropy identities and inequalities used in the paper. It relates conditioning and determination to entropy bounds, independence, and submodularity.

Conditional entropy

  • Conditioning defines H(X|Y) through the entropies of the conditional distributions, with the total probability formula combining those cases.The appendix states H(X|Y) = H(X, Y|Y).Source: Appendix A · p. 31

Independence

  • Equality in the conditional-entropy inequality holds exactly when the conditional distributions agree with the unconditional distribution, that is, when X and Y are independent.The appendix also gives the conditional-independence version relative to a conditioning variable.Source: Appendix A · pp. 31–32

Determination

  • If X determines Y, then H(X, Y) = H(X) and H(Y|X) = 0.Determination means Y is a function of X.Source: Appendix A · p. 32

Submodularity

  • When X1 and X2 each determine X0, and together determine X12, submodularity gives H(X12) + H(X0) ≤ H(X1) + H(X2).The inequality is stated under those determination conditions.Source: Appendix A · p. 32
Loading 0906.4387v5…