$\chi(\text{Parent}(\text{Root}))\stackrel{{\scriptstyle\text{def}}}{{=}}\emptyset$.
The following holds:

######  Theorem 8.3.

Let $Q(\bm{X}),Q^{\prime}(\bm{U})$ be two full conjunctive queries, over
variables $\bm{X}$ and $\bm{U}$ respectively.

  * •

[KR11, KKNS21] Let $T$ be a tree decomposition for $Q^{\prime}$. If the
following inequality holds for all entropic vectors $\bm{h}$:

$\displaystyle h(\bm{X})\leq$
$\displaystyle\max_{\varphi:\varphi\in\hom(Q^{\prime},Q)}E_{T}\circ\varphi$
(56)

then $Q^{\prime}$ dominates $Q$, $Q\preceq Q^{\prime}$.

  * •

[KKNS21] If $Q^{\prime}$ is chordal and $Q\preceq Q^{\prime}$, then inequality
(56) holds for all entropic vectors, where $T$ is the canonical tree
decomposition of $Q^{\prime}$ consisting of its maximal cliques. In other
words, (56) is a necessary and sufficient condition for dominance.

Let’s call a tree decomposition $T$ simple if for every edge
$(n,n^{\prime})\in\text{Edges}(T)$, $|\chi(n)\cap\chi(n^{\prime})|\leq 1$. If
$Q^{\prime}$ admits a simple tree decomposition, then condition (56) is
decidable; the proof follows immediately from Lemma 6.8. This implies:

######  Corollary 8.4.

Assume that $Q^{\prime}$ is chordal and admits a simple tree decomposition.
Then it is decidable whether $Q\preceq Q^{\prime}$. Moreover, if $Q\not\preceq
Q^{\prime}$, then there exists a normal database instance (Sec. 6.3) such that
$|Q(\bm{D})|>|Q^{\prime}(\bm{D})|$.

Finally, we remark that the connection between the query domination problem
and information inequalities is very tight. The following was proven in
[KKNS21]:

######  Theorem 8.5.

The following problems are computationally equivalent. (1) Check if an
inequality of the form $\max_{j=1,p}(\bm{c}^{(j)}\cdot\bm{h})\geq 0$ is valid
for all entropic vectors $\bm{h}$, where
$\bm{c}^{(1)},\ldots\bm{c}^{(p)}\in\mathbb{R}^{2^{[n]}}$ are $p$ vectors. (2)
Given two queries $Q,Q^{\prime}$ where $Q^{\prime}$ is acyclic, check whether
$Q\preceq Q^{\prime}$.

It is currently open whether these problems are decidable.

##  9 Conditional Inequalities and Approximate Implication

Our last application of information inequalities is for the approximate
implication problem, which can be described informally as follows. Let
$\sigma_{1},\ldots,\sigma_{p}$ be some constraints on the database (we will
define shortly what constraints we consider), and suppose we have a proof of
the implication $\bigwedge_{i}\sigma_{i}\Rightarrow\sigma_{0}$. The question
is, if the database $\bm{D}$ satisfies the constraints $\sigma_{i}$ only
approximatively, is it the case that that $\sigma_{0}$ also holds
approximatively? We will show here that this question is related to
conditional information inequalities, whose study requires us to do another
deep dive into the space of polymatroids and entropic functions. We start by
defining a conditional inequality:

######  Definition 9.1.

A conditional information inequality is an assertion of the following form:

$\displaystyle\bm{c}_{1}\cdot\bm{h}\geq 0\wedge\cdots\bm{c}_{p}\cdot\bm{h}\geq
0$ $\displaystyle\Rightarrow\bm{c}_{0}\cdot\bm{h}\geq 0$ (57)

where $\bm{c}_{i}\in\mathbb{R}^{2^{[n]}}$ for $i=0,p$ are vectors.

Sometimes it will be more convenient to replace $\bm{c}_{i}$ by $-\bm{c}_{i}$,
and write the implication as $\bigwedge_{i}\bm{c}_{i}\cdot\bm{h}\leq
0\Rightarrow\bm{c}_{0}\cdot\bm{h}\leq 0$. As before, the validity of a
conditional inequality depends on the domain of $\bm{h}$, e.g. it can be valid
for polymatroids, or entropic functions, etc.

The first non-Shannon inequality discovered was a conditional inequality
[ZY97], predating the first unconditioned Shannon inequality [ZY98]. Kaced and
Romashchenko [KR13] showed the first examples of essentially conditional
inequalities (explained below). We start by describing the connection between
conditional inequalities and the constraint implication problem in databases,
then study the relaxation problem, a technique for transferring exact
inferences to approximate judgments. We end with the proof of Theorem 5.4,
which we have postponed until we developed sufficient technical machinery.

###  9.1 The Constraint Implication Problem

An integrity constraint, $\sigma$, is an assertion about a relation
$R(\bm{X})$ that is required to hold strictly. The constraints considered here
are Functional Dependencies (FD), already reviewed in Sec. 2, and Multivalued
Dependencies (MVD). An MVD is a statement
$\sigma=(\bm{U}\twoheadrightarrow\bm{V}|\bm{W})$ where $\bm{U}\cup\bm{V}\cup
W$ form a partition of $\bm{X}$. A relation instance $R$ satisfies the MVD,
$R\models\sigma$, if $R=\Pi_{\bm{U}\bm{V}}(R)\bowtie\Pi_{\bm{U}\bm{W}}(R)$.

The implication problem asks whether a set of FDs and/or MVDs $\sigma_{i}$,
$i=1,p$, implies another FD or MVD $\sigma_{0}$:

$\displaystyle\sigma_{1}\wedge\cdots\wedge\sigma_{p}\Rightarrow$
$\displaystyle\sigma_{0}$ (58)

Armstrong’s axioms [AD80] are complete for the implication problem for FDs,
while Beeri et al. [BFH77] gave a complete axiomatization for both FDs and
MVDs, and showed that the implication problem is decidable. In contrast,
Herrmann [Her06] showed that the implication problem of Embedded MVDs is
undecidable; we do not discuss EMVDs here.

Lee [Lee87a] showed the following connection between information theory and
constraints. Fix a relational instance $R$, and let $\bm{h}$ be its associated
(uniform) entropic vector. Then $R\models\bm{U}\rightarrow\bm{V}$ iff
$h(\bm{V}|\bm{U})=0$, and $R\models\bm{U}\twoheadrightarrow\bm{V}|\bm{W}$ iff
$I_{h}(\bm{V};\bm{W}|\bm{U})=0$. Therefore, every implication problem for FDs
and MVDs can be stated as a conditional information inequality. For example,
the augmentation axiom [BFH77] states

$\displaystyle(A\twoheadrightarrow B|CD)\Rightarrow$
$\displaystyle(AC\twoheadrightarrow B|D)$

and is equivalent to the following conditional inequality:555This has the form
in Def. 9.1 once we write it as $-I(B;CD|A)\geq 0$ implies $-I(B;D|AC)\geq 0$.

$\displaystyle I(B;CD|A)=0\Rightarrow$ $\displaystyle I(B;D|AC)=0$ (59)

This can be proven immediately by observing that the identity
$I(B;CD|A)=I(B;C|A)+I(B;D|AC)$ implies:

$\displaystyle I(B;D|AC)\leq$ $\displaystyle I(B;CD|A)$

Since both terms are $\geq 0$, the implication (59) follows.

Beyond database applications, Conditional Independencies (CI) are commonly
used in AI, Knowledge Representation, and Machine Learning. A CI is an
assertions of the form $X\perp Y\mid Z$, where $X,Y,Z$ are three random
variables, stating that $X$ is independent of $Y$ conditioned on $Z$. The AI
community has extensively studied the implication problem for CIs. It was
shown that the implication problem is decidable and finitely axiomatizable for
saturated CIs [GP93] (where $XYZ=$ all variables), but not finitely
axiomatizable in general [Stu90].

###  9.2 The Relaxation Problem

How can we prove a conditional inequality (57)? One approach is as follows.
Find $p$ non-negative real numbers $\lambda_{1},\ldots,\lambda_{p}$ for which
the following inequality is valid:

$\displaystyle\bm{c}\cdot\bm{h}\geq$
$\displaystyle(\sum_{i=1,p}\lambda_{i}\bm{c}_{i})\cdot\bm{h}$ (60)

Then, observe that (60) implies (57). A natural question is whether every
conditional information inequality can be derived in this way, from an
unconditional inequality: when that is the case, then we say that the
conditional inequality (57) relaxes to (60), or that it is essentially
unconditional. Otherwise we say that it is essentially conditional. For
example, the augmentation axiom above can be relaxed, hence it is essentially
unconditioned.

Besides offering an important proof technique, relaxation is important in
modern database applications, because often the integrity constraints don’t
hold exactly, but only approximatively, especially when they are mined from a
given dataset [GR04, SBHR06, CIPY14, BBF+16, KN18, SGS18, PD11, FD16]. The
relaxation problem allows us to transfer proofs over exact constraints to
approximate constraints.

Every implication problem for FDs and MVDs relaxes [KS22]:

######  Theorem 9.2.

Consider the statement (58) asserting the implication between a set of
FDs/MVDs. Consider the associated conditional information inequality:

$\displaystyle\left(\bigwedge_{i}h(\sigma_{i})=0\right)\Rightarrow$
$\displaystyle(h(\sigma_{0})=0)$ (61)

where each expression $h(\sigma_{i})$ represents either
$I_{h}(\bm{V};\bm{W}|\bm{U})$ or $h(\bm{V}|\bm{U})$. Then the following are
equivalent:

  * •

The implication (58) holds for FDs/MVDs.

  * •

The implication (61) holds for all polymatroids.

  * •

The implication (61) holds for all entropic functions.

  * •

The implication (61) holds for all normal polymatroids.

  * •

The inequality $n^{2}/4(\sum_{i}h(\sigma_{i}))\geq h(\sigma_{0})$ holds for
all polymatroids. Furthermore, if $\sigma_{0}$ is an FD (rather than MVD),
then $n^{2}/4$ can be replaced by 1.

Thus, the implication problem for FDs and MVDs relaxes. A consequence of the
theorem is that, if (61) fails, then there exists a relation with only two
tuples falsifying the implication, namely one of the relations $R_{\bm{W}}$ in
(44) associated to a step function.

Next, we examine whether all conditional inequalities relax. To do this, we
need another (last) deep dive into the structure of entropic functions, and
introduce almost-entropic functions.

###  9.3 Background: Almost Entropic Functions

We start with a brief review of cones, following [Sch03, BV04]. A set
$K\subseteq\mathbb{R}^{n}$ is called a _cone_ , if $\bm{x}\in K$ and
$\theta\geq 0$ implies $\theta\bm{x}\in K$. The cone is _convex_ if
$\bm{x}_{1},\bm{x}_{2}\in K$ and $\theta\in[0,1]$ implies
$\theta\bm{x}_{1}+(1-\theta)\bm{x}_{2}\in K$. For any set
$K\subseteq\mathbb{R}^{n}$, we denote by $\bar{K}$ its topological closure,
and by
$K^{*}\stackrel{{\scriptstyle\text{def}}}{{=}}\\{{\bm{y}}\mid{\forall\bm{x}\in
K,\bm{y}^{T}\cdot\bm{x}\geq 0}\\}$, it’s dual. The dual is always a closed,
convex cone, $K\subseteq K^{**}$ and, when $K$ is a closed, convex cone, then
$K=K^{**}$.

