A Minimal Set of Shannon-type Inequalities for
Functional Dependence Structures

arXiv:1706.03513v1 [] 12 Jun 2017

Satyajit Thakor† , Terence Chan‡ and Alex Grant∗
School of Computing and Electrical Engineering, Indian Institute of Technology Mandi†
Institute for Telecommunications Research, University of South Australia‡
Myriota Pty Ltd∗
Abstract—The minimal set of Shannon-type inequalities (referred to as elemental inequalities), plays a central role in
determining whether a given inequality is Shannon-type. Often,
there arises a situation where one needs to check whether a given
inequality is a constrained Shannon-type inequality. Another
important application of elemental inequalities is to formulate
and compute the Shannon outer bound for multi-source multisink network coding capacity. Under this formulation, it is the
region of feasible source rates subject to the elemental inequalities
and network coding constraints that is of interest. Hence it is
of fundamental interest to identify the redundancies induced
amongst elemental inequalities when given a set of functional
dependence constraints. In this paper, we characterize a minimal
set of Shannon-type inequalities when functional dependence
constraints are present.

I. I NTRODUCTION
Shannon-type inequalities (also called basic inequalities) are
critical tools to obtain converse coding theorems (or outer
bounds) for the capacity of communication systems. Often
the structure of a communication network induces additional
functional dependence constraints on the random variables
involved in the system model. In [1], Yeung gave a framework
for information inequalities and characterized a minimal set
of Shannon-type inequalities for random variables (in the
absence of further functional dependency structures). The
characterization of these inequalities provides a mechanical
framework for proof of information inequalities and numerical
computation of outer bounds for communication networks.
A notable example is the explicitly computable outer bound
(often called the Linear Programming bound or LP bound) for
the multi-source multi-sink network coding problem (see [2]
and [3]). A related problem is to determine whether a given
information inequality is Shannon-type (i.e. is implied by the
Shannon inequalities). This is a redundancy check problem.
A computer program called Information Theoretic Inequality
Prover (ITIP) [4] is available to solve such linear programs.
In this context, the problems of (a) computing the network coding LP bound, and (b) proving basic information
inequalities can both be formulated as linear optimizations
with the elemental inequalities as a subset of the constraints.
One practical challenge in solving these optimization problems is the large number of variables and constraints. The
number of elemental inequalities grows exponentially with the
number of variables, making it challenging and sometimes
computationally infeasible to generate the set of constraints

directly. Therefore, it is of fundamental importance to reduce
complexity by eliminating redundant constraints. In this paper,
we address this problem by characterizing a minimal set of
Shannon-type inequalities subject to the presence of additional
functional dependence constraints.
Section II presents the framework for information inequalities, elemental inequalities, set-theoretic interpretation
of information measures and some applications of the set
of elemental inequalities under equality constraints such as
functional dependence. In Section III, we characterize a set
of redundant elemental inequalities for a given functional
dependence structure. Theorem 1 provides characterization
of minimal elemental inequalities for functional dependence
constraints and the proof is presented in Section IV. In Section
V, we discuss some applications of the main results and future
directions.
II. BACKGROUND
A. Entropy space
For a set of random variables V = {A, B, . . . } with |V| =
n, let h : 2V 7→ R be a real-valued function defined on the
non-empty subsets of V 1 . The function h can also be viewed
as a point in a 2n − 1 dimensional Euclidean space, where
the non-empty subsets of V are the indexes of the coordinate
axes. This space is the entropy space H [2]. For notational
simplicity, represent h as a vector
n

h = [h(A) : A ⊆ V \ ∅]T ∈ R2

−1

.

Let Γ be the set of all vectors satisfying the elemental
Shannon-type inequalities. These basic inequalities define the
polymatroid axioms:
Hh (A | V \ A) ≥ 0,
Ih (A; B | C) ≥ 0,

A∈V

(1)

A 6= B, C ⊆ V \ {A, B}

