CS Paper Radar

Shannon's problem on the monotonicity of entropy and a Conjecture of Tao

Ziran Liu

cs.IT math.PRmath.CO ·submitted 2026-08-31 21:31 UTC · v1
theory

Abstract

Let $X_1,X_2,\ldots$ be i.i.d. finitely supported random variables in a torsion-free abelian group, and write $S_k=X_1+\cdots+X_k$, and $H(S_k)$ is the Shannon entropy $S_k$, for all $k \ge 1$. We prove that, for every fixed $n\geq1$, \[ H(S_{n+1})-H(S_n) \geq \frac12\log\frac{n+1}{n} -o_{H(X_1)\to\infty}(1), \] uniformly over the ambient group and the input law. This proves a conjecture of Tao [29] in 2010.

Comment
62 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Sharp High-Entropy Bounds for Sums of Independent Discrete Random Variables

cs.IT ·2026-09-18 ·Haoran Wang
theory similarity 0.76
Abstract

Sharp high-entropy lower bounds for the entropy of a sum were known for identically distributed summands in torsion-free abelian groups and in prime cyclic groups. For arbitrary independent summands, Gavalakis, Goh and Kontoyiannis obtained an additive constant of $1/8$ and conjectured that the sharp constant is $1/2$. We prove that independent discrete random variables $X,Y$ with finite Shannon entropies satisfy $H(X+Y)\ge (H(X)+H(Y))/2+1/2-o(1)$ in every torsion-free abelian group as $\max{H(X),H(Y)}\to\infty$. The same conclusion holds in the prime cyclic group $\mathbb F_p$ when both $\max{H(X),H(Y)}$ and $\log_2 p-\max{H(X),H(Y)}$ tend to infinity. We give explicit error bounds in both settings. The proof extracts a component with paired point probabilities while controlling the entropy of the remainder independently of its support. Discrete rearrangement and uniform perturbation then transfer the continuous entropy power inequality to this component. In prime cyclic groups, an additional estimate controls the entropy lost under modular reduction. Binomial distributions show that the constant $1/2$ is optimal.

0.14

Entropy power inequalities in compact groups

cs.IT math.PRmath.CO ·2026-08-23 ·Lampros Gavalakis, Ioannis Kontoyiannis, Sharang M. Sriramu, Aaron Wagner
similarity 0.68
Abstract · 22 pages, no figures

Suppose $X,Y$ are independent random variables with values in a compact abelian group $(G,+)$. We examine the following two entropy power-type inequalities: $h(X+Y)\geq \frac{1}{2}h(X)+\frac{1}{2}h(Y)$ and $h(X+Y)\geq \max\{h(X),h(Y)\}$, where the entropy $h(Z)$ of a $G$-valued random variable $Z$ is defined in terms of its density with respect to Haar measure on $G$. For groups that are either connected or finite with no nontrivial subgroups, we precisely characterize the cases of equality and establish explicit, quantitative stability estimates in terms of relative entropy for these two inequalities. The main tools are a generalization of an entropic inequality obtained by Green, Manners and Tao (2023) for discrete entropy, and a harmonic-analytic estimate for the chi-squared contraction coefficient in connected compact groups. As an application, we derive exponential convergence rates to the uniform distribution in relative entropy for random walks on connected compact abelian groups.

0.38

Sharp Rogers--Shephard Inequalities for Rényi Entropy

cs.IT math.PRmath.MG ·2026-10-11 ·Bang-Xian Han, Guoqing Zhan, Chiyu Zhou, Zhuo-Nan Zhu
theory similarity 0.62
Abstract · 29 pages; comments are welcome!

We establish sharp weighted Rogers--Shephard inequalities for Rényi differential entropy. For independent copies $X,X'$ of a log-concave random vector in $\R^n$, we prove $h_p(aX-bX')\le h_p(X)+n\log(a+b)$ for all $a,b>0$ and $1\le p\le\infty$, where orders $1$ and $\infty$ correspond to Shannon entropy and min-entropy, respectively. The Shannon case settles the entropic Rogers--Shephard conjecture of Madiman and Kontoyiannis and its higher-dimensional formulation. For $1\le p<\infty$, equality holds precisely for invertible affine images of random vectors with independent exponential coordinates. At $p=\infty$, the larger equality class is characterized by possibly extended-valued convex potentials that are positively homogeneous of degree one. For every $0<p<1$, uniform laws on sufficiently high-dimensional simplices violate the unweighted bound. Thus $p=1$ is the critical order for this bound to hold in every dimension. The proof combines weighted convex intersections with an exponential lift to a log-affine probability density. At the Shannon endpoint, this lift yields an exact deficit decomposition with a conditional mutual information term for an additive channel with asymmetric Laplace noise.

0.43

Improved Bounds for the Entropic Central Limit Theorem in the Log-Concave Case

cs.IT math.PR ·2026-10-22 ·Tom Maitre
theory similarity 0.61
Abstract