A cone is _polyhedral_ if it has the form
$K=\\{{\bm{x}}\mid{\bm{M}\cdot\bm{x}\geq 0}\\}$, for some matrix
$\bm{M}\in\mathbb{R}^{m\times n}$. Any polyhedral cone is closed and convex,
and its dual is also polyhedral.

The set of polymatroids $\Gamma_{n}$ and of entropic vectors $\Gamma_{n}^{*}$
are subsets of $\mathbb{R}^{2^{n}}$. The superscript $*$ in $\Gamma_{n}^{*}$
is an unfortunate notation, since it does not represent a dual, but this
notation is already widely used. Valid inequalities (Def. 4.2) are the dual
cones, $(\Gamma_{n}^{*})^{*}$, and $(\Gamma_{n})^{*}$ respectively. Clearly,
$\Gamma_{n}$ is polyhedral, and therefore $\Gamma_{n}=\Gamma_{n}^{**}$. What
about $\Gamma_{n}^{*}$?

It turns out that, when $n\geq 3$, then $\Gamma_{n}^{*}$ is neither a cone nor
convex. This may come as a surprise, so we take the opportunity to briefly
review here the elegant proof by Zhang and Yeung [ZY97]. Consider the parity
function $h$, shown in Fig. 2, and observe that $h(X)=1$, $h(Z|XY)=0$, and
$I_{h}(X;Y)=0$. If $c$ is a natural number, the vector $c\cdot\bm{h}$ is also
entropic, by Prop. 5.3; but in general, $c\cdot\bm{h}$ is entropic only if
there exists a natural number $N$ such that $c=\log N$, which implies
$\Gamma_{n}^{*}$ is neither a cone, nor convex. To prove this, assume that
$c\cdot\bm{h}$ is entropic, and realized by a probability distribution
$p(X,Y,Z)$. Choose any two values $x$, $y$ such that $p(X=x)>0$ and
$p(Y=y)>0$. Since $I_{c\bm{h}}(X;Y)=c\cdot I_{h}(X;Y)=0$, it holds that
$X\perp Y$, hence $p(X=x)p(Y=y)=p(X=x,Y=y)>0$. Furthermore, $c\cdot
h(Z|XY)=0$, therefore $p$ satisfies the functional dependency $XY\rightarrow
Z$, and there exists a unique value $z$ s.t. $p(X=x,Y=y,Z=z)>0$. We have
obtained $p(X=x)p(Y=y)=p(X=x,Y=y,Z=z)$ and, by symmetry, it also holds that
$p(X=x)p(Z=z)=p(X=x,Y=y,Z=z)$. This implies $p(Y=y)=p(Z=z)$. Since $y$ was
arbitrary, it follows that $p(Y=y)=p(Y=y^{\prime})$ for all $y,y^{\prime}$ in
the support of $Y$. Therefore, the marginal distribution of $Y$ is uniform,
and its entropy is $c\cdot h(Y)=\log N$, where $N$ is the size of the support,
proving $c=\log N$, since $h(Y)=1$. Recall that in Sec. 4.2 we stated that the
conditional entropy $h(-|\bm{U})$ is not always an entropic vector: we invite
the reader to give such an example.

While $\Gamma_{n}^{*}$ is neither a cone nor convex, Yeung [Yeu08] proved:

######  Theorem 9.3.

The topological closure $\bar{\Gamma}^{*}_{n}$ of $\Gamma_{n}^{*}$ is a
closed, convex cone. A vector $\bm{h}\in\bar{\Gamma}^{*}$ is called almost-
entropic.

The complete picture of all sets of polymatroids discussed in this paper is
shown in Fig. 3.

If an inequality is valid for $\Gamma_{n}^{*}$, then it is also valid for
$\bar{\Gamma}_{n}^{*}$, by continuity. However, this no longer holds for
conditional information inequalities: Kaced and Romashchenko [KR13] gave an
example of a conditional inequality that is valid for $\Gamma_{n}^{*}$, but
not for $\bar{\Gamma}_{n}^{*}$. Since we are interested in the relaxation
problem, we will consider only validity for $\bar{\Gamma}_{n}^{*}$.

When $n=3$ then one can show that $\bar{\Gamma}_{3}^{*}=\Gamma_{3}$, hence it
is polyhedral. However, Matúš [Mat07] showed that, for $n\geq 4$,
$\bar{\Gamma}_{n}^{*}$ is not polyhedral. This explains the difficulties in
understanding the non-Shannon inequalities, and also in reasoning about
conditional inequalities.

###  9.4 A Conditional Inequality that Does Not Relax

Kaced and Romashchenko [KR13] gave four examples of essentially conditional
inequalities. This is a very surprising result: it means that a proof of the
implication (58) becomes useless if one of the assumptions has even a tiny
violation in the data. We describe here one of their examples, following the
adaptation in [KS22].

######  Theorem 9.4.

[KR13] The following conditional inequality is valid for
$\bar{\Gamma}_{n}^{*}$, and is essentially conditional:

$\displaystyle I(X;Y|A)=I(X;Y|B)$ $\displaystyle=I(A;B)=I(A;X|Y)=0\Rightarrow
I(X;Y)=0$

Notice that none of the constraints is an FD or an MVD, so this does not
contradict Theorem 9.2. We prove the theorem, and start by proving the
conditional inequality. For that we use the following non-Shannon inequality,
by Matús [Mat07]. For every $k\geq 1$,

$\displaystyle I(X;Y)\leq$
$\displaystyle\frac{k+3}{2}I(X;Y|A)+I(X;Y|B)+I(A;B)$ $\displaystyle+$
$\displaystyle\frac{k+1}{2}I(A;X|Y)+\frac{1}{k}I(A;Y|X)$ (62)

When $k=1$, this is Zhang and Yeung’s inequality (32). Matús proved (62) by
induction on $k$, by applying the Copy Lemma 5.8 at each induction step; we
omit the proof.

Since (62) holds for $\Gamma_{n}^{*}$, it also holds for
$\bar{\Gamma}_{n}^{*}$. To check the conditional inequality in Thm. (9.4), let
$\bm{h}\in\bar{\Gamma}_{n}^{*}$ such that
$I(X;Y|A)=I(X;Y|B)=I(A;B)=I(A;X|Y)=0$: then inequality (62) becomes
$I(X;Y)\leq\frac{1}{k}I(A;Y|X)$ and, since $k$ is arbitrary, it follows that
$I(X;Y)=0$.

Finally, we show that the conditional inequality does not relax, by
describing, for each $\lambda>0$, an entropic vector $\bm{h}$ s.t.

$\displaystyle I(X;Y)\geq$
$\displaystyle\lambda(I(X;Y|A)+I(X;Y|B)+I(A;B)+I(A;X|Y))$ (63)

Let $\bm{h}$ be the entropy of the following distribution:

$A$ $B$ $X$ $Y$ $p$ 0 0 0 0 $1/2-\varepsilon$ 1 0 0 1 $1/2-\varepsilon$ 0 1 1
0 $\varepsilon$ 1 1 0 0 $\varepsilon$

If $\varepsilon$ is small enough then one can check:666Complete calculations
are included in [KS22]; note that here we have swapped the roles of $A$ and
$B$, in order to better draw the connection to Zhang and Yeung’s inequality
(32).

$\displaystyle I(X;Y)=$ $\displaystyle\varepsilon+O(\varepsilon^{2}),\
I(A;X|Y)=O(\varepsilon^{2}),$ $\displaystyle I(X;Y|A)=$ $\displaystyle
I(X;Y|B)=I(A;B)=0$

which proves (63) for $\varepsilon$ is small enough.

###  9.5 Conditional Inequalities Relax with Error Terms

However, in another twist, it turns out that every conditional inequality
relaxes, if we admit a small error term. The following was proven in [KS22]:

######  Theorem 9.5.

Suppose that the following holds:

$\displaystyle\forall\bm{h}\in\bar{\Gamma}_{n}^{*},\ \
\left(\bigwedge_{i=1,p}\bm{c}_{i}\cdot\bm{h}\leq 0\right)\Rightarrow$
$\displaystyle\bm{c}_{0}\cdot\bm{h}\leq 0$ (64)

Then, for every $\varepsilon>0$ there exists
$\lambda_{1},\ldots,\lambda_{p}\geq 0$ such that:

$\displaystyle\forall\bm{h}\in\bar{\Gamma}_{n}^{*},\ \
\bm{c}_{0}\cdot\bm{h}\leq$
$\displaystyle\left(\sum_{i=1,p}\lambda_{i}\bm{c}_{i}\cdot\bm{h}\right)+\varepsilon
h(\bm{X})$ (65)

where $\bm{X}$ is the set of all $n$ variables.

Even with the error term, condition (65) still implies (64), because, if
$\bm{c}_{i}\cdot\bm{h}\leq 0$ for all $i$, then (65) implies
$\bm{c}_{0}\cdot\bm{h}\leq\varepsilon h(\bm{X})$ and, since $\varepsilon$ is
arbitrary, we obtain $\bm{c}_{0}\cdot\bm{h}\leq 0$. In fact, Matús’ inequality
(62) can be seen as a relaxation, with an error term, of the conditional
inequality in Theorem 9.4. Theorem 9.5 shows that this was not accidental:
every conditional inequality follows from an unconditional with an error term
that tends to 0. In the next section we will show that Theorem 9.5 has a
surprising application, to the proof of Theorem 5.4. Before that, we prove
Theorem 9.5 by showing:

######  Lemma 9.6.

[KS22] Let $K\subseteq\mathbb{R}^{n}$ be a closed, convex cone, and
$\bm{c}_{i}\in\mathbb{R}^{n}$, $i=0,p$ be vectors such that the following
holds:

$\displaystyle\forall\bm{x}\in K:\ \
\left(\bigwedge_{i=1,p}\bm{c}_{i}\cdot\bm{x}\leq 0\right)\Rightarrow$
$\displaystyle\bm{c}_{0}\cdot\bm{x}\leq 0$ (66)

Then, for every $\varepsilon>0$, there exists
$\lambda_{1},\ldots,\lambda_{p}\geq 0$ such that:

$\displaystyle\forall\bm{x}\in K:\ \ \bm{c}_{0}\cdot\bm{x}\leq$
$\displaystyle\left(\sum_{i=1,p}\lambda_{i}\bm{c}_{i}\right)\cdot\bm{x}+\varepsilon||\bm{x}||_{\infty}$
(67)

The lemma implies the theorem, because $\bar{\Gamma}_{n}^{*}$ is a closed,
convex cone, and $||\bm{h}||_{\infty}=h(\bm{X})$.

###### Proof.

(of Lemma 9.6) Let
$L\stackrel{{\scriptstyle\text{def}}}{{=}}\\{{-\bm{c}_{i}}\mid{i=1,p}\\}$.
Then condition (66) says that $\bm{x}\in K\cap L^{*}$ implies
$\bm{c}_{0}\cdot\bm{x}\leq 0$, or, equivalently, $-\bm{c}_{0}\in(K\cap
L^{*})^{*}$. The following holds for any closed, convex cones $K_{1},K_{2}$
(see[KS22, Sec.5.3]):