(2)

where
Hh (A|B) , h(A ∪ B) − h(B)
Ih (A; B|C) , h(A ∪ C) + h(B ∪ C) − h(A ∪ B ∪ C) − h(C).
In cases when the vector h is understood implicitly, we
will denote Hh (A|B) and Ih (A; B|C) simply as H(A|B) and
I(A; B|C).
1 With a slight abuse of notation, 2A denotes the set of all non-empty subsets
of A rather than the power set of A. Singletons are represented without braces.

The region Γ is a polyhedron. In particular
it is a pointed
n
cone in the non-negative orthant R2+ −1 . We refer to (1)
resp. (2) as the non-decreasing resp. submodular elemental
elemental inequalities. Straightforward enumeration shows that
there are
 
n n−2
m=n+
2
(3)
2

In other words, Th (α) is the signed measure for the atom [α]
induced by µ (or accordingly by the function h). It is easy to
see that
X
Th (α).
(7)
h(β) =

elemental inequalities. It has been proved that these elemental
inequalities are non-redundant and that every basic inequality
is implied by this set [5].
As the inequalities (1)–(2) are linear, the set Γ can be written
in matrix form as

Definition 1 (Functional dependency): A functional dependency is a binary tuple (X , Y) where X , Y are disjoint subsets
of V. It means that the set of variables indexed by X are
functionally imply those by Y.
Further, a polymatroid h (satisfying the basic inequalities)
satisfies the functional dependency (X , Y) if and only if

Γ , {h : Gh ≥ 0}

(4)