Let $μ$ be a log-concave isotropic probability measure on $R^d$ , and let $μ^n$ denote the law of the normalized sum of $n$ independent random vectors with law $μ$. We prove that \[ H(μ^n|γ)\leq \frac{C}{n} \min\left\{1+\log(ed)^2H(μ|γ)\ ,\ d\right\}. \] Compared to the previous best known bound, our estimate replaces the polynomial dependence on the dimension by a polylogarithmic one. The proof relies on a new combination of the De Bruijn identity with Eldan's stochastic localization process.

0.11

A simple proof of the group-theoretic Zhang-Yeung inequality

cs.IT ·2026-09-28 ·Harold Nieuwboer, Lubashan Pathirana
similarity 0.61
Abstract · 7 pages

Zhang and Yeung (IEEE Trans. Inf. Theory, 1998) established the first non-Shannon-type inequality that holds for all entropic vectors. Chan and Yeung (IEEE Trans. Inf. Theory, 2002) showed that there is a one-to-one relation between linear entropy inequalities and multiplicative inequalities involving cardinalities of subgroups of a finite group. The Shannon inequality admits a simple proof in the group theoretic setting, but a direct proof of the translation of Zhang--Yeung's inequality to the group-theoretic setting remained elusive. We resolve this open problem, giving a direct proof of the group-theoretic Zhang--Yeung inequality for cardinalities of subgroups of finite groups, using elementary group-theoretic and counting arguments.

0.18

Entropic Inequalities and Limit Theorems in Boolean Probability

cs.IT math.PR ·2026-10-14 ·Kewei Pan
theory similarity 0.58
Abstract

We study Boolean entropy and Fisher information in information inequalities and the Boolean central limit theorem. We prove a fractional Stam inequality for the Boolean Fisher information associated with arbitrary fractional partitions of subset sums, and derive an entropy power inequality for sums of Boolean independent random variables and its weighted version. We then establish a Boolean analogue of Barron's entropy convergence result along the Boolean central limit theorem: Boolean entropy converges to the entropy of the Rademacher law if and only if the initial entropy is finite. Furthermore, under a finite fourth moment, in the Boolean central limit theorem, we obtain \[ Γ(μ_n\mid\mathbf b)= \frac{m_4(μ)-1-m_3(μ)^2}{2}\frac{\log n}{n} +o\!\left(\frac{\log n}{n}\right), \] with an explicit example showing sharpness. For symmetric laws with finite fourth moment and finite Boolean Fisher information, \[ Ψ(μ_n\mid\mathbf b) =2\bigl(m_4(μ)-1\bigr)\frac{\log n}{n} +o\left(\frac{\log n}{n}\right). \] Our approach is based on the Nevanlinna representation of Cauchy transforms.

0.27

From an entropic inequality for sums in abelian groups to the theorems of Ruzsa and Plünnecke

cs.IT math.CO ·2026-10-08 ·Chandra Nair, Aref Namayandeh, Zhaobang Zhu
similarity 0.58
Abstract · 12 pages

We give a direct information-theoretic proof of the Plünnecke--Ruzsa inequalities for finite subsets of abelian groups. The argument rests on an elementary coupling inequality proved by maximizing joint entropy, without tensor powers or asymptotic constructions. It also yields Ruzsa's sumset triangle inequality and an extension to non-abelian groups.

0.13

Gap Entropy and Almost Instance-Wise Optimal Best-Arm Identification

cs.CC cs.AIcs.LG ·2026-09-12 ·Jiarui Yao, Jiaxi Zhao, Xiangxin Zhou
theory similarity 0.58
Abstract

In the best-arm identification problem, we are given $n$ stochastic arms with unknown means and wish to identify the arm with the largest mean with probability at least $1-δ$, using as few samples as possible. We consider independent Gaussian rewards with unit variance and means in $[0,1]$. Chen and Li [2016] conjectured that the instance-wise sample complexity of this problem is characterized by the gap entropy, up to an additive term arising from the two-arm problem. In this paper, we resolve their gap-entropy and almost instance-wise optimality conjectures. For an instance $I$, let $Δ_{[i]}$ be the gap between the largest and the $i$-th largest mean, let $H(I)=\sum_{i=2}^{n}Δ_{[i]}^{-2}$, and let Ent$(I)$ denote the entropy of the normalized complexities of its dyadic gap groups. For every $0<δ<0.1$, we show that the order-oblivious instance-wise lower bound is $ Θ (H(I)[\log(1/δ)+Ent(I)]). $ We also give a single $δ$-correct algorithm with expected sample complexity $ O ( H(I)[\log(1/δ)+Ent(I)] +D\log(e+\log(e+D))),D=Δ_{[2]}^{-2}, $ without prior knowledge of the gaps. Our lower bound removes the dyadic-gap and monotonicity restrictions of previous work, and our upper bound removes the additional polylogarithmic factor multiplying the two-arm term. Thus, a single algorithm attains the instance-wise lower bound up to an additive two-arm term. The main theorems have been formalized and proved in Lean 4.

0.17