Sumset and Entropic Inequalities

Posted on Edited on

Several researchers have observed that certain inequalities in Additive Combinatorics have analoguous Entropic inequalities.

Theorem [Ruzsa, 1996]
Let $A$ and $B$ be finite subsets on an abelian additive group $(\mathbb{G}, +)$, we have
$$|A| |B| |A + B| \le |A - B|^3.$$

Theorem [Tao, 2009]
Let $X$ and $Y$ be independent random variables with finite support on an abelian additive group $(\mathbb{G}, +)$, we have
$$H(X) + H(Y) + H(X + Y) \le 3 H(X - Y).$$

Even though these two inequalities may appear similar, there is no direct implication between them. However, their proofs do exhibit some similarities.

Ruzsa Equivalence Theorem

Ruzsa introduced an equivalence theorem aimed at establishing an explicit implication between a combinatorial inequality and a related entropic inequality. His primary emphasis was on the combinatorial inequality involving graph-restricted sumsets.

Definition [Graph-resticted sumset]
Suppose $A$ and $B$ are defined on an ambient additive group $(\mathbb{G}, +)$. Let $G$ be a subset of $A \times B$ (or equivalently a bipartite graph). The $G$-restricted sumset of $A$ and $B$ is defined as $A \overset{G}{+} B := {a + b : (a, b) \in G}$.

Theorem Let $(\mathbb{T}, +)$ be a finitely generated torsion-free abelian group.

  • $f$, $g_1, \dots, g_\ell$: Linear functions on $\mathbb{T} \times \mathbb{T}$ with integer coefficients.

    • In other words: $f(s, t) = a s + b t$ and $g_i(s, t) = c_i s + d_i t$, where $a, b, c_i, d_i$ are integers and $s, t \in \mathbb{T}$.

  • $\beta_1, \dots, \beta_\ell$: Positive real numbers.

The following statements are equivalent:

  1. Suppose $A$ and $B$ are finite subsets of $\mathbb{T}$. For any $G \subseteq A \times B$, we have
    $$
    |{a s + b t: (s, t) \in G}| \leq \prod_{i = 1}^\ell |{c_i s + d_i t: (s, t) \in G}|,
    $$
    or equivalently,
    $$|f(G)| \leq \prod_{i = 1}^\ell |g_i(G)|^{\beta_i}$$

  2. For every pair of random variables $(X, Y)$ with finite support in $\mathbb{T}$, we have
    $$
    H(a X + b Y) \leq \sum_{i = 1}^\ell \beta_i H(c_i X + d_i Y),
    $$
    or equivalently,
    $$|f(G)| \leq \prod_{i = 1}^\ell |g_i(G)|^{\beta_i}$$

An application of Ruzsa's Equivalence Theorem is as follows:

Theorem [Katz and Tao, 1999]
Let $A$ and $B$ be finite subsets on an abelian additive group $(\mathbb{G}, +)$, for any $G \subseteq A \times B$, we have
$$|A \overset{G}{-} B| \leq |A|^{2/3} |B|^{2/3} |A \overset{G}{+} B|^{1/2}.$$

Corollary [Ruzsa, 2009]
Let $X$ and $Y$ be random variables with finite support on an abelian additive group $(\mathbb{G}, +)$, we have
$$H(X - Y) \leq \frac{2}{3} H(X) + \frac{2}{3} H(Y) + \frac{1}{2} H(X + Y).$$

Generalized Ruzsa Equivalence Theorem

There is a trivial equivalence between cardinality inequalities and entropy inequalities via the observation that $\log |A + B| = \max_{P_{X, Y}} H(X + Y)$, where $X$ takes values in $A$ and $Y$ takes values in $B$. The equality is clearly obtained by taking a uniform distribution on the support of $|A + B|$. However, we are seeking non-trivial versions of equivalence theorems.

Theorem Let $(\mathbb{T}, +)$ be a finitely generated torsion-free abelian group. Let $f_1, \dots, f_k$ and $g_1, \dots, g_\ell$ be linear functions on $\mathbb{T}^n$ with integer coefficients, and let $\alpha_1, \dots, \alpha_k, \beta_1, \dots, \beta_\ell$ be positive real numbers. For the linear function $f_i$, let $S_i \subseteq [1 : n]$ denote the index set of non-zero coefficients. Similarly, for $g_i$ let $T_i \subseteq [1 : n]$ denote the corresponding index set of non-zero coefficients. Further let us assume that $S_i$ is a pairwise disjoint collection of sets. Then following statements are equivalent:

  1. For any $A_1, A_2, \dots, A_n$ that are finite subsets of $\mathbb{T}$, we have
    $$
    \prod_{i = 1}^k |f_i(A_{S_i})|^{\alpha_i} \leq \prod_{i = 1}^\ell |g_i(A_{T_i})|^{\beta_i},
    $$
    where $A_S = \otimes_{i\in S} A_i$.

  2. For every sequence of random variables $(X_1, \dots, X_n)$, with fixed marginals $P_{X_i}$ and having finite support in $\mathbb{T}$, we have
    $$
    \sum_{i = 1}^k \alpha_i \max_{\Pi(X_{S_i})} H(f_i(X_{S_i})) \leq \sum_{i = 1}^\ell \beta_i \max_{\Pi(X_{T_i})} H(g_i(X_{T_i})),
    $$
    where $\Pi(X_S)$ is collection of joint distributions $P_{X_S}$ that are consistent with the marginals $P_{X_i}, i \in S$.

A direct application of generalized Ruzsa theorem is as follows:

Corollary For distributions $P_X, P_Y, P_Z$ with finite support on a finitely generated torsion-free group $\mathbb{T}$, we have
$$
H(X) + \max_{\Pi(Y, Z)} H(Y + Z) \leq \max_{\Pi(X, Y)} H(X + Y) + \max_{\Pi(X, Z)} H(X + Z).
$$

Proof In [Ruzsa, 1996], Ruzsa showed that for any finite $A, B, C$ on a finitely generated torsion-free abelian group $\mathbb{T}$, we have
$$
|A| |B + C| \leq |A + B| |A + C|.
$$
We obtain the desired entropic inequality by applying Theorem 1.

Question Is there a direct entropic proof for the demonstrated inequality?

To the best of the author’s knowledge, there is no direct entropic proof available for the demonstrated inequality. If you have a specific interest in this question, it is recommended to reach out to the author for further information.