Discrete Entropy Power Inequalities via Sperner Theory∗

arXiv:1712.00913v2 [math.CO] 17 Dec 2017

Mokshay Madiman†, Liyao Wang‡and Jae Oh Woo§
December 19, 2017

Abstract
A ranked poset is called strongly Sperner if the size of k-family cannot exceed the sum
of k-largest Whitney numbers. In a sense of function ordering, a function f is (weakly)
majorized by g if the the sum of k-largest values in f cannot exceed the sum of klargest values in g. Two definitions arise from different contexts, but each share a strong
similarity with each other. Furthermore, the product of two weighted posets assumes
a structural similarity with a convolution of two functions. Elements in the product
of weighted posets with ranks capture underlying structures of the building blocks in
the convolution. Combining all together, we are able to derive several types of entropy
inequalities including discrete entropy power inequalities, and discuss more applications.

1

Introduction

Entropy power inequality plays one of the most important roles in proving coding theorems, or
finding channel capacities in Information Theory [1, 24, 5]. It also has close connections with
Probability Theory, or Convex Geometry [12]. We can formulate entropy power inequality
in two different types. The original formulation, which was suggested by Shannon [17] and
proved by Stam [18], is the following. For two independent random variables X and Y in Rd ,
2

2

2

e d h(X+Y ) ≥ e d h(X) + e d h(Y ) ,
where h(X) means the Shannon entropy of X. We can interpret the inequality as a superadditive entropy power with respect to the sum of two independent random variables. Another equivalent sharp lower bound formulation is also available such that
∗
h(X + Y ) ≥ h(ZX
+ ZY∗ ),
∗ and Z ∗ are two independent Gaussian distributions with h(X) = h(Z ∗ ) and
where ZX
Y
X
h(Y ) = h(ZY∗ ) [22].
Two types of entropy power inequalities stated above focus on the continuous domain. On
the other hand, we still have limited understanding on the discrete entropy power inequality
∗
Some portions of this paper were presented by the authors at the IEEE International Symposia on Information Theory in 2014 and 2015 [23, 25].
†
Department of Mathematical Sciences, University of Delaware, Newark DE 19716. Email: madiman@udel.edu
‡
J. P. Morgan Chase, New York. Email: njuwangliyao@gmail.com
§
Department of Mathematics, and Department of Electrical and Computer Engineering, The University of
Texas at Austin. Email: jaeoh.woo@gmail.com

1

on discrete domains such as integers, or cyclic groups. One of the main difficulties is that
useful analytic tools in the continuous domain cannot be naturally translated into the discrete
domain. For example, one can derive Entropy power inequality from sharp Young’s inequality
[21, 11]. But a non-trivial sharp discrete Young’s inequality is unknown.
Nonetheless, it is a natural and an interesting question to find a fully general discrete
entropy power inequality [9, 8, 6, 23, 25]. We established the lower bound of the entropy
of sums in prime cyclic groups including integers based on rearrangement inequalities and a
functional ordering by majorization in our companion paper [13]. In this paper, we focus on
the integer or the integer lattice domain and we continue to exploit the idea of majorization.
But instead of establishing rearrangement inequalities, we take a different path to establish
the lower bound of the entropy of sums in integers.
In our approach, we establish the similarity between the strongly Sperner property of
posets and the functional ordering by majorization. The Sperner property of a poset and the
anti-chain argument are originated from Erdös [3].
Our Contributions. Our main contributions in this paper are the following. We first
extend the Erdös’s anti-chain observation in Sperner poset to strongly Sperner poset. Next
we establish the close similarity between the convolution of two functions and the product
of two posets. Finally, we prove that the strongly Sperner poset can be re-translated into
majorization in a sense of function ordering. Then by following our previous approaches
[22, 23, 13], we prove several types of entropy inequalities including discrete entropy power
inequalities, and discuss more applications.
Notations and Basic Lemma. Throughout this paper, we will use three major notations
to describe our main results. First, we define the notion of a #-log-concave function. The
definition of the functional #-log-concavity is originally motivated by weighted posets with
log-concave Whitney numbers. Details are explained in Section 4 below
Let f : Z → R+ be a nonnegative function over integer such that Supp(f ) = {x0 , · · · , xn }
with x0 < · · · < xn . For the purpose of the consistency with the rank of the partially ordered
set, the starting index is chosen to be 0 instead of 1. So |Supp(f )| = n + 1. As we used the
same notation in [13], we ambiguously write a set to be an indicator function as well. For
example, f = 0.5{0, 3} means f (0) = f (3) = 0.5. Then we write
f=

n
X

ar {xr },

r=0

where ai ≥ 0 and x0 < · · · < xn . Given a non-negative function f , we define f # as
f # :=

n
X

ar {r}.

r=0

Then f # is supported on {0, · · · , n} with the same values of f . In other words, f # is a
squeezed rearrangement of f . We call f is #-log-concave if f # is log-concave, i.e., f # (i)2 ≥
f # (i − 1)f # (i + 1) for any i ∈ Z. Since ar = 0 for r ∈ Z \ {0, · · · , n}, it equivalently says
a2r ≥ ar−1 ar+1 . Similarly, we can extend the notion #-log-concavity to random variables
as well. We call a random variable X is #-log-concave if its probability mass function is
#-log-concave. We write X # given X with the probability mass function f if X # has the
probability mass function f # .