where G is a m × 2n matrix with entries from {−1, 0, 1},
and 0 is a length 2n all-zero vector. Each row of G encodes
one elemental inequality. The ordering of columns in G is
consistent with the coordinates of h, e.g., lexicographical
ordering on subsets of V.
B. Entropy characterization using atoms
An alternative geometric representation based on a settheoretic interpretation of information measures was given in
[5], which we will re-state below.
For each variable A in V, it corresponds to a set labelled
as Ã. Similarly, for a subset of variables C of V, we will use
C˜ to denote the corresponding union of all sets where A ∈ C.
In other words,
[
C˜ =
Ã.
A∈C

For a given function h, it is associated with a signed measure
µh (or µ for short) such that for any C ⊆ V,
˜
h(C) = µ(C).
˜ is the signed measure for the set C.
˜
Here, µ(C)
An atom is a set of the following form
\
Ã \ C˜

(5)

A6∈C

where C is a proper subset of V. To simplify notation, will
denote the atom defined in (5) as [C].
There are in total 2n − 1 atoms. It has been proved in [5]
that the signed measure for the atoms is uniquely determined
from h (and vice versa). In addition, there is also a one-to-one
correspondence between Shannon’s information measures and
a unique signed measure denoted µ. Following the convention
in [5],
˜
Hh (A|C) = µ(Ã \ C)
˜
Ih (A; B|C) = µ(Ã ∩ B̃ \ C).
Further, define
Th (α) , µ([α]), α ( V.

(6)

α:β\α6=∅

C. Optimization under functional dependencies

Hh (X |Y) = 0.

(8)

Let Φ be a set of L functional dependencies
Φ , {(Xℓ , Yℓ )}L
ℓ=1

(9)

Consider the following optimization problem
Optimize f (h) subject to
(
h∈Γ
h satisfies functional dependencies in Φ.

(10)

Note that h ∈ Γ constrains h to be a polymatroid and the
test (8) applies.
In the context of proving Shannon-type constrained inequalities, Φ can be given a set of functional dependency
constraints. In a network coding problem, Φ is the set of
functional dependency constraints induced by the network
topology and the multicast requirement.
Since all of these constraints are linear inequalities or
equalities, (10) is a linear optimization problem if the objective
function f is also linear.
Proving whether a given inequality is basic is a redundancy
check problem. More generally, a constrained information
inequality bT h ≥ 0 is redundant (subject to given functional
dependencies Φ) if the minimum value of the linear program
Minimize bT h
(
h∈Γ
Subject to
h satisfies functional dependencies in Φ.
is zero.
In general, the set of constraints in (10) can have a very large
and complex structure. Therefore, it is desirable to simplify,
or reduce these constraints prior to numerical solution. In this
paper, we take a first step to achieve this goal by exploiting
the functional dependency structure induced by Φ.
Remark 1: Functional dependence relations naturally define equivalence classes on the set of joint entropies. These
equivalence classes can be used as a basis for describing all
constraints and thus reduce the dimension of the optimization
problem. See Section V for further discussion.

III. M AIN

RESULTS

Definition 2 (Closure): Let C ⊆ V. Its closure cl(C) subject
to a given set of functional dependencies Φ is the maximal set
D such that
Hh (D|C) = 0
for all polymatroids h satisfying Φ.
For any subset of random variables C, its closure is the
largest set of random variables that will be be functionally
implied by C, for every set of random variables satisfies the
functional dependencies Φ.
Definition 3 (Close Atoms): An atom [A] is called close with
respect to a set of functional dependencies Φ = {(Xℓ , Yℓ )}L
ℓ=1 ,
if Xℓ ⊆ A whenever Yℓ ⊆ A, ℓ = 1, 2, . . . , L.
Definition 4 (Vanishing atoms): An atom [C] is called
vanishing with respect to the functional dependencies Φ if
Th (C) = 0
for all polymatroids h satisfying Φ.
Proposition 1 (Vanishing atoms): An atom [A] is vanishing
subject to functional dependencies Φ if and only if [A] is not
close subject to Φ.
Proposition 2: A polymatroid h satisfies all functional
dependencies in Φ if and only if Th (C) = 0 for all vanishing
(non-close) atoms.
In the absence of functional dependency constraints, the set
of minimal Shannon inequalities was obtained in [5] as

Definition 5 (Equivalence): Let C be close with respect to
a given list of functional dependencies Φ and A, B 6∈ C. If
B ∈ cl(AC) and A ∈ cl(BC), then we say A ∼C B.
It is easy to see that ∼C is an equivalence relation on V \ C.
The relation A ∼C B means that A and B imply each other
when conditioning on C.
Definition 6 (Minimal atom): Let C be close with respect to
a given list of functional dependencies Φ. A variable A ∈ V \C
is called C-minimal if whenever there exists B ∈ V \ C such
that B ∈ cl(AC), then A ∈ cl(BC).
Proposition 3 (Reduction 1): Consider the inequality
I(A; B|C) ≥ 0.

(11)

If A is not C-minimal with respect to functional dependencies
Φ, then (11) is redundant.
Proof: If A is not C-minimal, then by definition there
exists D 6∼C A such that
D ∈ cl(AC).
In other words,
Hh (D|AC) = 0
for all polymatroids h satisfying Φ. Consequently,
Ih (A; B|C) = Ih (D; B|C) + Ih (A; B|C, D).
Thus, (11) is implied by the inequalities
I(D; B|C) ≥ 0

H(A|V \ A) ≥ 0
and

and

I(A; B|C, D) ≥ 0.
I(A; B|C) ≥ 0

where A, B ∈ V and C is a subset of V.
Subject to further functional dependency constraints Φ,
some of these inequalities may become redundant. For example, it can be proved easily that if cl(C) = cl(D), then
I(A; B|C) = I(A; B|D)
and hence I(A; B|C) ≥ 0 ⇐⇒ I(A; B|D) ≥ 0. In the
following, we aim to identify such redundant inequalities.
Lemma 1: Let Φ be a given set of functional dependency
constraints. If subject to Φ,

Corollary 1: Similarly, the inequality
H(A|C) ≥ 0

(12)

is redundant subject to functional dependencies Φ if A is not
C-minimal with respect to Φ.
Proposition 4 (Reduction 2): Let A and B be C-minimal
with respect to given functional dependencies Φ, and suppose
A ∼C B. Then
I(A; B|C) ≥ 0

(13)

cl(C) = cl(C ′ )

is redundant if there exists C-minimal D such that D 6∼C A.
Proof:

{cl(AC), cl(BC)} = {cl(A′ C ′ ), cl(B ′ C ′ )},

I(A; B|C) = H(A|C)
= H(A|C, D) + I(A; D|C)

and
then I(A; B|C) = I(A′ ; B ′ |C ′ ). Consequently,
I(A; B|C) ≥ 0 ⇐⇒ I(A′ ; B ′ |C ′ ) ≥ 0.
Lemma 1 illustrates that two inequalities, distinct in the
absence of functional dependencies, can become equivalent
when functional dependencies are introduced. This paper will
identify all such redundant inequalities.

(14)
(15)

The inequality H(A|C, D) ≥ 0 is implied by I(A; B|C, D) ≥
0 or more precisely I(A; B|cl(CD)) ≥ 0.
The remaining inequalities of interest are of the form
I(A; B|C) ≥ 0
such that C is close, and A, B are both C-minimal.

Proposition 5 (Reduction 3): Let A be C minimal with
respect to given functional dependencies Φ. If there exists Cminimal B 6∈ C such that A 6∼C B then
H(A|C) ≥ 0

(16)

is redundant.
Proof: Notice that
H(A|C) = H(A|BC) + I(A; B|C).

(17)

Hence, (16) is implied by H(A|BC) ≥ 0 and I(A; B|C) ≥ 0.
In the above propositions, we have identified numerous
redundant inequalities. The following theorem summarises
above results by charactersing a minimal set of inequalities
that characterise all polymatroids satisfying the functional
dependencies Φ.
Theorem 1 (Minimal characterization): A function h is
polymatroidal and satisfies all functional dependencies in Φ
if and only if it satisfies every Type 1 and Type 2 inequality
below:
Type 1:
I(A; B|C) ≥ 0

(18)

where C is close, A 6∼C B and A, B are C-minimal.
Type 2:
H(A|C) ≥ 0

(19)

where C is close and A is C-minimal such that B ∼C A
whenever B is also C-minimal.
Moreover, this set of inequalities are minimal, in the sense
that each Type 1 and Type 2 inequality is non-redundant.
Again, we take the convention that two inequalities
I(A; B|C) ≥ 0
and
I(A′ ; B ′ |C ′ ) ≥ 0
are equivalent, if 1) cl(C) = cl(C ′ ), and 2) either A ∼C A′
and B ∼C B ′ , or A ∼C B ′ and B ∼C A′ .
Similarly for Type 2, inequalities
H(A|C) ≥ 0

A. Type 1 inequalities
Consider a Type 1 inequality of the form
I(A; B|C) ≥ 0.

(20)

By definition, 1) C is close, 2) A and B are C-minimal, and
3) A 6∼C B.
To prove that the above Type 1 inequality is non-redundant,
we will construct a function h satisfying all the functional
dependencies and all the polymatroidal inequalities except
(20). Instead of directly defining h, we define its corresponding
“atomic” function Th as follows:

−1 if β = C



0
if A, B 6∈ α, α 6= ∅, and β = C ∪ α
Th (β) =
(21)

0
if
β
is
vanishing



2
otherwise.
Note that, by definition,

h(β) =

X

Th (α).

(22)

α:β\α6=∅

Now, we will show that (20) is indeed non-redundant.
First, we will show that the so constructed function h (or
equivalently its atomic version Th ) violates the inequality (20).
Note that
X
Ih (A; B|C) =
Th (α).
α⊇C:A,B6∈α

It can be verified directly that Ih (A; B|C) = −1 ≤ 0, and
hence violating (20). Next, we will prove that function h
satisfies all other Types 1 and 2 inequalities, and also the
functional dependencies.
From (21), Th (β) = 0 if β is vanishing. Hence, the function
h satisfies all the functional dependencies. Now, let us consider
a Type 1 inequality
I(i, j|K) ≥ 0

(23)

which is different from (20). Again, by definition, 1) K is
close, 2) i and j are K-minimal, and 3) i 6∼K j. Notice that
X
Ih (i; j|K) =
Th (α).
α⊇K:i,j6∈α

and
′

′

H(A |C ) ≥ 0
are deemed equivalent, if 1) cl(C) = cl(C ′ ), and 2) A ∼C A′ .
IV. P ROOF OF T HEOREM 1
Since the set of inequalities in Theorem 1 is obtained
by eliminating all redundant inequalities, they certainly will
still characterise all polymatroids satisfying the functional
dependencies Φ. In the following, we will prove that our
obtained Type 1 and Type 2 inequalities are indeed minimal.
To prove the theorem, we will show that for each Type
1 or Type 2 inequality, we can construct a function h that
1) violates the chosen inequality, 2) satisfies all remaining
Type 1 and Type 2 inequalities, and 3) satisfies all functional
dependencies.

