Sumset and inverse sumset theory for Shannon entropy. (English) Zbl 1239.11015

Tao, Terence

Comb. Probab. Comput. 19, No. 4, 603-639 (2010).

Several of the most important results about cardinality questions concerning finite sets in commutative groups are extended to random variables assuming finitely many values, while cardinality is replaced by entropy. Given a finite set \(A\) in a commutative group, the entropy of the random variable \(X\) uniformly distributed on \(A\) is connected to the cardinality of \(A\) by the simple formula \(H(X)= \log |A|\). For two sets \(A_1, A_2\) and corresponding variables \(X_1, X_2\) the entropy of \(X_1+X_2\) is not determined by the size of the sumset, but gives another important quantity where sums with few representations are less important; in the author’s words, “one can thus think of entropy sumset theory as a ‘noise-tolerant’ analogue of sumset theory”.
For an analogue of the doubling constant Tao takes \[ \sigma[X] = \exp ( H(X_1+X_2) - H(X) ), \] where \(X_1, X_2\) are independent copies of \(X\). For this notion he establishes the analogue of (Green and Ruzsa’s extension of) Freiman’s theorem as follows. If \( \sigma[X] \leq K\), then \(X\) is within bounded distance in the transport metric from another variable \(U\), which is uniformly distributed on a coset progression of bounded rank, the involved bounds depending on \(K\).
Analogues of Plünnecke-type cardinality inequalities are also proved, in the general case in a less exact form than for cardinalities. This is due to the fact that there is no entopy analogue of Plünnecke’s graph inequality. By recent works of G. Petridis we know that graph theory can be replaced by simpler counting arguments in many applications, and this may perhaps be applied in the entropy case as well.
The analogue of the simplest cardinality inequality \(|A+A| \geq 2 |A| - 1\) (in torsion-free groups) undergoes an interesting metamorphosis in the entropy case. It becomes \( \sigma[X] \geq \sqrt 2 -\varepsilon\), where \(\varepsilon \to 0\) as \(H(X)\to \infty\), and the extremal case is an approximately normal distribution.
The reviewer thinks this entropy version is not only important in its own right but may have applications to classical sumset problems.

Reviewer: Imre Z. Ruzsa (Budapest)

MSC:

11B13	Additive bases, including sumsets
11B34	Representation functions
94A17	Measures of information, entropy

Keywords:

sumset; entropy; additive combinatorics

Citations:

Zbl 0199.36602; Zbl 0869.11011

References:

[1]	DOI: 10.1007/s00493-008-2271-7 · Zbl 1254.11017 · doi:10.1007/s00493-008-2271-7
[2]	DOI: 10.1007/BF01212974 · Zbl 0812.11017 · doi:10.1007/BF01212974
[3]	DOI: 10.1090/S0894-0347-04-00459-X · Zbl 1062.94006 · doi:10.1090/S0894-0347-04-00459-X
[4]	DOI: 10.1007/s000390050065 · Zbl 0907.11005 · doi:10.1007/s000390050065
[5]	DOI: 10.1016/j.aim.2008.05.002 · Zbl 1165.11016 · doi:10.1016/j.aim.2008.05.002
[6]	Tao, Additive Combinatorics (2006) · doi:10.1017/CBO9780511755149
[7]	DOI: 10.1112/jlms/jdl021 · Zbl 1133.11058 · doi:10.1112/jlms/jdl021
[8]	Ruzsa, Number Theory: New York Seminar (1996)