2

Secondly, we use a notion of a functional ordering, called majorization. Consider two realvalued functions f and g in Z. f [i] means the i-th largest value of f with allowing multiple
tie values. We write f ≺ g if for all k = 1, · · · , n − 1
k
X

f [i] ≤

k
X

g[i] ,

(1.1)

g[i] .

(1.2)

i=1

i=1

and
n
X

f [i] =

n
X
i=1

i=1

If f and g satisfy both conditions (1.1) and (1.2), we call f is majorized by g. Similarly
for random variables X and Y with probability mass functions f and g, we write X ≺ Y if
f ≺ g.
Thirdly, we explain the Rényi entropy which is a generalized entropy of the Shannon
entropy. The Rényi entropy of the order α ∈ (0, 1) and α ∈ (1, +∞) can be defined by
!
X
1
α
.
f (i)
log
Hα (X) =
1−α
i∈Z

For limiting cases of α, define
H0 (X) = log |supp(f )|,
X
H1 (X) =
−f (i) log f (i),
i∈Z

H∞ (X) = − log sup f (i).
i∈Z

These are consistent definitions by taking limits of Hα (X) for α ∈ (0, 1) and α ∈ (1, +∞).
So the Rényi entropy of order α ∈ [0, ∞] is well-defined. In particular, H1 (·) is same as the
Shannon entropy H(·).
We will also use the following Lemma.
Lemma 1.1. Assume that f and g are non-negative functions in Z and f ≺ g. For any
continuous convex function Φ : R → R with Φ(0) = 0,
X
X
Φ (f (i)) ≤
Φ (g(i)) .
i∈Z

i∈Z

Given a majorization, we can choose a convex function Φ(x) = −xα for α ∈ (0, 1),
Φ(x) = x log x for α = 1, and Φ(x) = xα for α ∈ (1, +∞). Then Rényi entropy inequalities
follow by using Proposition 1.1 and decorating terms into Rényi entropy.

2

Majorization Results for Sums of Discrete Random Variables

We focus on finitely many supported random variables over Z for concise discussion. We note
that, however, following the similar idea in [23], one can easily extend our main results to
infinitely many supported cases as well.

3

Our first main theorem is based on the strongly Sperner property of the product of
weighted chain posets. Details of strongly Sperner postes are discussed in the Section 4
below.
Theorem 2.1. If X1 , · · · , XN are independent and #-log-concave over Z,
#
X1 + · · · + XN ≺ X1# + · · · + XN
.

(2.1)

The next theorem below is based on the strongly Sperner property of the product of M (n)
posets. We assume that ai ’s are distinct positive real values. i.e. a1 6= a2 6= · · · =
6 an > 0.

Theorem 2.2. If Yi ’s are independent with Binomial mi , 12 for 1 ≤ mN ≤ mN −1 ≤ · · · ≤
m1 ,
a1 Y1 + a2 Y2 + · · · + aN YN ≺ Y1 + 2Y2 + · · · + N YN .

3
3.1

(2.2)

Applications with Discrete Entropy Power Inequalities
Generalized Hardy-Littlewood-Pólya type rearrangement inequality in
the integer

In our companion
 paper [13], we generalized Hardy-Littlewood-Pólya type rearrangement
inequality in Z pZ based on Lev’s set majorization [10]. Furthermore, as an application of
Theorem 2.1 above, we can also prove the set majorization for the integer case. For a finite
set A in Z, A# = {0, 1, · · · , |A| − 1} as we consider A as an indicator function.
Corollary 3.1. If A1 , A2 , · · · , An are finite sets (or indicator functions) in Z,
#
#
A1 ⋆ A2 ⋆ · · · ⋆ An ≺ A#
1 ⋆ A2 ⋆ · · · ⋆ An ,

where ⋆ represents a convolution operator.
Proof. We choose X1 , X2 , · · · , Xn as uniform distributions on A1 , A2 , · · · , An . By applying
Theorem 2.1 and re-normalizing the probability into the total number of points, the proof
follows.
Stating rearrangement inequality requires some basic notions of rearrangements as we did
in [13]. Let us consider a probability mass function f (x) : Z → R+ where R+ is the set of
non-negative real-values. We define f + given f by the rearrangement of f such that for any
positive z ∈ Z,
f + (0) ≥ f + (+1) ≥ f + (−1) ≥ · · · ≥ f + (z) ≥ f + (−z) ≥ · · · .
Similarly, we define f − given f by the rearrangement of f such that for any positive z ∈ Z,
f − (0) ≥ f − (−1) ≥ f − (+1) ≥ · · · ≥ f − (−z) ≥ f − (+z) ≥ · · · .
We also define f is △-regular if f + = f − . In this special case, we sometimes write either f +
or f − by f ∗ because both are the same. Equivalently, for any positive z ∈ Z,
f ∗ (0) ≥ f ∗ (+1) = f ∗ (−1) ≥ · · · ≥ f ∗ (z) = f ∗ (−z) ≥ · · · .

4