$\displaystyle(K_{1}\cap K_{2})^{*}=$
$\displaystyle\overline{\mathbf{conhull}(K_{1}^{*}\cup K_{2}^{*})}$

where $\mathbf{conhull}(A)$ is the conic hull of a set $A$, i.e. the set of
positive, linear combinations of vectors in $A$. Also, if $L$ is finite, then
$L^{**}=\mathbf{conhull}(L)$. Therefore, $-\bm{c}_{0}$ belongs to the
following set:

$\displaystyle(K\cap L^{*})^{*}=$
$\displaystyle\overline{\mathbf{conhull}(K^{*}\cup L^{**})}$ $\displaystyle=$
$\displaystyle\overline{\mathbf{conhull}(K^{*}\cup\mathbf{conhull}(L))}$
$\displaystyle=$ $\displaystyle\overline{\mathbf{conhull}(K^{*}\cup L)}$

For any $\varepsilon>0$, there exists $\bm{e}\in\mathbb{R}^{n}$ such that
$||\bm{e}||_{1}<\varepsilon$ and:

$\displaystyle-\bm{c}_{0}+\bm{e}\in$ $\displaystyle\mathbf{conhull}(K^{*}\cap
L)$

By the definition of the conic hull, and the fact that $K^{*}$ is a convex
cone, we obtain that there exists $\bm{d}\in K^{*}$ and $\lambda_{i}\geq 0$,
for $i=1,p$ such that:

$\displaystyle-\bm{c}_{0}+\bm{e}=$
$\displaystyle\bm{d}-\sum_{i=1,p}\lambda_{i}\bm{c}_{i}$

We prove (67). Let $\bm{x}\in K$, and observe that $\bm{d}\cdot\bm{x}\geq 0$,
then:

$\displaystyle\left(\sum_{i=1,p}\lambda_{i}\bm{c}_{i}\right)\cdot\bm{x}-\bm{c}_{0}\cdot\bm{x}+\bm{e}\cdot\bm{x}=$
$\displaystyle\bm{d}\cdot\bm{x}\geq 0$

and (67) follows from
$\bm{e}\cdot\bm{x}\leq||\bm{e}||_{1}\cdot||\bm{x}||_{\infty}\leq\varepsilon||\bm{x}||_{\infty}$.
∎

We end this section with a brief discussion of why Theorem 9.5 only holds for
the set of almost entropic functions $\bar{\Gamma}_{n}^{*}$, and fails for
$\Gamma_{n}^{*}$. Kaced and Romashchenko [KR13] gave an example of a
conditional inequality that is valid for $\Gamma_{n}^{*}$, but not for
$\bar{\Gamma}_{n}^{*}$. If Theorem 9.5 were to hold for that inequality, then
the relaxed inequality (65) holds for $\bar{\Gamma}_{n}^{*}$, and then we
could prove that the conditional inequality also holds for
$\bar{\Gamma}_{n}^{*}$.

###  9.6 Proof of Theorem 5.4

We have now the machinery needed to prove Theorem 5.4, which states that
$\text{Log-L-Bound}_{\Gamma_{n}^{*}}$ and $\text{Log-U-
Bound}_{\Gamma_{n}^{*}}$ are asymptotically equal. What makes the proof a
little difficult is the ill-behaved nature of the entropic functions
$\Gamma_{n}^{*}$. To cope with that, use some help from the almost entropic
functions $\bar{\Gamma}_{n}^{*}$, and prove that, here, the two bounds are
equal (not just asymptotically). We state and prove the theorem for an
arbitrary closed, convex cone $K$:

######  Theorem 9.7.

Fix $Q,\Sigma,\bm{b}$, and let $K$ be a closed, convex cone s.t.
$N_{n}\subseteq K\subseteq\Gamma_{n}$. (Recall that $N_{n}$ is the set of
normal polymatroids, Def. 6.2.) Then:

$\displaystyle\text{Log-L-Bound}_{K}(Q,\Sigma,\bm{b})=$
$\displaystyle\text{Log-U-Bound}_{K}(Q,\Sigma,\bm{b})$

In particular, the lower and upper bounds are equal for
$K=\bar{\Gamma}_{n}^{*}$, while they are not necessarily equal for
$\Gamma_{n}^{*}$. It shows that the set $\bar{\Gamma}_{n}^{*}$ is better
behaved that $\Gamma_{n}^{*}$, and that explains why it was used in prior work
[GT17, KNS17] to study lower bounds.

Before we prove the theorem, we show how to use it to prove Theorem 5.4. Its
proof follows from Theorem 9.7 and two identities, (68) and (69), which we
prove below. The first is very simple:

$\displaystyle\text{Log-U-
Bound}_{\bar{\Gamma}_{n}^{*}}(Q,\Sigma,\bm{b})=\text{Log-U-
Bound}_{\Gamma_{n}^{*}}(Q,\Sigma,\bm{b})$ (68)

and follows directly from the fact that $\bar{\Gamma}_{n}^{*}$ and
$\Gamma_{n}^{*}$ have the same dual cone,
$(\bar{\Gamma}_{n}^{*})^{*}=(\Gamma_{n}^{*})^{*}$; in other words, they define
the same set of valid inequalities $\bm{c}\cdot\bm{h}\geq 0$.

The second equality requires a proof, and we state it as a lemma:

######  Lemma 9.8.

The following holds:

$\displaystyle\sup_{k}\frac{\text{Log-L-
Bound}_{\Gamma_{n}^{*}}(Q,\Sigma,k\bm{b})}{\text{Log-L-
Bound}_{\bar{\Gamma}_{n}^{*}}(Q,\Sigma,k\bm{b})}=$ $\displaystyle 1$ (69)

###### Proof.

The proof is similar to that of Theorem 5.5 item (1) in Sec. 5.2. The LHS is
obviously $\leq 1$. To prove that it is $\geq 1$, denote by777If $\text{Log-L-
Bound}_{\bar{\Gamma}_{n}^{*}}(Q,\Sigma,\bm{b})=\infty$ then we choose $L$ an
arbitrarily large number, and make minor adjustments to the proof; we omit the
details. $L\stackrel{{\scriptstyle\text{def}}}{{=}}\text{Log-L-
Bound}_{\bar{\Gamma}_{n}^{*}}(Q,\Sigma,\bm{b})$, and observe that $\text{Log-
L-Bound}_{\bar{\Gamma}_{n}^{*}}$ is linear in $\bm{b}$, $\text{Log-L-
Bound}_{\bar{\Gamma}_{n}^{*}}(Q,\Sigma,k\bm{b})=kL$, because
$\bar{\Gamma}_{n}^{*}$ is a convex cone. It suffices to show that, for all
$\varepsilon>0$, there exists $\bm{h}\in\Gamma_{n}^{*}$ such that
$\bm{h}\models(\Sigma,k\bm{b})$ and $h(\bm{X})\geq(1-\varepsilon)^{2}kL$.

Start with some $\bm{h}\in\bar{\Gamma}_{n}^{*}$ satisfying:

$\displaystyle\forall\sigma\in\Sigma:\ h(\sigma)\leq$ $\displaystyle
b_{\sigma},$ $\displaystyle h(\bm{X})=$ $\displaystyle L$

which exists by the definition of $\text{Log-L-Bound}_{\bar{\Gamma}_{n}^{*}}$
(Def. 5.1) and the fact that the set
$\\{{\bm{h}\in\mathbb{R}^{2^{[n]}}}\mid{||\bm{h}||_{\infty}\leq L}\\}$ is
compact. Chan and Yeung’s Theorem 5.9 proves that $\Upsilon_{n}$ is dense in
$\Gamma_{n}^{*}$, and therefore it is also dense in $\bar{\Gamma}_{n}^{*}$.
Assume w.l.o.g. that $h(\bm{X})>0$, then
$g\stackrel{{\scriptstyle\text{def}}}{{=}}\min_{\bm{U},\bm{V}:h(\bm{V}|\bm{U}>0)}h(\bm{V}|\bm{U})>0$
(the smallest non-zero value of any expression $h(\bm{V}|\bm{U})$). Let
$\delta\stackrel{{\scriptstyle\text{def}}}{{=}}\varepsilon g/4$. Since
$\Upsilon_{n}$ is dense, there exists $r\in\mathbb{N}$ and
$\bm{h}^{(r)}\in\Upsilon_{n}$ such that
$||\frac{1}{r}\bm{h}^{(r)}-\bm{h}||_{\infty}\leq\delta$. We have $h(\bm{X})>0$
hence $h(\bm{X})\geq g$, therefore:

$\displaystyle\frac{1}{r}h^{(r)}(\bm{X})\geq$ $\displaystyle
h(\bm{X})-\delta=h(\bm{X})-\varepsilon g/4$ $\displaystyle\geq$ $\displaystyle
h(\bm{X})-(\varepsilon/4)h(\bm{X})\geq(1-\varepsilon)h(\bm{X})$
$\displaystyle=$ $\displaystyle(1-\varepsilon)L$

We claim that
$\frac{1}{r}h^{(r)}(\bm{V}|\bm{U})\leq(1+\varepsilon/2)h(\bm{V}|\bm{U})$, for
all $\bm{U},\bm{V}$. If $h(\bm{V}|\bm{U})=0$, then $\bm{h}$ satisfies the FD
$\bm{U}\rightarrow\bm{V}$, and therefore $\bm{h}^{(r)}$ also satisfies this FD
(see the note after Theorem 5.9), implying $h^{(r)}(\bm{V}|\bm{U})=0$.
Otherwise, $h(\bm{V}|\bm{U})\geq g$ and,

$\displaystyle\frac{1}{r}h^{(r)}(\bm{V}|\bm{U})\leq$ $\displaystyle
h(\bm{V}|\bm{U})+2\delta=h(\bm{V}|\bm{U})+\varepsilon g/2$ $\displaystyle\leq$
$\displaystyle(1+\varepsilon/2)h(\bm{V}|\bm{U})$

Therefore, we have:

$\displaystyle\forall\sigma\in\Sigma:\ h^{(r)}(\sigma)\leq$
$\displaystyle(1+\varepsilon/2)rb_{\sigma}$ $\displaystyle
h^{(r)}(\bm{X})\geq$ $\displaystyle(1-\varepsilon)rL$

Finally, by the Slack lemma, $\exists
k\in\mathbb{N},\bm{h}^{\prime}\in\Gamma_{n}^{*}$ such that:

$\displaystyle\forall\sigma\in\Sigma:\ h^{\prime}(\sigma)\leq$
$\displaystyle(1-\varepsilon/2)kh^{(r)}(\sigma)\leq(1-(\varepsilon/2)^{2})krb_{\sigma}\leq
krb_{\sigma}$ $\displaystyle h^{\prime}(\bm{X})\geq$
$\displaystyle(1-\varepsilon)kh^{(r)}(\bm{X})\geq(1-\varepsilon)^{2}krL$

This completes the proof. ∎

In the remainder of this section we prove Theorem 9.7.

###### Proof.

(of Theorem 9.7) We will use the following definition from [BV04, Example
5.12]:

######  Definition 9.9.

