CS Paper Radar

Separating Abelian and Homomorphic Entropy Cones

Shahram Khazaei

cs.IT ·submitted 2026-08-10 12:41 UTC · v1
theory

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.

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.64
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

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.62
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

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.61
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

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

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

A Counterexample to the Gyarmati-Matolcsi-Ruzsa Conjecture

cs.IT math.CO ·2026-10-30 ·Chandra Nair, Aref Namayandeh, Zhaobang Zhu
similarity 0.55
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

Almost Tight Bounds for Isomorphism Testing and Basis Construction in Finite Abelian Groups

cs.DS math.GR ·2026-10-06 ·Nader H. Bshouty
theory similarity 0.51
Abstract

We study isomorphism decision and basis construction for finite Abelian groups of known order $n$. We measure complexity by the number of additions performed in the groups and by the total running time. We give a randomized isomorphism decision algorithm that performs $\tilde O(n^{1/4})$ group additions and runs in $\tilde O(n^{1/4})$ time. This improves the $\tilde O(\sqrt n)$ upper bound of Chen and Fu and matches Bshouty $Ω(n^{1/4})$ lower bound up to polylogarithmic factors. We also prove that finding a basis with success probability at least $2/3$ requires $Ω(\sqrt n)$ group additions in the worst case. This matches the $\tilde O(\sqrt n)$ upper bound of Chen and Fu up to polylogarithmic factors. These results separate isomorphism decision from basis construction in finite Abelian groups: their optimal worst-case complexities are $\tildeΘ(n^{1/4})$ and $\tildeΘ(\sqrt n)$, respectivel

0.11

Axioms for relative entropy

cs.IT math.OAhep-thmath-ph ·2026-11-16 ·Roberto Longo
similarity 0.51
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.40

Random Non-Commutative Error-Correcting Codes

cs.IT math.GR ·2026-10-28 ·Michael Best, Alexander Lubotzky
similarity 0.51
Abstract · 18 pages, 1 table

Chapman, Dinur, and Lubotzky recently introduced the theory of non-commutative error-correcting codes, generalizing classical coding theory to arbitrary groups via $δ$-robust subsets used to detect proper subgroups. Building on this foundation, this paper systematically studies an analogue of random codes for arbitrary groups, exploring the extent to which the classical Gilbert-Varshamov (GV) bound holds in this non-commutative setting. While random universal codes of linear size in free groups are shown to be asymptotically bad, we establish a complete characterization for general families of finite groups. Specifically, a family of finite groups admits good random codes (forming a GV family) if and only if it exhibits uniform polynomial maximal-subgroup growth. Furthermore, we provide explicit quantitative bounds on the rate and optimal distance range based on intrinsic parameters, proving that families of finite solvable groups always form GV families and determining the exact probabilistic rate for direct powers of a fixed finite simple group.

0.25