So f ∗ is completely symmetric and unimodal. Furthermore, we define -regular f if f + (z +
1) = f − (z) for any z ∈ Z. In other words, for any positive z ∈ Z,
f + (0) = f + (+1) ≥ · · · ≥ f + (−z) = f + (z + 1) ≥ · · · .
Then by following the same arguments in [13], Corollary 3.1 implies the generalized rearrangement inequality in the integer. We omit detailed proofs following two theorems.
Proposition 3.2 (Generalized rearrangement inequality in the integer). Let f and g be arbitrary nonnegative functions in Z. Assume h1 , h2 , · · · , hn are △-regular and s1 , s2 , · · · , s2m−1 , s2m
are -regular in Z,
f ⋆ g⋆h1 ⋆ h2 ⋆ · · · ⋆ hn ⋆ s1 ⋆ s2 ⋆ · · · ⋆ s2m−1 ⋆ s2m (0)
−
+
−
≤ f + ⋆ g − ⋆ h∗1 ⋆ h∗2 ⋆ · · · ⋆ h∗n ⋆ s+
1 ⋆ s2 ⋆ · · · ⋆ s2m−1 ⋆ s2m (0).

Accordingly, Theorem 3.2 implies the rearranged majorization in the integer case as well.
Proposition 3.3 (Generalized rearrangement majorization in the integer). Let f be an arbitrary probability mass function. Assume h1 , h2 , · · · , hn are △-regular and s1 , s2 , · · · , s2m−1 , s2m
are -regular,
f ⋆ h1 ⋆ h2 ⋆ · · · ⋆ hn ⋆ s1 ⋆ s2 ⋆ · · · ⋆ s2m−1 ⋆ s2m
−
+
−
≺ f +/− ⋆ h∗1 ⋆ h∗2 ⋆ · · · ⋆ h∗n ⋆ s+
1 ⋆ s2 ⋆ · · · ⋆ s2m−1 ⋆ s2m

where f +/− means that we can choose either f + or f − .

3.2

Lower bound formulation of discrete entropy power inequality

One of main applications from Theorem 2.1 and Theorem 2.2 is establishing the lower bound
of entropy of sums. Combining with Lemma 1.1 imply the following two different types of
entropy inequalities.
Proposition 3.4. If X1 , · · · , XN are independent and #-log-concave over Z,


#
.
Hα (X1 + · · · + XN ) ≥ Hα X1# + · · · + XN

(3.1)

Hα (a1 Y1 + a2 Y2 + · · · + aN YN ) ≥ Hα (Y1 + 2Y2 + · · · + N YN ) .

(3.2)


Proposition 3.5. Let 0 < a1 6= · · · =
6 aN . If Yi ’s are i.i.d. copies of Binomial m, 12 for
m ≥ 1,

3.3

Discrete Rényi entropy power inequality of uniform distributions in
the integer lattice Zd

In our previous work of [25], we proved the discrete entropy power inequality in the integer
Z. In the following lemma, we extend the Theorem II.2 of [25] for α = 1 case to any Rényi
entropy of order α ≥ 1. Proof of the lemma can be found in Section 7.
Lemma 3.6. If X and Y are independent uniformly distributed over finite sets A ⊂ Z and
B ⊂ Z respectively,
Nα (X + Y ) + 1 ≥ Nα (X) + Nα (Y ),
where Nα (X) = e(1+α)Hα (X) for α ≥ 1.

5

(3.3)

Next, we are able to extend the entropy power inequality in the integer case to the integer
lattice Zd as well.
Theorem 3.7. If X and Y are uniform distributions over sets A and B in Zd ,
Nα (X) + Nα (Y ) + 1 ≥ Nα (X + Y ),
where Nα (X) = e(1+α)Hα (X) .
Proof. We reduce the problem in Zd to the same problem in Z. Then by applying Lemma 3.6,
the proof follows.
Consider a point z = (z1 , · · · , zd ) in Zd where zi ≥ 0 for each i. Next, we choose a
sufficiently large number q ∈ N. If q is not big enough, we can choose arbitrarily large q
satisfying desired conditions explained below. We regard z as a q-ary representation of an
integer value. In other words,
z = (z1 , · · · , zd ) ≡ z1 q d−1 + z2 q d−2 + · · · + zd ∈ Z.

(3.4)