We will prove that h satisfies (23) by considering different
cases. In the first case, C does not contain K as a subset. In
this case, the inequality (23) will not involve the atom C, and
hence will be satisfied by h.
Now, suppose that K is a proper subset of C. In this second
case, K 6= C. As K is close, it is non-vanishing. Therefore,
Th (K) = 2. Thus, Ih (i; j|K) ≥ 1 and hence (23) is satisfied
by h. It now remains to consider the third case when K = C.
If (23) is different from (20), then
{cl(iC), cl(jC)} =
6 {cl(AC), cl(BC)}.
In addition, as A 6∼C B and i 6∼C j, we may also assume
without loss of generality that cl(iC) 6= cl(AC) and cl(jC) 6=
cl(AC). In that case, cl(AC) ⊇ C and i, j 6∈ cl(AC). Therefore,

the non-vanishing atom cl(AC) is involved in the inequality
(23) and hence the inequality is satisfied by h.
So far, we have proved that h satisfies all Type 1 inequalities
except (20). Now, it remains to show that h also satisfies all
Type 2 inequalities.
Consider a Type 2 inequality
H(i|K) ≥ 0.

(24)

By definition, K must be close such that i is K-minimal, and
i ∼K j whenever j is also K-minimal. Again, if K is not a
subset of C, then the inequality does not involve the atom C.
Hence, Hh (i|K) is nonnegative. On the other hand, since both
A and B are C-minimal and A ∼C B, K is not equal to C. So,
it remains to consider the case where K is a proper subset of
C. By definition, Th (K) = 2. Hence, it is obvious that from
the definition that Hh (i|K) ≥ 1. The function h thus satisfies
all Type 2 inequalities. And the non-redundancy of Type 1
inequalities have been proved.
B. Type 2 inequality
Next, we will prove that Type 2 inequalities are also nonredundant. Consider a Type 2 inequality of the form
H(A|C) ≥ 0.

(25)

By definition, 1) C must be close and 2) A is C-minimal such
that A ∼C B whenever B is also C-minimal.
For this inequality, we define h as follows:

−1 if β = C




0
if A 6∈ α, α 6= ∅, and β = C ∪ α
Th (β) =
(26)

0
if β is vanishing



2
otherwise.

Again, h can be directly obtained via (7).
Recall that
X
Hh (A|C) =
Th (α).

(27)

α⊇C:A6∈α

From our construction, it is not difficult to see that Hh (A|C) =
−1 and hence h does not satisfy the inequality (25) but satisfies
all functional dependencies. Now, it remains to prove that h
satisfies all other Type 1 and Type 2 inequalities.
First, consider a Type 1 inequality
I(i, j|K) ≥ 0.

(28)