Let $K$ be a proper cone (meaning: closed, convex, with a non-empty interior,
and pointed i.e. $\bm{x},-\bm{x}\in K$ implies $\bm{x}=0$). A primal/dual cone
program in standard form888We changed to the original formulation [BV04] by
replacing $\bm{c}$ with $-\bm{c}$, replacing $\bm{y}$ with $-\bm{y}$. is the
following:

$\displaystyle\begin{array}[]{ll|ll}Primal&&Dual&\\\
\hline\cr\mbox{Maximize}&\bm{c}^{T}\cdot\bm{x}&\mbox{Minimize}&\bm{y}^{T}\cdot
b\\\
\mbox{where}&\bm{A}\cdot\bm{x}=\bm{b}&\mbox{where}&(\bm{y}^{T}\cdot\bm{A}-\bm{c}^{T})^{T}\in
K^{*}\\\ &\bm{x}\in K&&\end{array}$

Denote by $P^{*},D^{*}$ the optimal value of the primal and dual respectively.
Weak duality states that $P^{*}\leq D^{*}$, and is easy prove. When Slater’s
condition holds, which says that there exists $\bm{x}$ in the interior of $K$
such that $\bm{A}\bm{x}=\bm{b}$, then strong duality holds too: $P^{*}=D^{*}$.

$\text{Log-L-Bound}_{K}(Q,\Sigma,\bm{b})$ and $\text{Log-U-
Bound}_{K}(Q,\Sigma,\bm{b})$ can be expressed as a cone program, by letting
$\bm{A}$ and $\bm{c}$ be the matrix and vector defined in the proof of Theorem
5.2 (thus, $\bm{A}\cdot\bm{h}=(h(\sigma))_{\sigma\in\Sigma}$ and
$c_{\bm{X}}=1$, $c_{\bm{U}}=0$ for $\bm{U}\neq\bm{X}$):

$\displaystyle\begin{array}[]{ll|ll}\lx@intercol\text{Log-L-
Bound}_{K}\hfil\lx@intercol\vrule\lx@intercol&\vrule\lx@intercol\text{Log-U-
Bound}_{K}\hfil\lx@intercol\\\ \hline\cr\lx@intercol\mbox{Maximize
}\bm{c}^{T}\cdot
h\hfil\lx@intercol\vrule\lx@intercol&\vrule\lx@intercol\mbox{Minimize
}\bm{w}^{T}\cdot\bm{b}\hfil\lx@intercol\\\
\mbox{where}&\bm{A}\cdot\bm{h}+\bm{\beta}=\bm{b}&\mbox{where}&(\bm{w}^{T}\cdot\bm{A}-\bm{c}^{T})^{T}\in
K^{*}\\\ &(\bm{h},\bm{\beta})\in K\times\mathbb{R}_{+}^{s}&&\bm{w}\geq
0\end{array}$ (74)

Here $\bm{\beta}$ are slack variables that convert an inequality
$h(\sigma)\leq b_{\sigma}$ into an equality
$h(\sigma)+\beta_{\sigma}=b_{\sigma}$. We leave it to the reader to check that
these two programs are indeed primal/dual as in Def. 9.9.

However, in general, Slater’s condition need not hold for (74). For example,
$K=\bar{\Gamma}_{n}^{*}$ lies in the hyperplane $h(\emptyset)=0$, and thus has
an empty interior. This could be addressed by removing the $\emptyset$
dimension, but we have a bigger problem. Some of the constraints may be tight:
when $b_{\sigma}=0$, then $h(\sigma)=0$, meaning that no feasible solution
$\bm{h}$ exists in the interior of $K$. Instead, we will define a different
cone, $K_{0}$, by using polymatroids on a lattice, as in Sec. 5.1.

Partition $\Sigma$ into $\Sigma_{0}=\\{{\sigma}\mid{b_{\sigma}=0}\\}$ and
$\Sigma_{1}=\\{{\sigma}\mid{b_{\sigma}>0}\\}$, and denote by $\bm{b}_{1}$ the
restriction of $\bm{b}$ to $\Sigma_{1}$. In other words, $\Sigma_{0}$ defines
a set of functional dependencies, while $(\Sigma_{1},\bm{b}_{1})$ defines non-
tight statistics. Let $(L_{\Sigma_{0}},\subseteq)$ be the lattice of the
closed sets of $\Sigma_{0}$ (defined in Sec. 2); we will drop the subscript
and write simply $(L,\subseteq)$ to reduce clutter. Define
$F\subseteq\mathbb{R}^{2^{[n]}}$ the following cone999In fact $F$ is even a
vector space.:

$\displaystyle F\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\\{{\bm{h}\in\mathbb{R}^{2^{[n]}}}\mid{\forall\sigma\in\Sigma_{0}:h(\sigma)=0}\\}$

Let $L_{0}\stackrel{{\scriptstyle\text{def}}}{{=}}L-\\{\hat{0}\\}$,
$N\stackrel{{\scriptstyle\text{def}}}{{=}}|L_{0}|$. Our cone
$K_{0}\subseteq{\mathbb{R}}_{\tiny+}^{N}$ is:

$\displaystyle K_{0}\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\Pi_{L_{0}}(K\cap F)$ (75)

The function $\Pi_{L_{0}}$ projects a $2^{[n]}$-dimensional vector
$(h_{\bm{U}})_{\bm{U}\in 2^{\bm{X}}}$ to the $N$-dimensional vector
$(h_{\bm{U}})_{\bm{U}\in L_{0}}$. Thus, $K_{0}$ not only removes the
$\emptyset$ dimension, but also removes all dimensions subject to a tight
constraint. We prove the following:

  1. (1)

$K_{0}$ is proper

  2. (2)

$\text{Log-L-Bound}_{K}=\text{Log-L-Bound}_{K_{0}}$ and
$\text{Log-U-Bound}_{K}=\text{Log-U-Bound}_{K_{0}}$

  3. (3)

$\text{Log-L-Bound}_{K_{0}}=\text{Log-U-Bound}_{K_{0}}$

Theorem 9.7 follows from these three claims.

We start with item 1, and observe that $K_{0}$ is a closed, convex cone,
because $K\cap F$ is a closed, convex cone, and $\Pi_{L_{0}}$ is a linear
isomorphism $K\cap F\rightarrow K_{0}$: indeed, $\Pi_{L_{0}}$ is surjective by
the definition of $K_{0}$, and it is injective because, if
$\bm{h},\bm{h}^{\prime}\in K\cap F$, then
$\Pi_{L_{0}}(\bm{h})=\Pi_{L_{0}}(\bm{h}^{\prime})$ implies that, for every set
$\bm{U}$, $h(\bm{U})=h(\bm{U}^{+})=h^{\prime}(\bm{U}^{+})=h^{\prime}(\bm{U})$.
It is immediate to check that $K_{0}$ is pointed, and we will show below that
$K_{0}$ has a non-empty interior: this implies that it is proper.

Next, we prove item 2, and for that we will write $\bm{h}$ for a vector in
$K\cap F$ and write $\bm{h}^{(0)}$ for a vector in $K_{0}$. For any statistics
$\sigma=(\bm{V}|\bm{U})\in\Sigma_{1}$, denote by
$\sigma^{+}=((\bm{U}\bm{V})^{+}|\bm{U}^{+})$. We say that a vector
$\bm{h}^{(0)}$ satisfies the statistics $(\Sigma_{1},\bm{b}_{1})$, in notation
$\bm{h}^{(0)}\models(\Sigma_{1},\bm{b}_{1})$, if
$\bm{h}^{(0)}(\sigma^{+})\leq\bm{b}_{\sigma}$ for all $\sigma\in\Sigma_{1}$.
By definition, a vector $\bm{h}^{(0)}\in K_{0}$ satisfies the FDs
$\Sigma_{0}$.

######  Lemma 9.10.

The following holds:

$\displaystyle\text{Log-L-Bound}_{K}(Q,\Sigma,\bm{b})=\text{Log-L-
Bound}_{K_{0}}(Q,\Sigma_{1},\bm{b}_{1})$

Equivalently, the lemma states:

$\displaystyle\sup_{\bm{h}}$ $\displaystyle\left\\{{h(\bm{X})}\mid{\bm{h}\in
K,\bm{h}\models(\Sigma,\bm{b})}\right\\}$ $\displaystyle=$
$\displaystyle\sup_{\bm{h}^{(0)}}\left\\{{h^{(0)}(\hat{1})}\mid{\bm{h}^{(0)}\in
K_{0},\bm{h}^{(0)}\models(\Sigma_{1},\bm{b}_{1})}\right\\}$

and the proof is immediate, because the projection of a vector $\bm{h}\in K$
satisfying $(\Sigma,\bm{b})$ is a vector $\bm{h}^{(0)}\in K_{0}$ satisfying
$(\Sigma_{1},\bm{b}_{1})$, and, conversely, every such $\bm{h}^{(0)}$ is the
projection of a vector $\bm{h}$.

Recall that we have assumed $N_{n}\subseteq K\subseteq\Gamma_{n}$:

######  Lemma 9.11.

The following holds:

$\displaystyle\text{Log-U-Bound}_{K}(Q,\Sigma,\bm{b})=\text{Log-U-
Bound}_{K_{0}}(Q,\Sigma_{1},\bm{b}_{1})$

###### Proof.

We need to prove:

$\displaystyle\inf_{\bm{w}}$
$\displaystyle\left\\{{\sum_{\sigma\in\Sigma}w_{\sigma}b_{\sigma}}\mid{K\models\sum_{\sigma\in\Sigma}w_{\sigma}h(\sigma)\geq
h(\bm{X})}\right\\}$ (76) $\displaystyle=$
$\displaystyle\inf_{\bm{w}^{(0)}}\left\\{{\sum_{\sigma\in\Sigma_{1}}w_{\sigma^{+}}^{(0)}b_{\sigma}}\mid{K_{0}\models\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}h^{(0)}(\sigma^{+})\geq
h^{(0)}(\bm{X})}\right\\}$

A vector $\bm{w}$ on the LHS defines an unconstrained inequality, while a
vector $\bm{w}^{(0)}$ on the RHS defines a constrained inequality, because
$\bm{w}^{(0)}$ satisfies

$\displaystyle\forall\bm{h}^{(0)}\in
K_{0},\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}h^{(0)}(\sigma^{+})\geq
h^{(0)}(\bm{X})$

iff it satisfies

$\displaystyle\forall\bm{h}\in
K,\bigwedge_{\sigma\in\Sigma_{0}}h(\sigma)=0\Rightarrow\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}h(\sigma^{+})\geq
h(\bm{X})$ (77)

which is a constrained inequality.

We start by showing that LHS$\geq$RHS in Eq. (76). For that it suffices
observe that, if $\bm{w}=(\bm{w}_{\sigma})_{\sigma\in\Sigma}$ defines a valid
inequality $\sum_{\sigma\in\Sigma}w_{\sigma}h(\sigma)\geq h(\bm{X})$, then its
projection $\bm{w}^{(0)}=(w_{\sigma^{+}})_{\sigma\in\Sigma_{1}}$ defines a
valid constrained inequality
$\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}h^{(0)}(\sigma^{+})\geq
h^{(0)}(\bm{X})$, because all the missing terms $h(\sigma)$ for
$\sigma\in\Sigma_{0}$ are $=0$. Therefore
$\inf_{\bm{w}}(\cdots)\geq\inf_{\bm{w}^{(0)}}(\cdots)$