For the set A in Zd , we can shift A to have all points to be non-negative components. Then
we let A′ be the equivalent set in Z by using the q-ary representation (3.4). Similarly we can
find the B ′ in Z of B in Zd . So if q is sufficiently large, A ⋆ B can be regarded as A′ ⋆ B ′ in
Z. Let X ′ and Y ′ be uniform distributions on A′ and B ′ in Z, respectively. This implies
Hα (X + Y ) = Hα (X ′ + Y ′ ) ≥ Hα (X ′# + Y ′# ).
Then we apply Lemma 3.6 with Hα (X) = Hα (X ′ ) and Hα (Y ) = Hα (Y ′ ).
Theorem 3.7 suggests that a reasonable choice of the exponent c is still c = 1 + α for the
integer lattice Zd case unlike c = 1+α
d for the d-dimensional continuous random variable case.
The inequality is independent to the dimensional factor d. So one might want to develop a
proper dimensional discrete entropy power inequality in the integer lattice Zd by putting an
appropriate dimensional assumption:
Nαd (X) + Nαd (Y ) + 1 ≥ Nαd (X + Y ),
1+α

where Nαd (X) = e d H(X) . But the proper dimensional assumption is unclear to authors.
One may follow a dimensional assumption suggested by Garnder and Gronchi [4] when they
develop the discrete Brunn-Minkowski inequality. The main point of the dimensional assumption by Garnder and Gronchi [4] is that one point mass is assigned for each dimensional
direction. But we confirmed that the dimensional assumption in [4] is not sufficient to build
a proper dimensional discrete entropy power inequality in the integer lattice. We leave it as
an open question for future works.

3.4

Extension to Erdös-Moser Problem


Theorem 2.2 implies the entropy inequality of sums for Binomial m, 12 as a generalization
of Erdös-Moser Problem. Original Erdös-Moser problem is about Bernoulli distribution with
1
2.
Corollary 3.8. Let 0 < a1 6= · · · =
6 aN . For the case when α = +∞ in Theorem 3.5, we
have



mN (N + 1)
P (a1 Y1 + a2 Y2 + · · · + aN YN = k) ≤ P Y1 + 2Y2 + · · · + N YN =
2
6

We note that Nguyen proved that the optimal solution of the Erdös-Moser problem minimizes the variance [14]. More generally, our Corollary 3.5 implies that the optimal solution
of the Erdös-Moser problem minimizes the any order of Rényi entropy.

4

Backgrounds of Sperner Theory

In this section, we summarize basic backgrounds of Sperner Theory. Comprehensive materials
can be found in the books by Stanley [20] and Engel [2].

4.1

Partially ordered sets (poset)

A set S with a binary relation 4 is called a partially ordered if the relation 4 satisfies reflexive,
antisymmetric, and transitive properties, i.e., for any a, b, c ∈ S
• a 4 a (reflexive),
• if a 4 b and b 4 a, then a = a (antisymmetric),
• if a 4 b and b 4 c, then a 4 c (transitive).
In this case, we call S to be a partially ordered set, or a poset. For a, b ∈ S, a and b are
comparable if a 4 b or b 4 a. Otherwise, a and b are incomparable. A chain poset is a poset
if any two elements are comparable. A subset C of S is called a chain if C is a chain poset
as a subposet of S.
A subset A of S is called an antichain if any two distinct elements of A are incomparable.
A weighted poset is a poset such that each element has a positive weight. The weight function
w : S → R+ defines the weight of each element in S. We use a triple (S, w, 4) to represent
the weighted poset, but we sometimes describe S as a weighted poset without mentioning
the weight function w explicitly.
A chain C of S is called maximal if there is no larger chain C ′ such that C ⊆ C ′ . We
assume that every maximal chain of the poset S has length n. Then we call S to be a
graded poset with rank n. In this case, it turns out that S has a unique rank function
ρ : S → {0, 1, · · · , n} such that ρ(a) = 0 if a is a minimal element of S, and ρ(b) = ρ(a) + 1
if b covers a.

4.2

Normalized matching property

A weighted poset (S, w, 4) is called normal if for any antichain A which is a subset of elements
of rank i, the weight sum ratio of A with respect to the weighted Whitney number of rank
i is less than or equal to the weight sum ratio of the connected set of A at rank i + 1 with
respect to the weighted Whitney number of rank i + 1. There is a very useful property of the
product of weighted posets proved by Hsieh and Kleitman [7]. i.e.
w(∇(A))
w(A)
≤
w(Ni )
w(Ni+1 )
where Ni is a collection of elements at rank i, A ⊆ Ni is an antichain, w(A) is the weighted
sum of A, w(Ni ) is the weighted Whitney number of rank i, and ∇(A) is a collection of
elements at rank i + 1 connected to A (i.e. ∇(A) = {qi+1 ∈ Ni+1 : qi 4 qi+1 for each qi ∈ A}).

7

Proposition 4.1. A product of two normal posets with log-concave weighted Whitney numbers is again a normal poset with log-concave weighted Whitney numbers.
Proposition 4.2 (See [2, Corollary 4.5.3]). A normal poset is strongly Sperner.
Combining both, we can easily deduce the following.
Corollary 4.3. For each k ∈ {1, · · · , n}, assume that S(mk ) has log-concave Whitney numbers. Then the product of chain posets S(m1 , · · · , mk ) is strongly Sperner with log-concave
Whitney numbers.
Proof. Since the weight sum ratio of any antichain in a chain poset is always 1, any weighted
chain is normal. Then the conclusion follows from Proposition 4.1 and Proposition 4.2.
On the other hand, we will need to discuss an order isomorphism between two posets.
We will say that two posets (Q, 4) and (R, 4) are isomorphic if there exists a bijective map
ρ : Q → R such that q1 4 q2 iff ρ(r1 ) 4 ρ(r2 ).

4.3

Strongly Sperner posets

A product of chain posets S(m1 , · · · , mn ) can be defined to be a collection of n-tuples of
integers (a1 , · · · , an ) such that 0 ≤ ak ≤ mi for each k ∈ {1, · · · , n}. The relation a =
(a1 , · · · , an ) 4 b = (b1 , · · · , bn ) iff ak ≤ bk for each k ∈ {1, · · · , n}. Figure 1 shows an
example of the product poset S(2, 3).
We also introduce the poset M (n) which is defined as a n-tuples (a1 , · · · , an ) such that
0 = a1 = · · · = ak < ak+1 < · · · < an ≤ n with k ∈ {0, · · · , n} (if a1 > 0,P
k = 0). The relation
a = (a1 , · · · , an ) 4 b = (b1 , · · · , bn ) iff ai ≤ bi for all i. The rank ρ(a) = ni=1 ai . Stanley [19]
originally proved using the idea of algebraic geometry that M (n) is a rank-symmetric, rankunimodal, and strongly Sperner, then Proctor gave a more accessible proof [15]. In short,
we call that a ranked poset is Peck if it is a rank-symmetric, rank-unimodal, and strongly
Sperner.
Lemma 4.4 (See [19, 15]). A poset M (n) is a Peck poset.
Then Proctor, Saks, and Sturtevant proved that the Peck property is preserved under the
product.
Lemma 4.5 (See [16, Theorem 3.2]). A product of Peck posets is again Peck, so strongly
Sperner.

5

Proof of Theorem 2.1

We first establish the connection between a non-negative
Pn function and a weighted chain
poset. Let us consider a #-log-concave function f =
r=0 ar {xr } where x0 < · · · < xn
2
and ar ≤ ar−1 ar+1 . Then by simply letting Sf := Supp(f ) = {x0 , · · · , xn } with a weight
f (xr ) = ar , (Sf , f, ≤) forms a weighted chain poset. So we regard a non-negative function as
a weight chain poset:
f ≡ (Sf , f, 4),

8

(2, 3)
(2, 2) (1, 3)
(2, 1) (1, 2) (0, 3)

3
2
1

(2, 0) (1, 1) (0, 2)

2
×

0

1

=

(1, 0) (0, 1)
(0, 0)

0

Figure 1: Poset of S(2, 3)
where the relation 4 is the same as
≤. Since f is #-log-concave, Sf has log-concave
Pusual
n
#
Whitney numbers. Similarly f = r=0 ar {r} forms a weighted chain poset Sf # = {0, · · · , n}
with log-concave Whitney numbers. By our construction, Sf is isomorphic to Sf # by mapping
ρ(xr ) = r, so f (xr ) = f # (ρ(xr )).
Now assume that f1 , · · · , fN are #-log-concave. Let F (x(1) , · · · , x(N ) ) := f1 (x(1) ) · · · fN (x(N ) ).
# (N )
Similarly let F # (x(1) , · · · , x(N ) ) := f1# (x(1) ) · · · fN
(x ). As we have shown above, there exists an isomorphic map ρi between Sfi and Sf # for each i = 1, · · · , N . Then by constructing
i
a mapping ρ : Sf1 × · · · × SfN → Sf # × · · · × Sf # by
1
N

 

(1)
(N )
(N )
)
,
(5.1)
=
ρ
(x
),
·
·
·
,
ρ
(x
ρ x(1)
,
·
·
·
,
x
1
N
r1
rN
r1
rN
we see that Sf1 × · · · × SfN is isomorphic to Sf # × · · · × Sf # . i.e.
1
N


(Sf1 × · · · × SfN , F, 4) ≡ Sf # × · · · × Sf # , F # , 4 ,
1
N




(1)
(N )
(1)
(N )
where F xr1 , · · · , xrN = F # ρ1 (xr1 ), · · · , ρN (xrN ) .

Lemma 5.1. Sf # × · · · × Sf # forms a normal poset with log-concave Whitney numbers.
1

n

Proof. Since each Sf#i is a chain normal poset with log-concave weights, its product poset is
again a normal with log-concave Whitney numbers by Corollary 4.3.
Now let us move onto convolutions. We first define a level set

o
n
L[x] =
x(1) , · · · , x(N ) : x(1) + · · · + x(n) = x, x(i) ∈ Sfi for i = 1, · · · , N .

Lemma 5.2. ρ (L[x]) forms an antichain in Sf # × · · · × Sf # .
1

N



Proof. Suppose that there exist two distinct elements x := x(1) , · · · , x(N ) and y := y (1) , · · · , y (N )
such that x, y ∈ L[x] and x 4 y. This implies x(i) ≤ y (i) for each i = 1, · · · , N . Since x and
y are distinct, there exists some j such that x(j) < y (j) . Hence
x(1) + · · · + x(N ) < y (1) + · · · + y (N ) .
But this contradicts the fact that both x and y are in L[x].

9

12345

02345

01345
00345

01245

00245

01235

00145

00235

01234

00045

00135

00234

00035

00125

00134

00025

00034

00124

00015

00024

00123

00005

00014

00023

00004

00013

00003

00012
00002

00001

00000
Figure 2: Poset of M (5)

10

Since Sf # × · · · × Sf # is strongly Sperner, we are able to prove the majorization.
1

N

Proposition 5.3. If f1 , · · · , fN are #-log-concave probability mass functions,
#
f1 ⋆ · · · ⋆ fN ≺ f1# ⋆ · · · ⋆ fN
.

Proof. Let fL := f1 ⋆ · · · ⋆ fn and fR# := f1# ⋆ · · · ⋆ fn# . By the definition of the convolution,
X
fL (x) =
f1 (x(1) ) · · · fN (x(N ) ).
(x(1) ,··· ,x(N) )∈L[x]

Then by the isomorphism ρ in (5.1) and Lemma 5.2, fL (x) can be regarded as a sum of
weights of an antichain in Sf # × · · · × Sf # . Since Sf # × · · · × Sf # is normal poset by Lemma
1
1
N
N
5.1, Sf # × · · · × Sf # is strongly Sperner. Therefore
1

N

k
X

[i]
fL

≤

k
X

[i]

fR ,

i=1

i=1

where the left-hand side corresponds to the sum of k antichains and the right-hand side
corresponds to the sum of k largest Whitney numbers in Sf # ×· · ·×Sf # . Since for sufficiently
1
N
large M > 0
M
X
i=1

[i]

fL =

M
X

[i]

fR = 1,

i=1

the majorization follows immediately.
Then Theorem 2.1 is a random variable restatement of the above Proposition 5.3.

6

Proof of Theorem 2.2

We first assume that 0 < a1 < · · · < aN . Let Xi,j for 1 ≤ i ≤ N and 1 ≤ j ≤ mi ≤ N be
independent with Bernoulli 12 . We assume that 1 ≤ mN ≤ mN −1 ≤ · · · ≤ m1 . We also
define Yi ’s as follows:
Y1 := X1,1 + · · · + X1,m1 ,
..
..
.
.
YN := XN,1 + · · · + XN,mN .

Then Yi ’s are independent with Binomial mi , 21 for 1 ≤ mN ≤ mN −1 ≤ · · · ≤ m1 . Now
we denote by nj the number of defined Xi,j ’s for each 1 ≤ j ≤ N . Then we let Zj =
X1,j , · · · , Xnj ,j .
For each j, consider an element ij = (b1 , · · · , bnj ) in M (nj ). We encode bk = i > 0 for
some k in ij iff Xi,j = 1. For example, when nj = 5,
ij = (0, 0, 0, 2, 4)

iff

Zj = (X1,j = 0, X2,j = 1, X3,j = 0, X4,j = 1, X5,j = 0) .

Based on the correspondence introduced above, we are able to build a one-to-one and onto
correspondence between an element ij in M (nj ) and a realization of Zj . Furthermore, we are

11

able to construct an one-to-one and onto correspondence between an element (i1 , · · · , iN ) in
M (n1 ) × · · · × M (nN ) and each realization of (Z1 , · · · , ZN ).
Let Lj (Zj ) := a1 X1,j + · · · + anj Xnj ,j for each 1 ≤ j ≤ N . Then by the construction
YL : = a1 Y1 + · · · + aN YN = L1 (Z1 ) + · · · + LN (ZN ).
As we did in Section, we first define a level set Lj [xj ] in M (nj ) as follows
Lj [xj ] := {ij : corresponding Zj satisfies Lj (Zj ) = xj } .
Lemma 6.1. Lj [xj ] forms an antichain in M (nj ).
Proof. Suppose that there exist two distinct elements ij and i′j in Lj [xj ] such that ij 4 i′j .
Let’s say that ij and i′j correspond to Zj and Z′j , respectively. Since ij = (b1 , · · · , bnj ) and
i′j = (b′1 , · · · , b′nj ) are distinct, there should exist some k such that bk < b′k . If we let a0 = 0,
this implies abk < ab′k . So the correspondence immediately implies
Lj (Zj ) < Lj (Z′j ).
This contradicts that both ij and i′j are in Lj [xj ].
Similarly, we can also define a level set L[x] in M (n1 ) × · · · × M (nN )
L[x] := {(i1 , · · · , iN ) : corresponding (Z1 , · · · , ZN ) satisfies L1 (Z1 ) + · · · + LN (ZN ) = x} .
By using the same argument we did in Lemma 6.1, we can also prove that L[x] forms an
antichain. Because the idea is redundant, we omit the proof.
Lemma 6.2. L[x] forms an antichain in M (n1 ) × · · · × M (nN ).
On the other hand, by using Lemma, we can easily see that a product of posets M (n1 ) ×
· · · × M (nN ) is Peck, so strongly Sperner by Lemma 4.5.
Lemma 6.3. M (n1 ) × · · · × M (nN ) is strongly Sperner.
We note that |M (nj )| = 2nj , so |M (n1 ) × · · · × M (nN )| = 2n1 +···+nN . Then we can
interpret the probability as
P (YL = x) =

|L[x]|
2n1 +···+nN

.

In order to connect the strongly Sperner property with majorization, it is necessary to identify
the saturated case. When a1 = 1, · · · , aN = N , let
YR : = Y1 + · · · + N YN = R1 (Z1 ) + · · · + RN (ZN ),
where Rj (Zj ) := X1,j + · · · + nj Xnj ,j for each 1 ≤ j ≤ N . Then as Stanley and Proctor
explained before [19, 15], we can easily see that the size of each level set of Rj (Zj ) has a
bijective correspondence with a Whitney number of M (nj ). Hence each level set of YR has a
bijective correspondence with a Whitney number of M (n1 ) × · · · × M (nN ) as well by using
the property of the product of posets.

12

Now it remains to re-interpret the inequality below as the strongly Sperner property of
M (n1 ) × · · · × M (nN ):
X
X


P (YR ∈ C) ,
(6.1)
P (YL ∈ C) ≤ 2n1 +···+nN
sup
2n1 +···+nN
sup
C⊂N∪{0} |C|=k

C⊂N∪{0} |C|=k

where the left-hand side corresponds to the sum of k antichains in M (n1 ) × · · · × M (nN )
and the right-hand side exactly corresponds to the sum of k-largest Whitney numbers of
M (n1 ) × · · · × M (nN ). In a functional notation, by removing the constant term (2m1 +···+mN ),
the equation (6.1) is equivalent to the condition (1.1). The condition (1.2) obviously follows
using the fact that the total sum equals 1.
Next, we discuss the general case 0 < a1 6= · · · =
6 aN . In this case, we can reorder them
as 0 < aσ(1) < · · · < aσ(N ) using σ(·). By matching indices {σ(1), · · · , σ(N )} to {1, · · · , N }
in Xi,j , we can apply the same arguments as above. Even though we reorder indices, the
saturated case still remains the same. Therefore the proof follows for the general case as well.

7

Proof of Lemma 3.6

Since α = 1 case is previously proved in [25], we assume that α > 1. Since any uniform
distribution over a finite set is #-log-concave, by Theorem 3.4
Hα (X + Y ) ≥ Hα (X # + Y # ).
Then since Nα (X) = Nα (X # ) and Nα (Y ) = Nα (Y # ), if (3.3) is true
Nα (X + Y ) + 1 ≥ Nα (X # + Y # ) + 1
≥ Nα (X # ) + Nα (Y # )
= Nα (X) + Nα (Y ).
So it suffices to consider that A and B are a set of consecutive integers. Let |A| = n and
|B| = m. Since roles of X and Y are symmetric, we may assume that n ≥ m. It can be easily
shown by a direct calculation,
"m−1
#
X iα
1
1
Hα (X + Y ) =
log
+ (n − m + 1) α ,
1−α
mα n α
n
i=1

Hα (X) = log n,

Hα (Y ) = log m.

Let k = m/n. So k ∈ [0, 1]. First if m = 1, Hα (X + Y ) = Hα (X) and Hα (Y ) = 0. Then
Nα (X + Y ) + 1 = Nα (X) + 1 = Nα (X) + Nα (Y ).
Hence the inequality (3.3) is sharp. Next let
ξ(k, n) = 1 +

1
α
1
−
k−
k−α n−(1+α) .
n 1+α
1+α

13

In Hα (X + Y ), we look at the term inside log:
m−1
X
i=1

m−1
X
iα
1
−α −α
iα + n1−α − mn−α + n−α
+
(n
−
m
+
1)
=
n
m
mα n α
nα
Zi=1m
≤ n−α m−α
xα dx + n1−α − mn−α + n−α
1


α m
1 m−α
1
1−α
−
.
=n
1+ −
n 1+α n
1+α n

So we have a lower bound of the Rényi entropy of X + Y as

1 
Hα (X + Y ) ≥
log n1−α + log ξ(k, n) .
1−α
Then
1+α

Nα (X + Y ) = e(1+α)Hα (X+Y ) ≥ e(1+α) log n e 1−α log ξ(k,n) =: ν(k, n).
Since m = 1 case is already proved, if the following inequality is true, we are done.
1+α

ν(k, n) = e(1+α) log n e 1−α log ξ(k,n) ≥ e(1+α) log n + e(1+α) log kn = Nα (X) + Nα (Y ).
By rearranging terms, the above inequality is equivalent to
 1−α
ξ(k, n) ≤ 1 + k1+α 1+α .

When k = n2 , we can directly show the following inequality is true by elementary calculation:


 1−α
1−α1
2−α 1 
2
1+α
,n = 1 +
−
≤ 1 + 21+α n−(1+α)
.
ξ
n
1+αn 1+αn
Furthermore, it is easy to show that for k ∈ [0, 1] and α > 1


 1−α
1−α
1 + k1+α 1+α ≥ 1 − 1 − 2 1+α k.

Hence it remains to show



1−α
ξ(k, n) ≤ 1 − 1 − 2 1+α k


1−α
for all n ≥ 2 and k ≥ n3 . Let φ(k, n) := 1 − 1 − 2 1+α k − ξ(k, n). For a fixed n ≥ 2,

Then

∂φ
∂k

= 0 at


1−α
∂φ
α 
1 − k−(1+α) n−(1+α) .
= −1 + 2 1+α +
∂k
1+α
k∗ =

∗
and ∂φ
∂k > 0 for k > k and
easily show that

∂φ
∂k

h
i− 1
1−α
1−α
1
1 1+α
1+α
α
−1 + 2 1+α + 2 1+α α
,
n

< 0 for k < k∗ . Finally, by elementary calculation, we can
2
1
≤ k∗ < .
n
n

So for k ≥ n3 , φ(k, n) is minimized at k = n3 , and again by elementary calculation, we can
also check that φ n3 , n ≥ 0. Hence the proof follows.
We remark that when k = n2 , φ n2 , n < 0 for some n. So φ(k, n) ≥ 0 is proved for k ≥ n3 .
14

8

Conclusion

In this paper, we established the similarity between the convolution of two functions and the
product of two posets. Then, we prove that the strongly Sperner poset can be re-formulated
into majorization in a sense of function ordering. We also prove several types of entropy
inequalities including two types of discrete entropy power inequalities in the integer lattice,
and discuss extended rearrangement inequality, and generalized Erdös-Moser problems.

Acknowledgments
This work was supported in part by the U.S. National Science Foundation through grants
DMS-1409504 (CAREER) and CCF-1346564.

References
[1] Amir Dembo, Thomas M Cover, and Joy A Thomas. Information theoretic inequalities.
IEEE Transactions on Information Theory, 37(6):1501–1518, 1991.
[2] Konrad Engel. Sperner theory. Encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge, 1997.
[3] Paul Erdös. On a lemma of littlewood and offord. Bulletin of the American Mathematical
Society, 51(12):898–902, 1945.
[4] R Gardner and P Gronchi. A brunn-minkowski inequality for the integer lattice. Transactions of the American Mathematical Society, 353(10):3995–4024, 2001.
[5] Dongning Guo, Shlomo Shamai, Sergio Verdú, et al. The interplay between information
and estimation measures. Foundations and Trends® in Signal Processing, 6(4):243–429,
2013.
[6] Saeid Haghighatshoar, Emmanuel Abbe, and Emre Telatar. A new entropy power inequality for integer-valued random variables. In Information Theory Proceedings (ISIT),
2013 IEEE International Symposium on, pages 589–593. IEEE, 2013.
[7] W N Hsieh and DJ Kleitman. Normalized matching in direct products of partial orders.
Studies in Applied Mathematics, 52(3):285–289, 1973.
[8] Varun Jog and Venkat Anantharam. The entropy power inequality and mrs. Gerber’s
lemma for groups of order 2n. IEEE transactions on information theory, 60(7):3773–
3786, 2014.
[9] Oliver Johnson and Yaming Yu. Monotonicity, thinning, and discrete versions of the
entropy power inequality. Information Theory, IEEE Transactions on, 56(11):5387–
5395, 2010.
[10] Vsevolod F. Lev. Linear equations over Fp and moments of exponential sums. Duke
Mathematical Journal, 107(2):239–263, 2001.
[11] Jiange Li.
R\’enyi entropy power inequality and a reverse.
arXiv:1704.02634, 2017.

15

arXiv preprint

[12] Mokshay Madiman, James Melbourne, and Peng Xu. Forward and reverse entropy
power inequalities in convex geometry. In Convexity and Concentration, pages 427–485.
Springer, 2017.
[13] Mokshay Madiman, Liyao Wang, and Jae Oh Woo. Entropy inequalities for sums in
prime cyclic groups. Preprint, 2017.
[14] Hoi H Nguyen. A new approach to an old problem of erdős and moser. Journal of
Combinatorial Theory, Series A, 119(5):977–993, 2012.
[15] Robert A Proctor. Solution of two difficult combinatorial problems with linear algebra.
The American Mathematical Monthly, 89(10):721–734, 1982.
[16] Robert A Proctor, Michael E Saks, and Dean G Sturtevant. Product partial orders with
the sperner property. Discrete Mathematics, 30(2):173–180, 1980.
[17] C. E. Shannon. A mathematical theory of communication. Bell System Tech. J., 27:379–
423, 623–656, 1948.
[18] AJ Stam. Some inequalities satisfied by the quantities of information of fisher and
shannon. Information and Control, 2(2):101–112, 1959.
[19] Richard P Stanley. Weyl groups, the hard lefschetz theorem, and the sperner property.
SIAM Journal on Algebraic Discrete Methods, 1(2):168–184, 1980.
[20] Richard P. Stanley. Enumerative combinatorics. Volume 1, volume 49 of Cambridge
Studies in Advanced Mathematics. Cambridge University Press, Cambridge, second edition, 2012.
[21] Giuseppe Toscani. A strengthened entropy power inequality for log-concave densities.
IEEE Transactions on Information Theory, 61(12):6550–6559, 2015.
[22] Liyao Wang and Mokshay Madiman. Beyond the entropy power inequality, via rearrangements. Information Theory, IEEE Transactions on, 60(9):5116–5137, Sept 2014.
[23] Liyao Wang, Jae Oh Woo, and Mokshay Madiman. A lower bound on the renyi entropy
of convolutions in the integers. In Information Theory (ISIT), 2014 IEEE International
Symposium on, pages 2829–2833, June 2014.
[24] Hanan Weingarten, Yossef Steinberg, and Shlomo Shitz Shamai. The capacity region of
the gaussian multiple-input multiple-output broadcast channel. IEEE transactions on
information theory, 52(9):3936–3964, 2006.
[25] Jae Oh Woo and Mokshay Madiman. A discrete entropy power inequality for uniform
distributions. In Information Theory (ISIT), 2015 IEEE International Symposium on,
pages 1625–1629. IEEE, 2015.

16

