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

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.

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 |

### 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) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.