We prove now that LHS$\leq$RHS. Let $\bm{w}^{(0)}$ be a vector defining a
valid constrained inequality (77). The objective value of the RHS of (76) is
$\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}b_{\sigma}$. By the relaxation
theorem 9.5, for every $\varepsilon>0$ there exists $\lambda_{\sigma}\geq 0$,
for $\sigma\in\Sigma_{0}$, such that the following is a valid, unconstrained
inequality:

$\displaystyle
K\models\sum_{\sigma\in\Sigma_{0}}\lambda_{\sigma}h(\sigma)+\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}h(\sigma^{+})+\varepsilon
h(\bm{X})\geq$ $\displaystyle h(\bm{X})$

This inequality is not yet of the form on the LHS of (76), because we have
terms $h(\sigma^{+})$ instead of $h(\sigma)$. For each such term,
$h(\sigma^{+})=h((\bm{U}\bm{V})^{+}|\bm{U}^{+})$, where
$\sigma=(\bm{V}|\bm{U})$, we use the following Shannon inequality:

$\displaystyle h(\sigma^{+})=$ $\displaystyle
h((\bm{U}\bm{V})^{+}|\bm{U}^{+})\leq h((\bm{U}\bm{V})^{+}|\bm{U})$
$\displaystyle=$ $\displaystyle
h(\bm{U}\bm{V}|\bm{U})+h((\bm{U}\bm{V})^{+}|\bm{U}\bm{V})$ $\displaystyle=$
$\displaystyle h(\sigma)+h((\bm{U}\bm{V})^{+}|\bm{U}\bm{V})\leq
h(\sigma)+\sum_{\sigma\in\Sigma_{0}}h(\sigma)$

The last inequality,
$h((\bm{U}\bm{V})^{+}|\bm{U}\bm{V})\leq\sum_{\sigma\in\Sigma_{0}}h(\sigma)$,
can be checked by induction on the number of steps needed to compute the
closure $(\bm{U}\bm{V})^{+}$ using the FDs in $\Sigma_{0}$. (It also follows
from Theorem 9.2.) This implies that there exists coefficients
$\lambda^{\prime}_{\sigma}\geq 0$ such that the following is a valid,
unconstrained inequality:

$\displaystyle
K\models\sum_{\sigma\in\Sigma_{0}}\lambda^{\prime}_{\sigma}h(\sigma)+\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}h(\sigma)+\varepsilon
h(\bm{X})\geq$ $\displaystyle h(\bm{X})$

or, equivalently,

$\displaystyle
K\models\sum_{\sigma\in\Sigma_{0}}\frac{\lambda^{\prime}_{\sigma}}{1-\varepsilon}h(\sigma)+\sum_{\sigma\in\Sigma_{1}}\frac{w^{(0)}_{\sigma^{+}}}{1-\varepsilon}h(\sigma)\geq$
$\displaystyle h(\bm{X})$

This is a valid inequality for the LHS of (76), and its objective value is
$(\sum_{\sigma\in\Sigma_{1}}w^{(0)}_{\sigma^{+}}b_{\sigma})/(1-\varepsilon)$,
because $b_{\sigma}=0$ for all $\sigma\in\Sigma_{0}$. Since $\varepsilon$ can
be chosen arbitrarily small, it follows that LHS$\leq$RHS in (76). ∎

This completes the proof of item 2. It remains to prove item 3. For that we
represent both $\text{Log-L-Bound}_{K_{0}}(Q,\Sigma_{1},\bm{b}_{1})$ and
$\text{Log-U-Bound}_{K_{0}}(Q,\Sigma_{1},\bm{b}_{1})$ as the solutions to the
primal/dual cone program (74) over the cone $K_{0}$. Notice that the vector
$\bm{b}$ is restricted to $\bm{b}_{1}$ and, therefore, $b_{\sigma}>0$ for all
$\sigma\in\Sigma_{1}$: we no longer have tight constraints. Similarly, the
matrix $\bm{A}$ will be restricted to a matrix $\bm{A}_{1}$ whose rows
correspond to the closed sets $\bm{U}\subseteq\bm{X}$. It remains to check
Slater’s condition, and, in particular, prove that $K_{0}$ has a non-empty
interior. For that purpose we extended the definition of step functions from
Sec. 6.1 to our lattice $L$. For each closed set $\bm{W}\in L$, s.t.
$\bm{W}\neq\hat{1}$, we define the step function at $\bm{W}$ as follows.

$\displaystyle\forall\bm{U}\in L:\ \
h_{\bm{W}}^{(0)}(\bm{U})\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\begin{cases}0&\mbox{if $\bm{U}\subseteq\bm{W}$}\\\
1&\mbox{otherwise}\end{cases}$

Let $\bm{h}_{\bm{W}}\in K$ be the standard step function in Eq. (40) (we
assumed $N_{n}\subseteq K$). $\bm{h}_{\bm{W}}$ satisfies all FDs $\Sigma_{0}$,
because the only FDs that it does not satisfy are of the form
$\bm{U}\rightarrow\bm{V}$ where $\bm{U}\subseteq\bm{W}$,
$\bm{V}\not\subseteq\bm{W}$, and none of the FDs in $\Sigma_{0}$ have this
form because $\bm{W}^{+}=\bm{W}$. It follows $\bm{h}_{\bm{W}}\in K\cap F$, and
this proves $\bm{h}^{(0)}_{\bm{W}}=\Pi_{L_{0}}(\bm{h}_{\bm{W}})\in K_{0}$.
There are $N$ step functions $\bm{h}^{(0)}_{\bm{W}}\in K_{0}$, and it is
straightforward to check that they are independent vectors in
$\mathbb{R}^{N}$. Let $\varepsilon>0$ be small enough such that $2\varepsilon
N<\min_{\sigma\in\Sigma_{1}}b_{\sigma}$. Define
$\bm{h}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{\bm{W}\in
L_{0}}\varepsilon\bm{h}_{\bm{W}}$, and
$\bm{h}^{(0)}\stackrel{{\scriptstyle\text{def}}}{{=}}\Pi_{L_{0}}(\bm{h})$.
Since $K\cap F$ is a convex cone, $\bm{h}\in K\cap F$ and therefore
$\bm{h}^{(0)}\in K_{0}$. We claim that there exists slack variables
$\bm{\beta}$ such that $(\bm{h}^{(0)},\beta)$ is a feasible solution to the
cone program in (74) and, furthermore, $(\bm{h}^{(0)},\bm{\beta})$ belongs to
the interior of $K_{0}\times{\mathbb{R}}_{\tiny+}^{s}$. Indeed, for all
$\sigma\in\Sigma_{1}$, $h^{(0)}(\sigma)\leq\varepsilon N<b_{\sigma}$, hence,
if we define
$\beta_{\sigma}\stackrel{{\scriptstyle\text{def}}}{{=}}b_{\sigma}-h^{(0)}(\sigma)$,
the pair $(\bm{h}^{(0)},\bm{\beta})\in K_{0}\times{\mathbb{R}}_{\tiny+}^{s}$
is a feasible solution to the primal (74). Next, we prove that
$(\bm{h}^{(0)},\bm{\beta})$ is in the interior of
$K_{0}\times{\mathbb{R}}_{\tiny+}^{s}$. Since $\beta_{\sigma}>0$ for all
$\sigma\in\Sigma_{1}$, it follows that $\bm{\beta}$ is in the interior of
${\mathbb{R}}_{\tiny+}^{s}$. Set
$\bm{h}^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}\sum_{\bm{W}\in
L_{0}}(\varepsilon+\delta_{\bm{W}})\bm{h}_{\bm{W}}$, where
$\delta_{\bm{W}}\in(-\varepsilon,\varepsilon)$ are $N$ arbitrary numbers, we
have $\bm{h}^{\prime}\in K\cap F$, hence $\Pi_{L_{0}}(\bm{h}^{\prime})\in
K_{0}$. This proves that $\bm{h}^{(0)}$ is in the interior of $K_{0}$, thus,
verifying Slater’s condition. It follows that $\text{Log-L-
Bound}_{K_{0}}(Q,\Sigma_{1},\bm{b}_{1})=\text{Log-U-
Bound}_{K_{0}}(Q,\Sigma_{1},\bm{b}_{1})$, completing the proof of item 3. ∎

##  10 Conclusions

Data is ultimately information, and therefore the connection between databases
and information theory is no surprise. We have discussed applications of
information inequalities to several database theory problems: query upper
bounds, query evaluation, query domination, and reasoning about approximate
constraints. There are major open problems in information theory, for example
the decidability of entropic information inequalities, the complexity of
deciding Shannon inequalities, a characterization of the cone
$\bar{\Gamma}_{n}^{*}$, and each such open problem has a corresponding open
problem in database theory. In some cases the converse holds too, for example
the query domination problem is computationally equivalent to checking
validity of max-information inequalities, hence any proof of (un)-decidability
of one problem carries over to the other.

A broader question is whether information theory can find wider applications
in finite model theory. For example, functional dependencies and multivalued
dependencies can be specified either using first order logic sentences, or
using entropic terms. Are there other properties in finite model theory that
can be captured using information theory? Such a connection would enable
logical implications to be relaxed to approximate reasoning, with lots of
potential in modern, data-driven applications that rely heavily on statistical
reasoning.

