An entropic analogue of the MMS conjecture

Technical Summary: An Entropic Analogue of the MMS Conjecture

Problem Statement
The paper investigates a probabilistic problem concerning sampling without replacement from a finite population of real numbers with a zero mean. Let $P = \{x_1, \dots, x_n\}$ be a multiset of $n \ge 2$ real numbers such that $\sum x_i = 0$ and $\sum |x_i| > 0$. Let $k < n$ be a positive integer. A sample of size $k$ is drawn uniformly at random without replacement, and $X_P$ denotes the sum of the sampled elements.

The authors address the question of finding a sharp lower bound on the Shannon entropy $H(X_P)$. This inquiry is framed as an "entropic analogue" of the Manickam-Miklós-Singhi (MMS) conjecture. The classical MMS conjecture (Conjecture 1) posits that for $n \ge 4k$, the probability $P(X_P \ge 0) \ge k/n$. A refined version (Conjecture 2 by Aydinian and Blinovsky) suggests that the minimal probability $P(X_P \ge 0)$ is achieved by specific "extreme" populations consisting of $i$ positive values and $n-i$ negative values, where the values are scaled to maintain a zero mean. The authors seek to determine if a similar extremal principle holds for Shannon entropy.

Methodology
The paper employs two distinct methodological approaches to establish lower bounds on $H(X_P)$:

1. Sperner Theory and Majorization:

   • The authors define a "sign-split poset" $Q = (\binom{[n]}{k}, \le)$ associated with the population $P$. The elements of the poset are $k$-subsets of indices, ordered based on the inclusion of their intersections with the set of non-negative indices ($A$) and negative indices ($B$).
   • They prove that this poset possesses the Strong Sperner Property (Lemma 2) by demonstrating it is a "normal poset" (satisfying the Normalized Matching Property).
   • A key observation (Lemma 1) is that the collection of subsets yielding a specific sum value forms an antichain in this poset.
   • Leveraging the Strong Sperner Property, the authors show that the probability mass function (PMF) of $X_P$ is majorized by the PMF of a hypergeometric random variable $H_i \sim \text{Hyp}(n, i, k)$ for some $i \in [n-1]$ (Lemma 3).
   • Since Shannon entropy is a Schur-concave function, the majorization relationship implies $H(X_P) \ge H(H_i)$.

2. Elementary Entropic Argument:

   • A second proof of the main inequality avoids Sperner theory and majorization. It draws inspiration from Lubell's proof of the LYM inequality.
   • The approach involves constructing a random maximal chain in the sign-split poset using random permutations of the positive and negative elements.
   • By showing that the mapping from the rank of a selected subset in the chain to its sum is injective, the authors demonstrate that sampling $X_P$ is equivalent to sampling a hypergeometric variable $H_i$ and applying a strictly increasing transformation.
   • Using the property that conditioning does not increase entropy, they derive $H(X_P) \ge H(H_i)$.

Key Results

• Theorem 2 (Entropic Aydinian-Blinovsky Conjecture): For any non-trivial zero-mean population $P$, the entropy of the sample sum satisfies:
  $$H(X_P) \ge \min_{i \in [n-1]} H(H_i)$$
  where $H_i \sim \text{Hyp}(n, i, k)$. This establishes that the "extreme" populations defined by Aydinian and Blinovsky (those with $i$ positive and $n-i$ negative values) are also the minimizers of entropy.

• Theorem 1 (Main Result): The authors solve the minimization problem over $i$. They prove that the minimum entropy is achieved when $i=1$ (or symmetrically $i=n-1$), corresponding to the population $P = \{1, -\frac{1}{n-1}, \dots, -\frac{1}{n-1}\}$.
  $$H(X_P) \ge H(\text{Ber}(k/n))$$
  where $\text{Ber}(k/n)$ is a Bernoulli random variable with mean $k/n$. The inequality is sharp and equality holds for the population described above.

• Theorem 3 (Littlewood-Offord-type Result): As a byproduct of the majorization argument, the paper establishes a bound on the maximum point probability (the mode) of $X_P$:
  $$\sup_{x \in \mathbb{R}} P(X_P = x) \le \max_{i \in [n-1]} P(H_i = m_i)$$
  where $m_i$ is a mode of the hypergeometric variable $H_i$.

Significance and Claims
The paper claims to provide the first entropic analogue of the MMS conjecture. Its significance lies in:

1. Bridging Fields: It connects combinatorial design theory (specifically the MMS conjecture and Johnson scheme invariants) with information theory (Shannon entropy).
2. Extremal Principle: It confirms that the populations which minimize the probability of a non-negative sum (in the context of the Aydinian-Blinovsky conjecture) also minimize the Shannon entropy of the sum.
3. Methodological Contribution: The work demonstrates the utility of Sperner theory and majorization in deriving entropy inequalities for sums of dependent random variables (sampling without replacement), a setting distinct from previous applications involving independent variables.
4. Generalizability: The authors note that their majorization-based approach (Lemma 3) applies to any Schur-concave function of the PMF, suggesting potential extensions to Rényi entropy (Corollary 5), though the specific minimization for general $\alpha$ remains an open numerical problem.

The paper does not claim to resolve the original MMS conjecture (regarding probabilities) but rather establishes a parallel, rigorous result for entropy, providing a new perspective on the extremal behavior of sampling sums.