PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Harold Nieuwboer, Lubashan Pathirana

arXiv:2609.35451v1cs.ITmath.IT

TL;DR

A direct proof of the group-theoretic Zhang–Yeung inequality had remained open. This paper proves it using elementary group-theoretic and counting arguments, providing the direct proof sought.

  • Problem

    A direct proof of the subgroup-cardinality translation of the Zhang–Yeung inequality remained an open problem.

    Source: §1 · p. 2

  • Method

    The proof uses exact counting of multiplication fibers and elementary linear algebraic results on the group algebra C[G].

    Source: §1 · p. 3

  • Results

    The paper resolves the open problem with a direct proof of the group-theoretic Zhang–Yeung inequality.

    Source: §1 · p. 2, §3 · p. 6

  • Takeaways & Limitations

    The argument establishes the subgroup-cardinality inequality through an elementary proof that does not appear to rely on the usual copy construction.

    Source: §1 · p. 3, §3 · p. 6

    The group-theoretic copy construction leaves the Chan–Yeung setting because its sample space is not generally a group, and iterative copying can lead to non-uniform distributions.

    Source: §1 · p. 3

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames the search for entropy inequalities beyond Shannon’s and presents the Zhang–Yeung inequality as a four-variable example. It then states the paper’s contribution: a direct, elementary proof of its group-theoretic translation.

1 Introduction

  • The introduction motivates the problem by asking which relations hold among joint-variable entropies, beyond Shannon’s inequality.Conditional mutual information I(A : C|B) is non-negative, an equivalent form of the submodularity inequality.Source: §1 · p. 1
  • The entropic vector records the joint entropy H(XI) for each subset I of the variables, with H(X∅) = 0.The set of entropic vectors is denoted Γ∗n; for n ≥ 3 it is not closed, although its closure is a convex cone characterized by linear inequalities.Source: §1 · p. 1
  • For n ≥ 4, valid linear inequalities for the entropic cone exist that cannot be derived from Shannon-type inequalities.Characterizing the full set of such inequalities remains open.Source: §1 · p. 1
  • The Zhang–Yeung inequality is valid for four finite-outcome discrete random variables and cannot be derived from Shannon-type inequalities.It states that 2I(X3 : X4) ≤ I(X1 : X2) + I(X1 : X3X4) + 3I(X3 : X4|X1) + I(X3 : X4|X2).Source: §1 · p. 1
  • Chan and Yeung translate linear entropy inequalities into multiplicative inequalities on subgroup cardinalities, with the converse also holding.Subgroups G1, . . . , Gn yield variables Xi = gGi from uniform g ∈ G; joint entropies correspond to subgroup intersections.Source: §1 · p. 2
  • The paper gives a direct elementary proof of the group-theoretic Zhang–Yeung inequality, an open problem previously noted by Chan–Yeung [CY02, Ex. 5.2] and Yeung [Yeu25].The proof uses exact counting of multiplication fibers and elementary linear algebra on the group algebra C[G].Source: §1 · pp. 2–3
  • A group-theoretic copy construction samples pairs (g, h) with gG1 = hG1 to obtain a copy variable R while preserving the relevant marginal distribution.The construction has limits: its sample space is generally not a group, and iterative copying can require non-uniform distributions.Source: §1 · pp. 2–3
  • The authors’ proof does not appear to use the copy lemma, unlike known proofs of the Zhang–Yeung inequality based on copying and Shannon-type inequalities.The copy lemma constructs a variable with a specified matching marginal and conditional independence property.Source: §1 · pp. 2–3

2 Preliminaries

The preliminaries develop counting and group-algebra tools for proving subgroup cardinality inequalities. Averaging operators yield projection and trace properties, while counting multiplication fibers supports the ensuing corollaries.

2 Preliminaries

  • For any subset X of G, counting pairs with product in X relates |HK ∩ X| to |H ∩ K|.The set X need not be a subgroup.Source: §2 · p. 3
  • Counting products in HK shows that each fiber of the multiplication map H × K → G over HK has size |H ∩ K|.The proof parametrizes every pair with a fixed product using an element of H ∩ K.Source: §2 · p. 3
  • For a subgroup H, Φ_H is a self-adjoint orthogonal projection onto C[G]^H with trace |G|/|H|.Its image consists of vectors invariant under left multiplication by H.Source: §2 · p. 4
  • If L ≤ M, operator monotonicity and nonnegative traces give a subgroup cardinality inequality in Corollary 2.1.The proof combines operator monotonicity with positivity of traces of products of positive semidefinite operators.Source: §2 · p. 4
  • When H, K ≤ L, the same operator and trace argument yields the subgroup cardinality inequality in Corollary 2.2.The corollary is stated for H and K contained in L.Source: §2 · p. 4

3 The proof of the Zhang–Yeung inequality

The proof bounds a set of subgroup-product quadruples and develops lower bounds for an intersection that is not itself a subgroup. Applying the auxiliary lemmas in succession, then bounding the final intersection by |G3G4|, gives the group-theoretic Zhang–Yeung inequality.

3 The proof of the Zhang–Yeung inequality

  • The set E counts quadruples from G13 × G14 × G23 × G24 whose middle product lies in G3G4, and its size is upper-bounded using |G1G2 ∩ G3G4|.For fixed z, the proof counts possible (p, q) with pq = z, then bounds the choices of (a, b) and (c, d).Source: §3 · p. 5
  • The authors upper-bound |G1G2 ∩ G3G4| by |G3G4| = |G3||G4|/|G34|, but still need good lower bounds on |G14G23 ∩ G3G4|, which is not directly a subgroup cardinality.Source: §3 · p. 5
  • Lemma 3.2 uses a direct set inclusion followed by two applications of Corollary 2.1.The inclusion compares G14G23 ∩ G3G4 with G14G23 ∩ G3G14.Source: §3 · p. 5
  • Lemma 3.3 bounds a set built from G14G13 and G13G14 by placing its product with G34 inside G14G3 ∩ G3G4.The proof applies the multiplication-map counting lemma and Corollary 2.2, then rearranges the resulting inequalities.Source: §3 · p. 5
  • Bounding |G1G2 ∩ G3G4| by |G3G4| completes the derivation of the group-theoretic Zhang–Yeung inequality.The proof applies Lemmas 3.1–3.3 in succession before this final estimate.Source: §3 · p. 6
Loading 2609.35451v1…