## References

  * [ACK+11] Michael Armbrust, Kristal Curtis, Tim Kraska, Armando Fox, Michael J. Franklin, and David A. Patterson.  PIQL: success-tolerant query processing in the cloud.  PVLDB, 5(3):181–192, 2011.
  * [AD80] William Ward Armstrong and Claude Delobel.  Decomposition and functional dependencies in relations.  ACM Trans. Database Syst., 5(4):404–430, 1980.
  * [AFP+09] Michael Armbrust, Armando Fox, David A. Patterson, Nick Lanham, Beth Trushkowsky, Jesse Trutna, and Haruki Oh.  SCADS: scale-independent storage for social computing applications.  In CIDR 2009, Fourth Biennial Conference on Innovative Data Systems Research, Asilomar, CA, USA, January 4-7, 2009, Online Proceedings, 2009\.
  * [AGM13] Albert Atserias, Martin Grohe, and Dániel Marx.  Size bounds and query plans for relational joins.  SIAM J. Comput., 42(4):1737–1767, 2013.
  * [AL02] Marcelo Arenas and Leonid Libkin.  A normal form for XML documents.  In Lucian Popa, Serge Abiteboul, and Phokion G. Kolaitis, editors, Proceedings of the Twenty-first ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, June 3-5, Madison, Wisconsin, USA, pages 85–96. ACM, 2002.
  * [AL05] Marcelo Arenas and Leonid Libkin.  An information-theoretic approach to normal forms for relational and XML data.  J. ACM, 52(2):246–283, 2005.
  * [ALK+13] Michael Armbrust, Eric Liang, Tim Kraska, Armando Fox, Michael J. Franklin, and David A. Patterson.  Generalized scale independence through incremental precomputation.  In SIGMOD 2013, pages 625–636, 2013.
  * [AtCG+15] Molham Aref, Balder ten Cate, Todd J. Green, Benny Kimelfeld, Dan Olteanu, Emir Pasalic, Todd L. Veldhuizen, and Geoffrey Washburn.  Design and implementation of the logicblox system.  In Timos K. Sellis, Susan B. Davidson, and Zachary G. Ives, editors, Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, May 31 - June 4, 2015, pages 1371–1382. ACM, 2015.
  * [BB12] Paul Balister and Béla Bollobás.  Projections, entropy and sumsets.  Comb., 32(2):125–141, 2012.
  * [BBF+16] Tobias Bleifuß, Susanne Bülow, Johannes Frohnhofen, Julian Risch, Georg Wiese, Sebastian Kruse, Thorsten Papenbrock, and Felix Naumann.  Approximate discovery of functional dependencies for large datasets.  In Proceedings of the 25th ACM International Conference on Information and Knowledge Management, CIKM 2016, Indianapolis, IN, USA, October 24-28, 2016, pages 1803–1812, 2016.
  * [BFH77] Catriel Beeri, Ronald Fagin, and John H. Howard.  A complete axiomatization for functional and multivalued dependencies in database relations.  In Proceedings of the 1977 ACM SIGMOD International Conference on Management of Data, Toronto, Canada, August 3-5, 1977., pages 47–61, 1977.
  * [BV04] Stephen Boyd and Lieven Vandenberghe.  Convex Optimization.  Cambridge University Press, 2004.
  * [CGFS86] Fan R. K. Chung, Ronald L. Graham, Peter Frankl, and James B. Shearer.  Some intersection theorems for ordered sets and graphs.  J. Comb. Theory, Ser. A, 43(1):23–37, 1986.
  * [CIPY14] Xu Chu, Ihab F. Ilyas, Paolo Papotti, and Yin Ye.  Ruleminer: Data quality rules discovery.  In IEEE 30th International Conference on Data Engineering, Chicago, ICDE 2014, IL, USA, March 31 - April 4, 2014, pages 1222–1225, 2014\.
  * [Csi22] Laszlo Csirmaz.  Around entropy inequalities.  https://www.lirmm.fr/~romashchen/seminar-aait.html, 2022.  Slides and video accessed March 2023.
  * [CV93] Surajit Chaudhuri and Moshe Y. Vardi.  Optimization of _Real_ conjunctive queries.  In ACM PODS, 1993, pages 59–70, 1993.
  * [CY02] Terence H. Chan and Raymond W. Yeung.  On a relation between information inequalities and group theory.  IEEE Transactions on Information Theory, 48(7):1992–1995, 2002\.
  * [Fag82] Ronald Fagin.  Horn clauses and database dependencies.  J. ACM, 29(4):952–985, 1982.
  * [Fag83] Ronald Fagin.  Degrees of acyclicity for hypergraphs and relational database schemes.  J. ACM, 30(3):514–550, 1983.
  * [FBS+20] Michael J. Freitag, Maximilian Bandle, Tobias Schmidt, Alfons Kemper, and Thomas Neumann.  Adopting worst-case optimal joins in relational database systems.  Proc. VLDB Endow., 13(11):1891–1904, 2020.
  * [FD16] Abram Friesen and Pedro Domingos.  The sum-product theorem: A foundation for learning tractable models.  In Maria Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 1909–1918, New York, New York, USA, 20–22 Jun 2016. PMLR.
  * [FK98] Ehud Friedgut and Jeff Kahn.  On the number of copies of one hypergraph in another.  Israel Journal of Mathematics, 105(1):251–256, 1998.
  * [Fri04] Ehud Friedgut.  Hypergraphs, entropy, and inequalities.  Am. Math. Mon., 111(9):749–760, 2004.
  * [GLVV12] Georg Gottlob, Stephanie Tien Lee, Gregory Valiant, and Paul Valiant.  Size and treewidth bounds for conjunctive queries.  J. ACM, 59(3):16:1–16:35, 2012.
  * [GM06] Martin Grohe and Dániel Marx.  Constraint solving via fractional edge covers.  In Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2006, Miami, Florida, USA, January 22-26, 2006, pages 289–298. ACM Press, 2006.
  * [GM14] Martin Grohe and Dániel Marx.  Constraint solving via fractional edge covers.  ACM Trans. Algorithms, 11(1):4:1–4:20, 2014.
  * [GP93] Dan Geiger and Judea Pearl.  Logical and algorithmic properties of conditional independence and graphical models.  The Annals of Statistics, 21(4):2001–2021, 1993.
  * [GR04] Chris Giannella and Edward L. Robertson.  On approximation measures for functional dependencies.  Inf. Syst., 29(6):483–507, 2004.
  * [GT17] Tomasz Gogacz and Szymon Torunczyk.  Entropy bounds for conjunctive queries with functional dependencies.  In Michael Benedikt and Giorgio Orsi, editors, 20th International Conference on Database Theory, ICDT 2017, March 21-24, 2017, Venice, Italy, volume 68 of LIPIcs, pages 15:1–15:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
  * [Her06] Christian Herrmann.  Corrigendum to ”on the undecidability of implications between embedded multivalued database dependencies” [inform. and comput. 122(1995) 221-235].  Inf. Comput., 204(12):1847–1851, 2006.
  * [IR95] Yannis E. Ioannidis and Raghu Ramakrishnan.  Containment of conjunctive queries: Beyond relations as sets.  ACM Trans. Database Syst., 20(3):288–324, 1995.
  * [JKV06] T. S. Jayram, Phokion G. Kolaitis, and Erik Vee.  The containment problem for REAL conjunctive queries with inequalities.  In ACM PODS, 2006, pages 80–89, 2006.
  * [KKNS20] Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, and Dan Suciu.  Decision problems in information theory.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, 47th International Colloquium on Automata, Languages, and Programming, ICALP 2020, July 8-11, 2020, Saarbrücken, Germany (Virtual Conference), volume 168 of LIPIcs, pages 106:1–106:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
  * [KKNS21] Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, and Dan Suciu.  Bag query containment and information theory.  ACM Trans. Database Syst., 46(3):12:1–12:39, 2021.
  * [KMP+20] Batya Kenig, Pranay Mundra, Guna Prasaad, Babak Salimi, and Dan Suciu.  Mining approximate acyclic schemes from relations.  In David Maier, Rachel Pottinger, AnHai Doan, Wang-Chiew Tan, Abdussalam Alawini, and Hung Q. Ngo, editors, Proceedings of the 2020 International Conference on Management of Data, SIGMOD Conference 2020, online conference [Portland, OR, USA], June 14-19, 2020, pages 297–312. ACM, 2020.
  * [KN18] Sebastian Kruse and Felix Naumann.  Efficient discovery of approximate dependencies.  PVLDB, 11(7):759–772, 2018.
  * [KNS16] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu.  Computing join queries with functional dependencies.  In Tova Milo and Wang-Chiew Tan, editors, Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 327–342. ACM, 2016.
  * [KNS17] Mahmoud Abo Khamis, Hung Q. Ngo, and Dan Suciu.  What do shannon-type inequalities, submodular width, and disjunctive datalog have to do with one another?  In Emanuel Sallinger, Jan Van den Bussche, and Floris Geerts, editors, Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2017, Chicago, IL, USA, May 14-19, 2017, pages 429–444. ACM, 2017.  Extended version available at http://arxiv.org/abs/1612.02503.
  * [KR11] Swastik Kopparty and Benjamin Rossman.  The homomorphism domination exponent.  Eur. J. Comb., 32(7):1097–1114, 2011.
  * [KR13] Tarik Kaced and Andrei E. Romashchenko.  Conditional information inequalities for entropic and almost entropic points.  IEEE Trans. Inf. Theory, 59(11):7149–7167, 2013.
  * [KS22] Batya Kenig and Dan Suciu.  Integrity constraints revisited: From exact to approximate implication.  Log. Methods Comput. Sci., 18(1), 2022.
  * [Lee87a] Tony T. Lee.  An information-theoretic analysis of relational databases - part I: data dependencies and information metric.  IEEE Trans. Software Eng., 13(10):1049–1061, 1987.
  * [Lee87b] Tony T. Lee.  An information-theoretic analysis of relational databases - part II: information structures of database schemas.  IEEE Trans. Software Eng., 13(10):1061–1072, 1987.
  * [LW49] L. H. Loomis and H. Whitney.  An inequality related to the isoperimetric inequality.  Bull. Am. Math. Soc., 55:961–962, 1949.
  * [Mar13] Dániel Marx.  Tractable hypergraph properties for constraint satisfaction and conjunctive queries.  J. ACM, 60(6):42:1–42:51, 2013.
  * [Mat07] Frantisek Matús.  Infinitely many information inequalities.  In IEEE International Symposium on Information Theory, ISIT 2007, Nice, France, June 24-29, 2007, pages 41–44. IEEE, 2007.
  * [MKS21] Amine Mhedhbi, Chathura Kankanamge, and Semih Salihoglu.  Optimizing one-time and continuous subgraph queries using worst-case optimal joins.  ACM Trans. Database Syst., 46(2):6:1–6:45, 2021.
  * [NPRR12] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra.  Worst-case optimal join algorithms: [extended abstract].  In Michael Benedikt, Markus Krötzsch, and Maurizio Lenzerini, editors, Proceedings of the 31st ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2012, Scottsdale, AZ, USA, May 20-24, 2012, pages 37–48. ACM, 2012.
  * [NPRR18] Hung Q. Ngo, Ely Porat, Christopher Ré, and Atri Rudra.  Worst-case optimal join algorithms.  J. ACM, 65(3):16:1–16:40, 2018.
  * [NRR13] Hung Q. Ngo, Christopher Ré, and Atri Rudra.  Skew strikes back: new developments in the theory of join algorithms.  SIGMOD Rec., 42(4):5–16, 2013.
  * [PD11] Hoifung Poon and Pedro M. Domingos.  Sum-product networks: A new deep architecture.  In UAI 2011, Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence, Barcelona, Spain, July 14-17, 2011, pages 337–346, 2011.
  * [Pip86] Nicholas Pippenger.  What are the laws of information theory.  In 1986 Special Problems on Communication and Computation Conference, pages 3–5, 1986.
  * [Rom22] Andrei E. Romashchenko.  The zhang-yeung inequality: an attempt to explain.  https://www.lirmm.fr/~romashchen/seminar-aait.html, 2022.  Slides and video accessed March 2023.
  * [SBHR06] Yannis Sismanis, Paul Brown, Peter J. Haas, and Berthold Reinwald.  GORDIAN: efficient and scalable discovery of composite keys.  In Proceedings of the 32nd International Conference on Very Large Data Bases, Seoul, Korea, September 12-15, 2006, pages 691–702, 2006.
  * [Sch03] A. Schrijver.  Combinatorial Optimization - Polyhedra and Efficiency.  Springer, 2003.
  * [SGS18] Babak Salimi, Johannes Gehrke, and Dan Suciu.  Bias in OLAP queries: Detection, explanation, and removal.  In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 1021–1035, 2018.
  * [SOC16] Maximilian Schleich, Dan Olteanu, and Radu Ciucanu.  Learning linear regression models over factorized joins.  In Fatma Özcan, Georgia Koutrika, and Sam Madden, editors, Proceedings of the 2016 International Conference on Management of Data, SIGMOD Conference 2016, San Francisco, CA, USA, June 26 - July 01, 2016, pages 3–18. ACM, 2016.
  * [Stu90] Milan Studený.  Conditional independence relations have no finite complete characterization.  In 11th Prague Conf. Information Theory, Statistical Decision Foundation and Random Processes, pages 377–396. Norwell, MA, 1990.
  * [Vel14] Todd L. Veldhuizen.  Triejoin: A simple, worst-case optimal join algorithm.  In Nicole Schweikardt, Vassilis Christophides, and Vincent Leroy, editors, Proc. 17th International Conference on Database Theory (ICDT), Athens, Greece, March 24-28, 2014, pages 96–106. OpenProceedings.org, 2014.
  * [Wan22] Yilei Wang.  Personal communication, 2022.
  * [WWS23] Yisu Remy Wang, Max Willsey, and Dan Suciu.  Free join: Unifying worst-case optimal and traditional joins.  CoRR, abs/2301.10841, 2023.
  * [Yeu08] Raymond W. Yeung.  Information Theory and Network Coding.  Springer Publishing Company, Incorporated, 1 edition, 2008.
  * [ZY97] Zhen Zhang and Raymond W. Yeung.  A non-shannon-type conditional inequality of information quantities.  IEEE Trans. Information Theory, 43(6):1982–1986, 1997.
  * [ZY98] Zhen Zhang and Raymond W Yeung.  On characterization of entropy function via information inequalities.  IEEE Transactions on Information Theory, 44(4):1440–1452, 1998\.