If K is not a subset of C, then the inequality does not
involve the atom [C]. Hence, Ih (i, j|K) is nonnegative. Also,
as C =
6 K, Th (K) = 2 and hence Ih (i, j|K) ≥ 0. Now,
suppose K is a proper subset of C. By definition, Th (K) = 2.
Hence, Ih (i, j|K) ≥ 0. The function h thus satisfies all Type
1 inequalities.
Next, we consider a Type 2 inequality
H(i|K) ≥ 0.

(29)

If K = C, then i ∼K A and thus (29) and (25) are the same
inequality. Suppose K =
6 C. If K is a proper subset of C, then

Th (K) = 2. And if K is not a subset of C, then Th (C) is not
involved in the inequality (29). In any cases, this implies that
h will satisfy (29). Non-redundancy of (25) and also Theorem
1 is thus proved.
V. A PPLICATIONS

AND

F UTURE

WORK

It is desirable to obtain directly the reduced matrix representing the functions h in the constraint region of (10). In [6]
(see also [7], [8]), we gave a graph based recursive algorithms
to find implied functional dependencies from local functional
dependencies. Though the graph based algorithm does not
always give all implied functional dependence relations, it
gives many functional dependencies depending on the structure of local functional dependencies without depending on the
linear programming framework. In [9] (see also [8]), we gave
algorithms to directly obtain a reduced size matrix defining
the constraint region. Despite the fact that the reduction was
not minimal, it was demonstrated that for the well known
butterfly network, the matrix size can be reduced by 98%.
The number of variables, 2n − 1, in the optimization problems
can be reduced to the number of equivalence classes for a
given functional dependency structure. Given the functional
dependence structure, the minimal set of inequalities defining
the constraint region can also be obtained in a matrix form
directly using the approach similar to [9]. Applications of this
matrix include solving the optimization problem (10).
As a continuation of research work in this direction, we aim
to employ the results of this paper to develop more refined algorithms (compared to [9]), for obtaining the “minimal” matrix
directly. Moreover, we are investigating further generalizations
of the ideas presented in this paper.
ACKNOWLEDGMENT
This work is supported in part by Science and Engineering
Research Board, Department of Science and Technology,
Government of India, under project SB/S3/EECE/265/2016.
It is also supported in part by Australian Research Council
under Discovery Project DP150103658.
R EFERENCES
[1] R. W. Yeung, “A framework for linear information inequalities,” IEEE
Trans. Inform. Theory, vol. 43, pp. 1924–1934, Nov. 1997.
[2] R. W. Yeung, Information Theory and Network Coding. Springer, 2008.
[3] R. W. Yeung and Z. Zhang, “On symmetrical multilevel diversity coding,”
IEEE Trans. Inform. Theory, vol. 45, pp. 609–621, Mar. 1999.
[4] R. W. Yeung and Y.-O. Yan, “Information theoretic inequality prover
(ITIP).” http://user-www.ie.cuhk.edu.hk/∼ ITIP/.
[5] R. W. Yeung, “A new outlook on shannon’s information measures,” IEEE
Trans. Inform. Theory, vol. 37, pp. 466–474, May 1991.
[6] S. Thakor, A. Grant, and T. Chan, “Network coding capacity: A functional
dependence bound,” in IEEE Int. Symp. Inform. Theory, pp. 263 –267,
Jun. 2009.
[7] S. Thakor, A. Grant, and T. Chan, “Cut-set bounds on network information flow,” IEEE Trans. Inform. Theory, vol. 62, pp. 1850–1865, Apr.
2016.
[8] S. Thakor, Characterization and Computation of Network Coding Capacity Bounds. PhD thesis, Institute for Telecommunications Research,
University of South Australia, Australia, 2012.
[9] S. Thakor, A. Grant, and T. Chan, “On complexity reduction of the
LP bound computation and related problems,” in IEEE Int. Symp. Net.
Coding, pp. 1–6, Jul. 2011.

