CS Paper Radar

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

Chandra Nair, Aref Namayandeh, Zhaobang Zhu

cs.IT math.CO ·submitted 2026-10-08 09:55 UTC · v1

Abstract

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.

Comment
12 pages

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.IT ·2026-09-28 ·Harold Nieuwboer, Lubashan Pathirana
similarity 0.73
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

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

cs.IT ·2026-09-18 ·Haoran Wang
theory similarity 0.67
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.66
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

A Counterexample to the Gyarmati-Matolcsi-Ruzsa Conjecture

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

We provide a counterexample to the non-abelian Gyarmati-Matolcsi-Ruzsa conjecture. The construction comes from an equivalent maximal-coupling entropy inequality, for which a counterexample can be found in a lower-dimensional group. We give an explicit cardinality counterexample in $D_4^{14}$, the fourteenth direct power of the dihedral group of order $8$.

0.48

Separating Abelian and Homomorphic Entropy Cones

cs.IT ·2026-08-10 ·Shahram Khazaei
theory similarity 0.61
Abstract

Chan and Yeung showed that finite groups suffice to determine which homogeneous linear information inequalities are universally valid. We compare two restricted group-characterizable entropy cones: the Abelian cone $\widetildeΓ^{\mathrm{Abl}}_n$ and the homomorphic cone $\widetildeΓ^{\mathrm{Hom}}_n$, the latter generated by coset systems of normal subgroups. We prove \[ \widetildeΓ^{\mathrm{Abl}}_{16}\subsetneq\widetildeΓ^{\mathrm{Hom}}_{16}, \] and, if $n_{\rm AH}$ is the least number of variables for which these cones differ, we show $6\le n_{\rm AH}\le16$. The separating functional is a class-restricted entropy inequality: it is valid on the Abelian cone but is not a universal information inequality. It is obtained by lifting the order dual of the Pálfy--Szabó six-cross identity while quantifying errors at inexact subgroup joins. We then construct sixteen normal subgroups of a class-two $2$-group of order $2^{43}$ for which every join error vanishes while the endpoint containment fails by one bit. Since mixed-linear random variables are Abelian, the same example also separates the mixed-linear and homomorphic entropy cones.

0.04

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

cs.IT math.PRmath.CO ·2026-08-31 ·Ziran Liu
theory similarity 0.58
Abstract · 62 pages

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.

0.17

Axioms for relative entropy

cs.IT math.OAhep-thmath-ph ·2026-11-16 ·Roberto Longo
similarity 0.57
Abstract · 27 pages

For normal states of arbitrary von Neumann algebras, we characterize positive finite multiples of Araki relative entropy among non-degenerate divergences. The axioms are monotonicity under normal unital completely positive maps, tensor additivity, superadditivity for product second states, and separate lower semicontinuity in the predual norm. Alternatively, a conditional-expectation identity replaces the two tensor assumptions. The proof uses order bounds and asymptotic estimates on tensor powers. An appendix proves the known analytic estimates needed here, using standard modular theory and Haagerup L^p spaces. We also obtain the corresponding characterization in the C* algebraic setting.

0.41

On Han- and Shearer-Type Information Inequalities: Equality Conditions and Combinatorial Applications

cs.IT ·2026-10-13 ·Gunank Jakhar, Gowtham R. Kurri, Suryajith Chillara, Vinod M. Prabhakaran
similarity 0.56
Abstract · 17 pages, 2 figures

Madiman and Tetali established strong and weak fractional inequalities that subsume classical entropy subset inequalities such as Han's inequality and Shearer's lemma. In this work, we derive a decomposition of the gap in the strong fractional inequality and use it to establish the necessary and sufficient conditions for equality in the strong form of Han's inequality. As a consequence, we characterize the equality conditions for a strong Loomis-Whitnet-type projection inequality of Balister and Bollobas (2012). Finally, we apply the weak fractional inequality to an extremal graph theory problem, recovering and extending results of Sason (2022) and Boucheron et al. (2013), whose approaches rely on Han's inequality.

0.37