###  .1 Proof of the claim in Example 4.9

We prove that any valid $\Sigma$-information inequality is a positive linear
combination of the four inequalities shown in Example 4.9. Such an inequality
has the following form:

$\displaystyle w_{R}h(XY)+w_{S}h(YZ)+w_{T}h(ZU)$
$\displaystyle+w_{B}h(U|XZ)+w_{A}h(X|YU)\geq$ $\displaystyle h(XYZU)$ (78)

where $w_{R},\ldots,w_{A}\geq 0$ are non-negative real numbers. Since the
inequality holds for all polymatroids, it also holds for every step function
$\bm{h}^{\bm{V}}$ (see Eq. (45)), for all $\bm{V}\subseteq\\{X,Y,Z,U\\}$.
There are $2^{4}-1=15$ step functions, but we only use 5 of them:

$\displaystyle\bm{h}^{X}:$ $\displaystyle w_{R}+w_{B}\geq$ $\displaystyle 1$
$\displaystyle\bm{h}^{Y}:$ $\displaystyle w_{R}+w_{S}\geq$ $\displaystyle 1$
$\displaystyle\bm{h}^{Z}:$ $\displaystyle w_{S}+w_{T}\geq$ $\displaystyle 1$
$\displaystyle\bm{h}^{U}:$ $\displaystyle w_{T}+w_{A}\geq$ $\displaystyle 1$
$\displaystyle\bm{h}^{XU}:$ $\displaystyle w_{R}+w_{T}\geq$ $\displaystyle 1$

Consider the three constraints for $\bm{h}^{Y},\bm{h}^{Z},\bm{h}^{XU}$, which
mention only the variables $w_{R},w_{S},w_{T}$. Any solution to these three
constraints can be immediately extended to a solution to all 5 constraints, by
setting $w_{B}\geq\max(0,1-w_{R})$ and $w_{A}\geq\max(0,1-w_{T})$. On the
other hand, the three constraints on $w_{R},w_{S},w_{T}$ assert that they form
a fractional edge cover of a triangle. The fractional edge covering polytope
of a triangle has four extreme vertices,
$(0,1,1),(1,0,1),(1,1,0),(1/2,1/2,1/2)$. It follows that the extreme vertices
of our polytope over all 5 variables are:

$\displaystyle\begin{array}[]{|ccccc|}\hline\cr
w_{R}&w_{S}&w_{T}&w_{A}&w_{B}\\\ \hline\cr 0&1&1&0&1\\\ 1&0&1&0&0\\\
1&1&0&1&0\\\ 1/2&1/2&1/2&1/2&1/2\\\ \hline\cr\end{array}$

Each of these vectors corresponds precisely to one of the four inequalities
that we listed in Example 4.9, and, conversely, any $\Sigma$-inequality of the
form (78) is dominated by some convex combination of one of these four.

###  .2 Proof of (33), and Failure of the Copy Lemma

We start by proving Inequality (33). The proof follows immediately from the
following identity:

$\displaystyle-$ $\displaystyle I(X;Y)+I(X;Y|A)+I(X;Y|B)+I(A:B)+$
$\displaystyle+I(X;Y|A^{\prime})+I(A^{\prime};Y|X)+I(A^{\prime};X|Y)+3I(A^{\prime};AB|XY)$
$\displaystyle=$ $\displaystyle
I(A;B|A^{\prime})+I(A;A^{\prime}|Y)+I(A;A^{\prime}|X)$
$\displaystyle+I(A;A^{\prime}|BXY)+I(B;A^{\prime}|Y)+I(B;A^{\prime}|X)$
$\displaystyle+I(B;A^{\prime}|AXY)+I(X;Y|BA^{\prime})+I(X;Y|AA^{\prime})$
$\displaystyle+I(X;A^{\prime}|ABY)+I(Y;A^{\prime}|AB)$

Next, we prove that the polymatroid in Fig. 5 does not satisfy the Copy Lemma.
Assuming otherwise, let $h^{\prime}$ denote the polymatroid over variables
$X,Y,A,B,A^{\prime},B^{\prime}$. Using only basic Shannon inequalities, we
derive a contradiction. We will drop the index $h^{\prime}$ from
$I_{h^{\prime}}(\cdots)$ and write simply $I(\cdots)$. By assumption, the
values $h^{\prime}(\bm{U})$ for all sets $\bm{U}$ that do not contain both $A$
and $A^{\prime}$, or both $B$ and $A^{\prime}$ are known, for example
$h^{\prime}(A^{\prime}|XY)=h(A|XY)=1$. We also known the value
$h^{\prime}(\bm{U})$ when $\bm{U}$ contain $XY$, example
$h^{\prime}(AA^{\prime}XY)=h^{\prime}(AA^{\prime}|XY)+h^{\prime}(XY)=h^{\prime}(A|XY)+h^{\prime}(A^{\prime}|XY)+h(XY)=1+1+3=5$.
We proceed by examining the other sets where $A,A^{\prime}$ or $B,B^{\prime}$
co-occur, and start by showing $h^{\prime}(AA^{\prime})\leq 3$:

$\displaystyle I(A;A^{\prime}|X)=$ $\displaystyle
h^{\prime}(AX)+h^{\prime}(A^{\prime}X)-h^{\prime}(X)-h^{\prime}(AA^{\prime}X)$
$\displaystyle=$ $\displaystyle 3+3-2-h^{\prime}(AA^{\prime}X)\geq 0$

and we derive $h^{\prime}(AA^{\prime}X)\leq 4$. Similarly (replacing $X$ with
$Y$) we derive $h^{\prime}(AA^{\prime}Y)\leq 4$. Finally, we have:

$\displaystyle I(X;$ $\displaystyle Y|AA^{\prime})=$ $\displaystyle=$
$\displaystyle
h^{\prime}(AA^{\prime}X)+h^{\prime}(AA^{\prime}Y)-h^{\prime}(AA^{\prime}XY)-h^{\prime}(AA^{\prime})\geq
0$

and we derive that $h^{\prime}(AA^{\prime})\leq 3$. We repeat the argument
above by replacing $A$ with $B$, and derive similarly that
$h^{\prime}(BA^{\prime})\leq 3$. Next, we show that
$h^{\prime}(ABA^{\prime})\geq 5$, which follows from:

$\displaystyle I(XY;$ $\displaystyle A^{\prime}|AB)=$ $\displaystyle=$
$\displaystyle
h^{\prime}(ABXY)+h^{\prime}(ABA^{\prime})-h^{\prime}(AB)-h^{\prime}(ABA^{\prime}XY)$
$\displaystyle=$ $\displaystyle 4+h^{\prime}(ABA^{\prime})-4-5\geq 0$

thus $h^{\prime}(ABA^{\prime})\geq 5$. (We also have
$h^{\prime}(ABA^{\prime})\leq h^{\prime}(ABA^{\prime}XY)=5$, hence
$h^{\prime}(ABA^{\prime})=5$, but the inequality suffices for us.) Finally, we
derive a contradiction:

$\displaystyle I(A;B|A^{\prime})=$ $\displaystyle
h^{\prime}(AA^{\prime})+h^{\prime}(BA^{\prime})-h^{\prime}(A^{\prime})-h^{\prime}(ABA^{\prime})$
$\displaystyle\leq$ $\displaystyle 3+3-2-5=-1$

###  .3 Addendum to Theorem 5.9

We briefly sketch here the proof that, if an entropic function $\bm{h}$
satisfies a set of functional dependencies, then so do all $\bm{h}^{(r)}$, for
all $r\geq 0$. For that we need to review the main argument of the proof in
[CY02].

Let $\bm{h}$ be an entropic function, realized by a probability distribution
$(R,p)$. The first step is to ensure that the probabilities $p(t)$ can be
assumed to be rational numbers. Assume w.l.o.g. that $R$ is the support of
$p$, then, by Lee’s result [Lee87a], $h\models\bm{U}\rightarrow\bm{V}$, iff
$R\models\bm{U}\rightarrow\bm{V}$. Consider now any sequence of probability
distributions on $R$, $p^{(k)}:R\rightarrow[0,1]$, of rational numbers, such
that $\lim_{k}p^{(k)}=p$. Then $p^{(k)}$, and its entropic vector
$\bm{h}^{(k)}$, continue to satisfy the same FDs as $R$ and, thus, the same
FDs as $\bm{h}$. Since $\bm{h}^{(k)}$ can be arbitrarily close to $\bm{h}$, it
suffices to prove that the theorem holds for an entropic vector $\bm{h}$
realized by a probability distribution $(R,p)$ where the probabilities are
rational numbers. Assume they have a common denominator $q>0$, and let
$N=|R|$.

From here on, we follow Chan and Yeung’s proof [CY02]. For each
$r=q,2q,3q,\ldots$ define the following $r\times n$ matrix
$\bm{M}_{r}=(m_{\rho i})_{\rho=1,r;i=1,n}$. Its rows are copies of the tuples
in $R$, where each tuple $\bm{x}\in R$ occurs $r\cdot p(\bm{x})$ times in the
matrix $\bm{M}_{r}$. Intuitively, $\bm{M}_{r}$ can be viewed as a relation
with $n$ attributes and $r$ tuples, including duplicates, whose uniform
probability distribution has the same entropic vector $h$ as $(R,p)$. Let $G$
be the symmetric group $S_{r}$, i.e. the group of permutation on the set
$\\{1,2,\ldots,r\\}$; one should think of $G$ as the group of permutations on
the rows of $\bm{M}_{r}$. For each $i=1,\ldots,n$, let $G_{i}$ the subgroup
that leaves the column $i$ invariant, in other words:

$\displaystyle G_{i}=$ $\displaystyle\\{{\sigma\in
G}\mid{m_{\sigma(\rho),i}=m_{\rho,i},\forall\rho=1,r}\\}$

Denoting similarly $G_{\alpha}$ the subgroup of permutations that leave the
set of columns $\alpha\subseteq[n]$ invariant, one can check that
$G_{\alpha}=\bigcap_{i\in\alpha}G_{i}$. Let $\bm{h}^{(r)}$ be the entropy of
the uniform probability distribution on the relational instance
$\\{{(aG_{1},\ldots,aG_{n})}\mid{a\in G}\\}$. Using a combinatorial argument,
Chan and Yeung [CY02] prove that
$\lim_{r\rightarrow\infty}\frac{1}{r}\bm{h}^{(r)}=\bm{h}$. We will not repeat
that argument here, but make the additional observation that, if $R$ satisfies
the FD $\bm{U}\rightarrow\bm{V}$, then $G_{\bm{U}}\subseteq G_{\bm{V}}$, which
implies that $\bm{h}^{(r)}$ also satisfies the same FD.

###  .4 Proof of Equation (47)

Möbius inversion formula states that, if $f,g:2^{\bm{X}}\rightarrow\mathbb{R}$
are two set functions, and one of the identities below holds, then so does the
other:

$\displaystyle f(\bm{U})=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{U}}g(\bm{V})$ $\displaystyle
g(\bm{U})=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{U}-\bm{V}|}f(\bm{V})$
(79)

It is immediate to derive that the following identities are also
equivalent:101010Define
$h(\bm{U})\stackrel{{\scriptstyle\text{def}}}{{=}}f(\bm{X}-\bm{U})$ then (79)
becomes:  $\displaystyle h(\bm{U})=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{X}-\bm{U}}g(\bm{V})$ $\displaystyle
g(\bm{U})=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{U}-\bm{V}|}h(\bm{X}-\bm{V})$
The claim follows by replacing $\bm{V}$ with $\bm{X}-\bm{V}$ in the second
equation, then renaming $h$ to $f$.

$\displaystyle f(\bm{U})=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{X}-\bm{U}}g(\bm{V})$ $\displaystyle
g(\bm{U})=$
$\displaystyle\sum_{\bm{V}:\bm{X}-\bm{U}\subseteq\bm{V}}(-1)^{|\bm{V}\cap\bm{U}|}f(\bm{V})$

To prove Equation (47), we use Equation (48), and the fact that
$h(\bm{X})=\sum_{\bm{V}:\bm{V}\subseteq\bm{X}}a_{\bm{V}}$:

$\displaystyle h(\bm{U})=$
$\displaystyle\sum_{\bm{V}:\bm{V}\cap\bm{U}\neq\emptyset}a_{\bm{V}}=h(\bm{X})-\sum_{\bm{V}:\bm{V}\subseteq\bm{X}-\bm{U}}a_{\bm{V}}$
$\displaystyle h(\bm{X}|\bm{U})=$
$\displaystyle\sum_{\bm{V}:\bm{V}\subseteq\bm{X}-\bm{U}}a_{\bm{V}}$

Möbius’ inversion formula implies:

$\displaystyle a_{\bm{U}}=$
$\displaystyle\sum_{\bm{V}:\bm{X}-\bm{U}\subseteq\bm{V}}(-1)^{|\bm{V}\cap\bm{U}|}h(\bm{X}|\bm{V})$

If $\bm{X}-\bm{U}\subseteq\bm{V}$, then we can write $\bm{V}$ uniquely as
$(\bm{X}-\bm{U})\cup\bm{V}_{0}$, where $\bm{V}_{0}\subseteq\bm{U}$. After
renaming $\bm{V}_{0}$ to $\bm{V}$ we derive:

$\displaystyle a_{\bm{U}}=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}h(\bm{X}|(\bm{X}-\bm{U})\cup\bm{V})$
$\displaystyle=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}h(\bm{X})-\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}h((\bm{X}-\bm{U})\cup\bm{V})$
$\displaystyle=$
$\displaystyle-\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}h((\bm{X}-\bm{U})\cup\bm{V})$
$\displaystyle=$
$\displaystyle-\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}\left(h((\bm{X}-\bm{U})\cup\bm{V})-h(\bm{X}-\bm{U})\right)$
$\displaystyle=$
$\displaystyle-\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}h(\bm{V}|\bm{X}-\bm{U})$

We used twice the fact that $\sum_{\bm{V}\subseteq\bm{U}}(-1)^{|\bm{V}|}=0$
when $\bm{U}\neq\emptyset$. This completes the proof.

###  .5 Proof of Lemma 6.8

To prove the lemma we need to establish a simple fact:

######  Proposition .1.

Let $\alpha_{1},\ldots,\alpha_{n}\geq 0$ be non-negative real numbers. Define
the following set function $\bm{h}:2^{\bm{X}}\rightarrow\mathbb{R}$:

$\displaystyle h(\bm{U})\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\max_{i:X_{i}\in\bm{U}}\alpha_{i}$

Then $\bm{h}$ is a normal polymatroid.

###### Proof.

Set $\alpha_{0}\stackrel{{\scriptstyle\text{def}}}{{=}}0$ and assume w.l.o.g.
that $\alpha_{0}\leq\alpha_{1}\leq\alpha_{2}\leq\cdots\leq\alpha_{n}$. Define
$\delta_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}\alpha_{i}-\alpha_{i-1}$
for $i=1,n$. We prove:

$\displaystyle\bm{h}=$
$\displaystyle\sum_{i=1,n}\delta_{i}\bm{h}^{\bm{X}_{[i+1:n]}}$ (80)

If $k$ is the largest index s.t. $X_{k}\in\bm{U}$, then:

$\displaystyle\sum_{i=1,n}\delta_{i}\bm{h}^{\bm{X}_{[i+1:n]}}(\bm{U})=$
$\displaystyle\sum_{i=1,k}\delta_{i}=\alpha_{k}=h(\bm{U})$

which proves (80). Since $\delta_{i}\geq 0,\forall i$, $\bm{h}$ is a normal
polymatroid. ∎

###### Proof.

(of Lemma 6.8) We prove the claim by induction on the number of variables
$n=|\bm{X}|$. When $n=0$ then the claim holds vacuously, so assume $n\geq 1$.
We will use the following identity:

$\displaystyle\forall\bm{U}\subseteq\bm{X}:\ \ h(\bm{U})=$ $\displaystyle
h(\bm{U}|X_{n})+I(\bm{U};X_{n})$

Consider the following two set functions
$2^{\bm{X}-\\{X_{n}\\}}\rightarrow\mathbb{R}_{+}$:

$\displaystyle h_{1}(\bm{U})\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle h(\bm{U}|X_{n})$ $\displaystyle
h_{2}(\bm{U})\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\max_{X_{i}\in\bm{U}}I(X_{i};X_{n})$

Since $\bm{h}_{1}$, is a polymatroid in $n-1$ variables, by induction
hypothesis we obtain a normal polymatroid $\bm{h}_{1}^{\prime}$ satisfying
properties (a),(b),(c). The second function is already a normal polymatroid,
by Prop. .1. Observe that $h_{2}(\bm{U})\leq I(\bm{U};X_{n})$ for any set
$\bm{U}$ (see Eq. 31 in Prop. 5.6). Define:

$\displaystyle a\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\min_{i}(h(X_{n})-I(X_{i};X_{n}))=h(X_{n})-h_{2}(\bm{X})$

and observe that:

$\displaystyle 0\leq$ $\displaystyle a\leq h(X_{n})-I(\bm{U};X_{n}),\ \ \
\forall\bm{U}\subseteq\bm{X}-\\{X_{n}\\}$

Since both $\bm{h}_{1}^{\prime}$ and $\bm{h}_{2}$ are normal polymatroids, we
can write them as:

$\displaystyle\bm{h}_{1}^{\prime}=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{X}-\\{X_{n}\\}}b_{\bm{V}}\bm{h}^{\bm{V}}$
$\displaystyle\bm{h}_{2}=$
$\displaystyle\sum_{\bm{V}\subseteq\bm{X}-\\{X_{n}\\}}c_{\bm{V}}\bm{h}^{\bm{V}}$

where $b_{\bm{V}},c_{\bm{V}}$ are non-negative coefficients. Define
$\bm{h}^{\prime}$ as:

$\displaystyle\bm{h}^{\prime}\stackrel{{\scriptstyle\text{def}}}{{=}}$
$\displaystyle\sum_{\bm{V}\subseteq\bm{X}-\\{X_{n}\\}}b_{\bm{V}}\bm{h}^{\bm{V}}+\sum_{\bm{V}\subseteq\bm{X}-\\{X_{n}\\}}c_{\bm{V}}\bm{h}^{\bm{V}\cup\\{X_{n}\\}}+a\bm{h}^{\bm{X}}$

We claim that $\bm{h}^{\prime}$ satisfies the conditions of the lemma.
Obviously, $\bm{h}^{\prime}$ is a normal polymatroid, it remains to check
conditions (a),(b),(c). Observe that the following identities hold, for all
$\bm{U}\subseteq\bm{X}-\\{X_{n}\\}$:

$\displaystyle h^{\prime}(\bm{U})=$ $\displaystyle
h_{1}^{\prime}(\bm{U})+h_{2}(\bm{U})$ $\displaystyle
h^{\prime}(\bm{U}\cup\\{X_{n}\\})=$ $\displaystyle
h_{1}^{\prime}(\bm{U})+h_{2}(\bm{X}-\\{X_{n}\\})+a$ $\displaystyle=$
$\displaystyle h_{1}^{\prime}(\bm{U})+h(X_{n})$

We check condition (a). If $\bm{U}$ does not contain $X_{n}$, then

$\displaystyle h^{\prime}(\bm{U})=$ $\displaystyle
h_{1}^{\prime}(\bm{U})+h_{2}(\bm{U})\leq
h(\bm{U}|X_{n})+I(\bm{U};X_{n})=h(\bm{U})$

If $X_{n}\in\bm{U}$ then:

$\displaystyle h^{\prime}(\bm{U})=$ $\displaystyle
h_{1}^{\prime}(\bm{U}-\\{X_{n}\\})+h(X_{n})$ $\displaystyle\leq$
$\displaystyle h(\bm{U}-\\{X_{n}\\}|X_{n})+h(X_{n})=h(\bm{U})$

Next, we check condition (b):

$\displaystyle h^{\prime}(\bm{X})=$ $\displaystyle
h_{1}^{\prime}(\bm{X}-\\{X_{n}\\})+h(X_{n})$ $\displaystyle=$ $\displaystyle
h(\bm{X}-\\{X_{n}\\}|X_{n})+h(X_{n})=h(\bm{X})$

Finally, we check condition (c) for $X_{i}$, $i<n$:

$\displaystyle h^{\prime}(X_{i})=$ $\displaystyle
h_{1}^{\prime}(X_{i})+h_{2}(X_{i})=h_{1}(X_{i})+h_{2}(X_{i})$ $\displaystyle=$
$\displaystyle h(X_{i}|X_{n})+I(X_{i};X_{n})=h(X_{i})$

and finally for $X_{n}$:
$h^{\prime}(X_{n})=h_{1}^{\prime}(\emptyset)+h(X_{n})$. ∎