Upper bounds for integrated information

Alireza Zaeemzadeh1* and Giulio Tononi1*

1 Department of Psychiatry, University of Wisconsin, Madison, WI 53719, USA

*<EMAIL_ADDRESS>(AZ<EMAIL_ADDRESS>(GT)

## Abstract

Integrated Information Theory (IIT) offers a theoretical framework to quantify
the causal irreducibilty of a system, subsets of the units in a system, and
the causal relations among the subsets. Specifically, mechanism integrated
information quantifies how much of the causal powers of a subset of units in a
state, also referred to as a mechanism, cannot be accounted for by its parts.
If the causal powers of the mechanism can be fully explained by its parts, it
is reducible and its integrated information is zero. Here, we study the upper
bound of this measure and how it is achieved. We study mechanisms in
isolation, groups of mechanisms, and groups of causal relations among
mechanisms. We put forward new theoretical results that show mechanisms that
share parts with each other cannot all achieve their maximum. We also
introduce techniques to design systems that can maximize the integrated
information of a subset of their mechanisms or relations. Our results can
potentially be used to exploit the symmetries and constraints to reduce the
computations significantly and to compare different connectivity profiles in
terms of their maximal achievable integrated information.

## Author summary

Originally developed as a theory of consciousness, integrated information
theory provides a mathematical framework to quantify the causal irreducibility
of systems and subsets of units in the system. For example, mechanism
integrated information quantifies how much of the causal powers of a subset of
units in a state cannot be accounted for by its parts. Here, we provide
theoretical results on the upper bounds for this measure, how it is achieved,
and why mechanisms with overlapping parts cannot all be maximally integrated.
We also study the upper bounds for integrated information of causal relations
among the mechanisms. The ideas introduced here can potentially pave the way
to design systems with optimal causal irreducibility and to develop
computationally lightweight exact or approximate measures for integrated
information.

##  1 Introduction

As a theory of consciousness, Integrated Information Theory (IIT) [1, 2, 3]
introduces a mathematical framework that quantifies the causal powers of
systems and subsets of units in a system. The methods of IIT have inspired
activity in the neuroscience [4, 5, 6, 7, 8], complexity science [9, 10, 11,
12], and physics [13, 14, 15]. In short, IIT identifies the essential
properties of experience and provides a framework to quantify to what extent a
physical system complies with such properties in terms of its causal powers.
These properties are intrinsicality, information, integration, exclusion, and
composition [1]. This work is mainly focused on the last property, _i.e.,_
composition, meaning that we are concerned with how the subsets of units in
the system specify causes and effects over subsets of units and how these
causes and effects are related. Our results are applicable even if a candidate
system does not satisfy all the essential properties. According to IIT, the
causal components within the system must satisfy the same properties as the
system except composition. They must have cause-effect power within the system
(intrinsically), select a specific state (information) in a way that cannot be
accounted for by their parts (integration) and over a definite set of units
(exclusion) [1].

In particular, IIT enables us to quantify the causal _irreducibility_ of each
subset of system. A set of units in its current state, also referred to as a
_mechanism_ , is irreducible if its causal powers cannot be accounted for by
its parts. For that, the potential cause and the potential effect of each
mechanism are identified and the irreducibility is quantified by measuring how
such cause or effect can be accounted for only using the parts of the
mechanism. A central quantity in the formalism of IIT is the mechanism
integrated information, denoted by $\varphi$, which measures the causal
irreducibility of a single mechanism [1, 16].

An irreducible mechanism, _i.e.,_ a mechanism with nonzero $\varphi$, with its
corresponding cause and effect is referred to as a _distinction_. IIT also
provides us with a framework to quantify how different distinctions causally
interact with each other by defining and measuring the strength of the
_relations_ among them [1, 17]. For example, distinctions might have
overlapping effects, making them related. Finally, the causal powers of the
whole system can be accounted for by its cause-effect structure, which is
composed of its causal distinctions and causal relations that bind together
the distinctions.

The measures to quantify integrated information of distinctions and relations
that capture the postulates of IIT are presented in [1]. In this work we study
the upper bounds achievable by these measures and how we can achieve them.
Barbosa et al [16, 18] showed the integrated information of an individual
distinction can increase by adding reliable, not noisy, units to it. Here, we
study the maximum achievable integrated information of a single distinction of
fixed size and the trade-offs when considering the system as a whole, with all
its overlapping distinctions and their shared parts. In particular, we discus
the following bounds:

  * •

In Section 2.1, we derive an upper bound for how much information a
distinction can specify beyond each of its parts.

  * •

We use this bound to find the maximum integrated information achievable by a
distinction, as well as a bound for the sum of integrated information of all
the distinctions.

  * •

Then in Section 2.2 and Section 2.3, we will show why the distinctions of a
system cannot all achieve their corresponding maximum $\varphi$. We further
provide a numerical bound for a special class of systems.

  * •

The upper bounds for integrated information of relations, as well as the
conditions necessary for achieving them, are presented in Section 3.

In the proofs, we provide techniques to exploit the symmetries in the systems
to simplify the computation of the integrated information. The bounds provided
in this work can be used to compare different connectivity profiles in terms
of their maximum achievable integrated information. We also believe the ideas
and the techniques used to prove the results may be of wider utility, _e.g._ ,
developing approximate measures of integrated information for larger systems.
Furthermore, the results discussed here can be directly used to derive bounds
for $\Phi$, which is defined to be the sum of the integrated information of
all the distinctions and the relations [1].

Section 4 provides numerical experiments and discussions on mathematical
properties of the bounds and the constructions. Finally, a few open problems
and potential directions for research are discussed in Section 5.

##  2 Upper bounds for mechanism integrated information

Consider a stochastic system $S$ consisting of $N$ random variables
$\\{S_{1},S_{2},\dots,S_{N}\\}$. These random variables represent a system
with transition probability matrix (TPM) defined as $p(S_{t+1}=s_{t+1}\mid
S_{t}=s_{t})$, which denotes the probability that the system is in state
$s_{t+1}$ at time $t+1$ given the state of the system at time $t$. The
mechanism integrated information, presented in [1], quantifies how much a
mechanism $M\subseteq S$ in state $m_{t}$ constrains the state of its
potential causes $Z_{t-1}\subseteq S$ and its potential effects
$Z_{t+1}\subseteq S$, above and beyond their parts. For that, a difference
measure is developed that compares the probability distribution of a cause
purview $Z_{t-1}$ or an effect purview $Z_{t+1}$, before and after
partitioning the mechanism-purview pair into independent parts.

Formally, the effect repertoire $\pi_{e}(Z_{t+1}\mid M_{t}=m_{t})$ is defined
as the probability distribution over the potential effect purview $Z_{t+1}$,
given that the mechanism is in state $m_{t}$, and is obtained by _causally_
marginalizing out the random variables outside the mechanism and purview,
under the assumption that the variables at $t+1$ are conditionally independent
given all the variables at $t$ [1, 16]. Having introduced the effect
repertoire, the maximal effect state of $m_{t}$ within the purview $Z_{t+1}$
is defined as:

$z^{\prime}_{e}(m,Z)=\arg\max_{z\in\Omega_{Z}}\pi_{e}(z\mid
m)\log_{2}\left(\frac{\pi_{e}(z\mid m)}{\pi_{e}(z;M)}\right)$ (1)

where $\pi_{e}(z;M)$ is the unconstrained effect probability of state
$z\in\Omega_{Z}$:

$\pi_{e}(z;M)=|\Omega_{M}|^{-1}\sum_{m\in\Omega_{M}}\pi_{e}(z\mid M=m),\quad
z\in\Omega_{Z}.$

To avoid cluttering the notation, the time subscripts $t+1$ and $t$ are
dropped here. Eq (1) gives us the state for which the mechanism $m$ makes the
most difference compared to chance. Since there is at least one state
$z\in\Omega_{Z}$ such that $\pi_{e}(z\mid m)>\pi_{e}(z;M)$, the maximal effect
state will always be a state for which the mechanism increases the probability
compared to the unconstrained probability. This is in line with our intuition
that for a state to be caused by a mechanism, its probability needs to be
increased by that mechanism. Given this maximal effect state, the integrated
effect information of $m$ quantifies how much difference the mechanism makes
to this state above and beyond its parts, by comparing the effect repertoire
for state $z^{\prime}_{e}$, $\pi_{e}(z^{\prime}_{e}\mid m)$, with its
partitioned version $\pi_{e}^{\theta^{\prime}}(z^{\prime}_{e}\mid m)$:

$\varphi_{e}(m,Z)=\pi_{e}(z^{\prime}_{e}\mid
m)\left|\,{\log_{2}\left(\frac{\pi_{e}(z^{\prime}_{e}\mid
m)}{\pi_{e}^{\theta^{\prime}}(z^{\prime}_{e}\mid m)}\right)}\,\right|_{+}.$
(2)

Here, $|.|_{+}$ represents the positive part operator, which sets the negative
values to $0$. $\pi_{e}^{\theta}(Z\mid m)$ is the effect repertoire calculated
after partitioning the mechanism-purview pair into independent parts using the
partition $\theta\in\Theta(M,Z)$, $\Theta(M,Z)$ is the set of all the valid
partitions, and $\theta^{\prime}$ is the minimum information partition (MIP).
$\varphi_{e}(m,Z)$ quantifies how much the mechanism as a whole increases the
probability of the effect state $z^{\prime}_{e}$ compared to the MIP, which is
obtained as:

$\theta^{\prime}=\arg\min_{\theta\in\Theta(M,Z)}\frac{1}{\mathcal{N}(\theta)}\pi_{e}(z^{\prime}_{e}\mid
m)\left|\,{\log_{2}\left(\frac{\pi_{e}(z^{\prime}_{e}\mid
m)}{\pi_{e}^{\theta}(z^{\prime}_{e}\mid m)}\right)}\,\right|_{+}.$ (3)

The MIP is the partition $\theta\in\Theta(M,Z)$ that makes the least
difference to the effect repertoire relative to the maximum possible
difference achievable by that partition, $\mathcal{N}(\theta)$. Normalizing
the distance between $\pi_{e}(z^{\prime}_{e}\mid m)$ and
$\pi_{e}^{\theta}(z^{\prime}_{e}\mid m)$ by $\mathcal{N}(\theta)$ makes the
comparison between different partitions with different number of parts fair.
The value of $\mathcal{N}(\theta)$ will be derived shortly. If there exists a
partition for which the unpartitioned probability is less than or equal to the
partitioned probability, the mechanism is reducible to its parts and the
integrated effect information over purview $Z$ is $0$. We can further find the
most irreducible purview by finding

$z_{e}^{*}(m)=\arg\max_{\\{z^{\prime}_{e}\mid Z\subseteq
S\\}}\varphi_{e}(m,Z=z^{\prime}_{e}).$

$z_{e}^{*}(m)$ is the subset of units that mechanism $m$ as a whole makes the
most difference to. $\varphi_{e}(m)=\varphi_{e}(m,z_{e}^{*}(m))$ is the
difference that $m$ as a whole makes to its most irreducible purview, which is
referred to as the mechanism integrated effect information. Similar analysis
and procedure can be used to define the cause repertoire $\pi_{c}(Z_{t-1}\mid
M_{t}=m_{t})$ and the integrated cause information $\varphi_{c}(m)$ [1]. For a
detailed description of the definitions for the cause side, see S1 Appendix..
Finally, the overall integrated information of a mechanism is then defined as
$\varphi(m)=\min\\{\varphi_{e}(m),\varphi_{c}(m)\\}$. An irreducible mechanism
with its maximal cause and effect purviews are referred to as a _distinction_.

It is evident that the difference measure of the form $p(z\mid
m)\left|\,{\log_{2}(\frac{p(z\mid m)}{q(z\mid m)})}\,\right|_{+}$ plays a
central role in measuring $\varphi$. This was derived from the postulates of
IIT and was first introduced in [18]. In short, this measure satisfies the
following properties:  (i) The measure differs from $0$ only if the
probability of the state is increased.  (ii) The measure is not an aggregate
over all the states and reflects how much change is made in an individual
state.  (iii) In a scenario where $p(z_{1}\cup z_{2}\mid m)=p_{1}(z_{1}\mid
m)p_{2}(z_{2}\mid m)$, $q(z_{1}\cup z_{2}\mid m)=q_{1}(z_{1}\mid
m)q_{2}(z_{2}\mid m)$, and $p_{2}(z_{2}\mid m)=q_{2}(z_{2}\mid m)$, the
measure produces a smaller value for the purview $z_{1}\cup z_{2}$ than only
$z_{1}$. This scenario represents the case where $m$ makes no difference to a
subset of the purview $z_{2}$, therefore having this subset in the maximal
purview is discouraged.

We can look at this measure as the product of two terms. The first term,
$p(z\mid m)$, is referred to as selectivity, while the second term,
$\left|\,{\log_{2}(\frac{p(z\mid m)}{q(z\mid m)})}\,\right|_{+}$, is called
informativeness. Adding new units can never increase the selectivity,
therefore the measure is only increased if the new units increase the
informativeness enough. Variations of this measure have been used to define
integrated information of distinctions and systems [1, 2]. However, the
question of how large these measures can get remains open. In this section, we
first study the maximum integrated information achievable by a single
distinctions. Then we show why this upper bound cannot be achieved by all the
distinctions of a system, by studying a few important special cases.

Our working assumption to derive these bounds is that the system is realizable
by a TPM that is a product of unit TPMs (conditional independence). This is a
minimal assumption as both the definition of $\varphi$ and causal
marginalization process make use of such TPM [16, 1, 2]. Furthermore, we
consider systems consisting of binary units, but the results are generalizable
to non-binary units as well. In S2 Appendix., we show that our results still
hold even if we use slightly different difference measures such as point-wise
mutual information or Kullback–Leibler divergence.

###  2.1 Single mechanism

Before discussing our main results, we first need to present a few helpful
lemmas. Lemma 1 states how the process of causal marginalization places a
certain limit on the informativeness. Formally, given the set of units outside
the mechanism $W=S-M$, the effect repertoire of a single unit $Z_{i}\in Z$ is
defined as:

$\pi_{e}(Z_{i}\mid m)=\frac{1}{2^{|W|}}\sum_{w}p(Z_{i}\mid m,w),$ (4)

where $|W|=N-|M|$ is the number of units outside the mechanism. Furthermore,
the effect repertoire of $Z$ is defined as:

$\pi_{e}(Z\mid m)=\prod_{i}\pi_{e}(Z_{i}\mid m).$ (5)

Using this definition, it can be shown that:

######  Lemma 1.

Given two mechanisms $\bar{M}$ and $M$, such that $\bar{M}\subset M\subseteq
S$, and a single unit $Z_{i}$, we have:

$\left|\,{\log_{2}(\frac{\pi_{e}(Z_{i}=z_{i}\mid
m)}{\pi_{e}(Z_{i}=z_{i}\mid\bar{m})})}\,\right|_{+}\leq|M|-|\bar{M}|.$

All the proofs are provided in S3 Appendix.. $|M|-|\bar{M}|$ is the number of
units that need to be causally marginalized to calculate
$\pi_{e}(Z_{i}=z_{i}\mid\bar{m})$ from $\pi_{e}(Z_{i}=z_{i}\mid m)$, which can
also be thought of as the number of causal connections cut from the unit
$Z_{i}$. Throughout this manuscript, cutting a (causal) connection between a
unit at $t$ and a unit at $t+1$ refers to recalculating the conditional
probability distribution of the output by causally marginalizing out the input
unit. Furthermore, this bound does not depend on the state of the purview unit
$z_{i}$ and it holds for any state, not just the maximal state selected in Eq
(1). The result in Lemma 1 can be generalized as:

######  Lemma 2.

Given a mechanism $M$ in state $m$, a purview $Z$ in state $z$, and a
partition $\theta$, we have:

$\left|\,{\log_{2}(\frac{\pi_{e}(Z=z\mid m)}{\pi_{e}^{\theta}(Z=z\mid
m)})}\,\right|_{+}\leq\mathcal{N}(\theta),$

where $\mathcal{N}(\theta)$ is the total number of connections cut by the
partition $\theta$.

This result is general in the sense that it holds for any partitioning that
removes an arbitrary subset of connections, even if it does not divide the
mechanism-purview pair into independent parts. As shown in Eq (3), to find the
partition that makes the least difference, we normalize the difference between
the unpartitioned and partitioned repertoires by $\mathcal{N}(\theta)$. This
makes the comparison between the partitions that sever different number of
connections fair. Using Lemma 2 and the fact that the informativeness term is
a bound for the integrated information, we can readily state our first main
result. Theorem 1 states that the integrated information of mechanism $M$ over
a purview cannot be larger than the total number of potential connections
between them. This holds both for the cause and the effect sides.

######  Theorem 1.

For a mechanism $M\subseteq S$ in state $m$, a candidate cause purview $C$,
and a candidate effect purview $E$, we have:

$\displaystyle\varphi_{e}(m,E)\leq|M||E|\quad\text{and}\quad\varphi_{c}(m,C)\leq|M||C|,$

where $|E|$ and $|C|$ denote the size of the candidate effect and cause
purviews, respectively.

This provides us with our first upper bound for the sum of integrated
information of all the distinctions of a system:

$\sum_{M\subseteq S}\varphi(m)=\sum_{M\subseteq
S}\min\\{\varphi_{c}(m),\varphi_{e}(m)\\}\leq\sum_{M\subseteq
S}|M|N=N\sum_{|M|=1}^{N}|M|\binom{N}{|M|}=\frac{N^{2}}{2}2^{N}.$ (6)

And, if we are interested in the upper bound over unique purviews:

$\sum_{M\subseteq S}\varphi(m)\leq\sum_{M\subseteq
S}|M||Z^{*}(m)|\overset{(a)}{\leq}\sum_{M\subseteq
S}|M|^{2}=\sum_{|M|=1}^{N}|M|^{2}\binom{N}{|M|}=\frac{N(N+1)}{4}2^{N}.$ (7)

Inequality (a) follows from the fact that for any two sets $S_{1}$ and
$S_{2}$, $|S_{1}|^{2}+|S_{2}|^{2}\geq|S_{1}||S_{2}|+|S_{2}||S_{1}|$. This
means that in a scenario where each purview can be assigned to only one
mechanism, matching the sizes of the mechanisms and purviews maximizes the
upper bound. This scenario is an important special case, as it was studied in
[17] to explain how IIT can be used to account for the quality of certain type
of experiences, such as the spatial experience. In the next section, we will
show due to the constraints imposed by overlapping distinctions of different
sizes, also referred to as mechanisms of different orders, these bounds are
not achievable.

It is also worthwhile to mention that the results provided here for a single
mechanism are in line with the bounds for the system integrated information
defined in [2]. As shown in Theorem 1 in [2], the maximum achievable system
integrated information for a given partition is the number of connections cut
by that partition. This makes the overall maximum system integrated
information the maximum number of connections cut by any valid cut, which is
$|S|(|S|-1)$ for the system partitions considered in [2].

###  2.2 Inter-order constraints

In this section, we discuss how mechanisms that are either subsets or
supersets of each other place certain constraints on the maximum integrated
information achievable by them. For example, as already shown in Lemma 1, the
levels of determinism for a single purview unit given two different mechanisms
are bounded by each other, if one mechanism is a subset of the other. It can
also be shown that if a mechanism $M$ fully specifies its cause purview,
_i.e.,_ $\pi_{c}(Z=z^{*}\mid m)=1$, then any superset of that mechanism
$\bar{M}\supseteq M$ also fully specifies the same purview,
$\pi_{c}(Z\mid\bar{m})=1$. The same holds for the effect side as well.

######  Lemma 3.

Superset of a deterministic mechanism is deterministic. For two mechanisms
$M\subset\bar{M}\subseteq S$ and a single-unit purview $Z_{i}$, If
$\pi_{e}(Z_{i}=z_{i}\mid m)=1$, then $\pi_{e}(Z_{i}=z_{i}\mid\bar{m})=1$ and
if $\pi_{e}(Z_{i}=z_{i}\mid m)=0$, then $\pi_{e}(Z_{i}=z_{i}\mid\bar{m})=0$.

Such constraints can be exploited to show that the upper bound can only be
achieved by a subset of the mechanisms. Another important fact to keep in mind
is that $\varphi_{e}(m,Z=z)=|M||Z|$ is only achievable when $\pi_{e}(Z=z\mid
m)=1$. This is because this bound is derived for the informativeness term and
is only achievable when the selectivity term, $\pi_{e}(Z=z\mid m)$, is $1$:

######  Lemma 4.

If $\varphi_{e}(m,Z)=|M||Z|$ then $\pi_{e}(Z=z\mid m)=1$. Similarly, if
$\varphi_{c}(m,Z)=|M||Z|$ then $\pi_{c}(Z=z\mid m)=1$.

This is a very strict constraint if we want to construct a system such that
$\varphi_{e}(m)=\varphi_{e}(m,z_{e}^{*}(m))=|M||Z_{e}^{*}|$ for all the
mechanisms. In what follows, we show that even having a single mechanism-
purview pair that achieves this upper bound makes it impossible for a
significant number of other mechanism-purview pairs to achieve their maximum
integrated information.

######  Theorem 2.

$\varphi_{e}(\bar{m},\bar{Z})<|\bar{M}||\bar{Z}|$, if
$\varphi_{e}(m,Z)=|M||Z|$ and

  * •

$\bar{M}\subset M$ and $Z\cap\bar{Z}\neq\varnothing$, OR

  * •

$\bar{M}\supset M$ and $Z\cap\bar{Z}\neq\varnothing$.

Theorem 2 states that any subset or superset of $M$ cannot share purview units
with $M$ and still achieve the maximum, if $\varphi_{e}(m,Z)=|M||Z|$. Such
mechanisms can only achieve their maximal integrated information over disjoint
purviews. This makes it immediately clear why all the distinctions in a system
larger than $1$ unit cannot be maximally irreducible, as there are fewer
disjoint purview sets than all the mechanisms. As discussed in S1 Appendix.,
the same results hold for the integrated cause information as well. This makes
the bounds in (6) and (7) not achievable.

######  Corollary 1.

There is no system with larger than $1$ unit such that all the distinctions
are maximally integrated.

This is in line with our intuitive definition of integrated information.
$\varphi$ captures the difference that a mechanism makes over and beyond its
parts. Therefore, if parts (subsets) of a mechanism-purview pair are maximally
irreducible, the pair itself cannot be. For example, if there exist a
mechanism in the system that achieves maximum $\varphi_{e}$ over the entire
system, i.e. $|M||Z|=|M|N$, none of the subsets or supersets of that mechanism
can achieve maximum $\varphi_{e}$ over their corresponding purviews. Another
special case is when every single-unit mechanism achieves $\varphi_{e}=1$ over
itself. Again, this makes it impossible for all the other distinctions to have
maximum $\varphi_{e}$. In fact, in this case, the integrated effect
information for the rest of the distinctions will be $0$, as any mechanism-
purview pair is reducible to its parts.

###  2.3 Intra-order constraints

As outlined in the preceding sections, having a high selectivity is necessary
to have a large integrated information. For example, Lemma 4 states that
having selectivity of $1$ is necessary to achieve the maximal integrated
effect and cause information. This motivates us to study a special case that
is particularly important. Assume that in a system consisting of $N$ units,
all the mechanisms of size $K$ specify themselves with probability $1$,
_i.e.,_ $\pi_{e}(Z=z^{\prime}\mid m)=1$ where $Z=M$. Since the mechanisms of
size $K$ are not subsets or supersets of each other, Theorem 2 does not hold.
However, even in this setting, the _intra-order_ constraints prevent the
distinctions from achieving the maximum integrated information.

######  Theorem 3.

In a system $S$ consisting of $N$ units, for a given mechanism size $1<K<N$,
if $\pi_{e}(Z=z^{\prime}\mid m)=1,\forall M:|M|=K$, and the purview units are
the same as the mechanism units, _i.e.,_ $Z=M$, none of the mechanisms with
$|M|=K$ can achieve their maximum integrated effect information of
$|M||Z|=|M|^{2}$.

The theorem states that if all the mechanisms of size $K$ fully specify
themselves, their $\varphi$ cannot achieve its maximum. The only exceptions
are when there is only one such mechanism, $K=N$, or there is no overlap
between the mechanisms $K=1$. In S1 Appendix., we show that this result holds
for the integrated cause information as well.

Analyzing this setup helps us to understand how mechanisms that are not parts
of each other, but share parts, constrain each other. The proof for Theorem 3,
which is provided in S3 Appendix., is a constructive proof. Thus, it also
provides us with a procedure to construct a TPM that can achieve the maximum
possible integrated information in this setting. The main idea behind the
proof, and therefore the construction, is to use the definition of the effect
repertoire in (4) and (5) to characterize the TPM that can satisfy the
assumptions of the theorem. This both gives us the TPM and limits the maximum
attainable integrated effect information.

In S3 Appendix., we also show that the MIP for the system under consideration
can be found by evaluating only $\frac{K}{2}+1$ partitions, significantly
reducing the computations and making it feasible to calculate the integrated
information of such distinctions in larger networks. In section 4, we show
that the integrated effect information in this system is much less than the
number of connections by numerically evaluating the $\frac{K}{2}+1$ candidate
partitions. We can employ this linear time numerical evaluation to calculate
the sum of integrated effect information over all the mechanisms in a
hypothetical system where all the mechanisms of any size have themselves as
the most irreducible purview with selectivity $1$ (not just all the mechanisms
of size $K$). This gives us a numerical upper bound for reflexive systems,
_i.e.,_ systems in which every mechanism has itself as the purview. We will
provide experiments to show how this computationally light numerical bound is
tight and may in fact hold in general.

##  3 Upper bounds for relation integrated information

Any mechanism $m$ with its maximally irreducible cause and effect purviews
defines a causal distinction $d(m)=(z^{*}(m),\varphi_{d}(m))$, where
$z^{*}(m)=\left(z^{*}_{c}(m),z^{*}_{e}(m)\right)$ contains the maximally
irreducible cause and effect purviews in their maximal states.

Causal relations are defined over subsets of the causal distinctions. If we
define the set of all the valid distinctions of a candidate system as
$\mathcal{D}$, a subset of distinctions $\boldsymbol{d}\subseteq\mathcal{D}$
forms a relation if the cause purview, the effect purview, or both the cause
and the effect purviews of each distinction overlap over the same units in the
same states. This definition includes the special case of a self-relation
where the cause and effect purviews of the same distinction overlap
congruently over a set of units. This means a system consisting of $N$ units
can potentially contain as many as $2^{2^{N}-1}-1$ causal relations. Any
nonempty subset of units can define a distinction and any nonempty subset of
distinctions can potentially define a relation. Here we discuss the bound on
the integrated information of a single relation and the sum of relations’
integrated information, given a bound on the sum of distinctions’ integrated
information. This makes the analysis in this section mostly independent of the
results in the previous sections, as the final results holds for any bound on
the sum of distinctions’ integrated information.

In [1], it is shown that we can write the relation integrated information of a
set of distinctions $\boldsymbol{d}\subseteq\mathcal{D}$ with
$|\boldsymbol{d}|\geq 2$ as:

$\varphi_{r}(\boldsymbol{d})=\left|\bigcap_{(z^{*},\varphi_{d})\in\boldsymbol{d}}\big{(}z^{*}_{c}\cup
z^{*}_{e}\big{)}\right|\min_{(z^{*},\varphi_{d})\in\boldsymbol{d}}\frac{\varphi_{d}}{|z^{*}_{c}\cup
z^{*}_{e}|}.$ (8)

Both the intersection and the union operators consider both the units in the
purview and the state of units. If there is no congruent overlap among the
purviews of the distinctions
$\bigcap_{(z^{*},\varphi_{d})\in\boldsymbol{d}}\big{(}z^{*}_{c}\cup
z^{*}_{e}\big{)}$, and therefore $\varphi_{r}(\boldsymbol{d})$, would be zero.
For the special case of self-relations, $|\boldsymbol{d}|=1$, the relation
integrated information of a distinction $d$ is calculated as:

$\varphi_{r}(d)=\left|z^{*}_{c}\cap
z^{*}_{e}\right|\frac{\varphi_{d}}{|z^{*}_{c}\cup z^{*}_{e}|}.$ (9)

Our first observation is that the relation integrated information of any
subset of distinctions $\boldsymbol{d}$ cannot be larger than the smallest
distinction’s integrated information

$\varphi_{r}(\boldsymbol{d})\leq\min_{(z^{*},\varphi_{d})\in\boldsymbol{d}}\varphi_{d}$

This is because the relation overlap
$\left|\bigcap_{(z^{*},\varphi_{d})\in\boldsymbol{d}}\big{(}z^{*}_{c}\cup
z^{*}_{e}\big{)}\right|$ is always smaller than the $|z^{*}_{c}\cup
z^{*}_{e}|$ of all the distinctions involved. Therefore, to maximize the
integrated information of an individual relation or the sum of integrated
information of all the relations, we need to maximize the integrated
information of all the distinctions. However, as discussed in Section 2, due
to inter-order and intra-order constraints, all the distinctions cannot
achieve their maximum. Therefore, we study the problem of how we can maximize
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$, given
that $\sum_{d\in\mathcal{D}}\varphi_{d}$ is bounded by a certain value. For
that, we first derive an upper bound for
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$ for any
given set of cause and effect purviews. Then, we will discuss how we can
maximize the upper bound by properly distributing
$\sum_{d\in\mathcal{D}}\varphi_{d}$ over all the distinctions. This provides
us with a measure to compare different cause effect structures in terms of
their maximum achievable
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$. Then,
we will use this bound to derive a bound for
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$.

In [1], it is shown that we can write
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$ as a
linear combination of distinctions’ integrated information by defining
$\mathcal{Z}(o)$ as:

$\mathcal{Z}(o)=\\{(z,\varphi):z=z^{*}_{c}\cup
z^{*}_{e},((z^{*}_{c},z^{*}_{e}),\varphi)\in\mathcal{D},o\in z^{*}_{c}\cup
z^{*}_{e}\\}.$ (10)

$o$ is an arbitrary unit in a arbitrary state in the system. Each element in
$\mathcal{Z}(o)$ is a tuple that contains $z^{*}_{c}\cup z^{*}_{e}$ and the
integrated information of a distinction that contains $o$ in either its cause
or effect purview. This definition helps us to rewrite
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$ as [1]:

$\small\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})=\sum_{\begin{subarray}{c}\boldsymbol{d}\subseteq\mathcal{D}\\\
|\boldsymbol{d}|=1\end{subarray}}\varphi_{r}(\boldsymbol{d})+\sum_{\begin{subarray}{c}\boldsymbol{d}\subseteq\mathcal{D}\\\
|\boldsymbol{d}|\geq
2\end{subarray}}\varphi_{r}(\boldsymbol{d})=\sum_{\begin{subarray}{c}\boldsymbol{d}\subseteq\mathcal{D}\\\
|\boldsymbol{d}|=1\end{subarray}}\varphi_{r}(\boldsymbol{d})+\sum_{o}\sum_{i=1}^{|\mathcal{Z}(o)|}\frac{\varphi_{(i)}}{|z_{(i)}|}(2^{|\mathcal{Z}(o)|-i}-1).$
(11)

The total sum is reformulated as the sum of the integrated information of
self-relations and a linear combination of $\frac{\varphi_{(i)}}{|z_{(i)}|}$
of the distinctions. $\frac{\varphi_{(i)}}{|z_{(i)}|}$ denotes sorted indexing
of the elements in $\mathcal{Z}(o)$, such that $(z_{(1)},\varphi_{(1)})$ has
the smallest $\frac{\varphi}{|z|}$ ratio, $(z_{(2)},\varphi_{(2)})$ has the
second smallest $\frac{\varphi}{|z|}$ ratio, and so on. The first summation in
the last term sums over all the units in all their possible states.

To find an upper bound
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$ for
given set of cause and effect purviews, we can simplify the objective function
by finding the maximum of each term in the sum separately. The maximization is
over the values of the distinction integrated information:

$\small\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})\leq\max\sum_{\begin{subarray}{c}\boldsymbol{d}\subseteq\mathcal{D}\\\
|\boldsymbol{d}|=1\end{subarray}}\varphi_{r}(\boldsymbol{d})+\sum_{o}\max\sum_{i=1}^{|\mathcal{Z}(o)|}\frac{\varphi_{(i)}}{|z_{(i)}|}(2^{|\mathcal{Z}(o)|-i}-1)$
(12)

The first is bounded by

$\sum_{\begin{subarray}{c}\boldsymbol{d}\subseteq\mathcal{D}\\\
|\boldsymbol{d}|=1\end{subarray}}\varphi_{r}(\boldsymbol{d})\leq\sum_{d\in\mathcal{D}}\varphi_{d}.$

This is because, as we just discussed, the integrated information of a self-
relation is less than its distinction integrated information. We can further
find the maximum for the second term in the objective function by solving the
following problem for a given $o$:

$\displaystyle\max$
$\displaystyle\sum_{i=1}^{|\mathcal{Z}(o)|}\frac{\varphi_{(i)}}{|z_{(i)}|}(2^{|\mathcal{Z}(o)|-i}-1),$
(13) subject to
$\displaystyle\sum_{i=1}^{|\mathcal{Z}(o)|}\frac{\varphi_{(i)}}{|z_{(i)}|}\leq
S(o)$

Even though the value of $S(o)$ is not known, we can find the optimal
distribution of $\sum_{d\in\mathcal{D}}\varphi_{d}$ over all the distinctions
and study the trade-off between $S(o)$ and $|\mathcal{Z}(o)|$. The inter- and
intra-order constraints among the distinctions, studied in the previous
section, determine the exact value of $S(o)$ for a given set of distinctions.
To solve the optimization problem in (13), we need to formalize the constraint
that $\frac{\varphi_{(i)}}{|z_{(i)}|}$ is non-decreasing and non-negative by a
change of variable as follows:

$\displaystyle\frac{\varphi_{(1)}}{|z_{(1)}|}=x_{1},\frac{\varphi_{(2)}}{|z_{(2)}|}=x_{1}+x_{2},\dots,\frac{\varphi_{(i)}}{|z_{(i)}|}=\sum_{j=1}^{i}x_{j},$
$\displaystyle x_{j}\geq 0,\forall j$

In other words, we are defining
$\frac{\varphi_{(i)}}{|z_{(i)}|}=\frac{\varphi_{(i-1)}}{|z_{(i-1)}|}+x_{i}$,
where $x_{i}$ is a non-negative value. This translates the problem in (13)
into:

$\displaystyle\max$
$\displaystyle\sum_{i=1}^{|\mathcal{Z}(o)|}(2^{|\mathcal{Z}(o)|-i}-1)\sum_{j=1}^{i}x_{j},$
(14) subject to
$\displaystyle\sum_{i=1}^{|\mathcal{Z}(o)|}\sum_{j=1}^{i}x_{j}=\sum_{i=1}^{|\mathcal{Z}(o)|}(|\mathcal{Z}(o)|-i+1)x_{i}\leq
S(o)$ $\displaystyle x_{i}\geq 0,\ i=1,\dots,|\mathcal{Z}(o)|.$

This is an easy problem to solve, as it includes maximizing a linear function
of $|\mathcal{Z}(o)|$ variables, given $|\mathcal{Z}(o)|+1$ linear
constraints. The solution to the problem is one of the $|\mathcal{Z}(o)|+1$
vertices defined by the constraints. The first vertex is $x_{i}=0,\forall i$,
which is the trivial minimum of the problem. The rest of the vertices have the
same property that for some $k$, $x_{k}=\frac{S(o)}{|\mathcal{Z}(o)|-k+1}$ and
$x_{i}=0,i\neq k$. For such vertex, the value of the objective function is:

$\frac{S(o)}{|\mathcal{Z}(o)|-k+1}\sum_{i=k}^{|\mathcal{Z}(o)|}(2^{|\mathcal{Z}(o)|-i}-1)=S(o)\left(\frac{2^{|\mathcal{Z}(o)|-k+1}}{|\mathcal{Z}(o)|-k+1}(1-\frac{1}{2^{|\mathcal{Z}(o)|}})-1\right).$

This value is monotonically decreasing with $k$, which means the maximum
occurs at the vertex where $x_{1}=\frac{S(o)}{|\mathcal{Z}(o)|}$ and
$x_{i}=0,i=2,\dots,|\mathcal{Z}(o)|$. This corresponds to a system where all
the distinctions in $\mathcal{Z}(o)$ have the same $\frac{\varphi}{|z|}$
value, i.e.
$\frac{\varphi_{(i)}}{|z_{(i)}|}=\frac{S(o)}{|\mathcal{Z}(o)|},\forall i$. In
other words, if we distribute the sum, $S(o)$, such that the distinction
integrated information is proportional to its $|z^{*}_{c}\cup z^{*}_{e}|$ for
all the distinctions, we can achieve the maximum value of:

$S(o)\left(\frac{2^{|\mathcal{Z}(o)|}}{|\mathcal{Z}(o)|}(1-\frac{1}{2^{|\mathcal{Z}(o)|}})-1\right).$
(15)

This expression also describes the trade-off between the number of
distinctions that contain an specific purview unit $o$ and the sum of their
$\frac{\varphi_{(i)}}{|z_{(i)}|}$. This value increases rapidly with the
number of purviews over $o$, but due to the inter- and intra-order
constraints, $S(o)$ might decrease. As long as the rate of decrease for $S(o)$
is less than $\frac{|\mathcal{Z}(o)|}{2^{|\mathcal{Z}(o)|}}$, adding new
distinctions to $\mathcal{Z}(o)$ results in larger
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$.

Plugging this result back into (12), we get:

$\displaystyle\small\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})\leq\sum_{d\in\mathcal{D}}\varphi_{d}+\sum_{o}S(o)\left(\frac{2^{|\mathcal{Z}(o)|}}{|\mathcal{Z}(o)|}(1-\frac{1}{2^{|\mathcal{Z}(o)|}})-1\right).$
(16)

We can further use the bound derived in Section 2.1, _i.e.,_
$\varphi_{e}\leq|M||z_{e}|,$ into the definition of $S(o)$, by noticing that
for any distinction $\varphi\leq\varphi_{e}$ and $|z^{*}_{c}\cup
z^{*}_{e}|\geq|z^{*}_{e}|$. This means for any distinction
$\frac{\varphi}{|z^{*}_{c}\cup
z^{*}_{e}|}\leq\frac{\varphi_{e}}{|z^{*}_{e}|}\leq|M|$. More specifically, we
have:

$\displaystyle|\mathcal{Z}(o)|$ $\displaystyle\leq 2^{N}-1,$
$\displaystyle\sum_{i=1}^{|\mathcal{Z}(o)|}\frac{\varphi_{(i)}}{|z_{(i)}|}$
$\displaystyle\leq\sum_{|M|=1}^{N}|M|\binom{N}{|M|}=\frac{N}{2}2^{N}.$

Using the above values for $|\mathcal{Z}(o)|$ and $S(o)$, as well as the bound
in (6), we get:

$\displaystyle\small\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})\leq\frac{N^{2}}{2}2^{N}+N^{2}2^{N}\left(\frac{2^{2^{N}-1}}{2^{N}-1}(1-\frac{1}{2^{2^{N}-1}})-1\right).$
(17)

The rate of increase for this bound is $\mathcal{O}(N^{2}2^{2^{N}})$. However,
in Section 2.2 and 2.3, we studied a few special cases and showed that this
bound is not achievable. We could have arrived at the same rate of growth by
noticing that the maximum number of relations is $2^{2^{N}-1}-1$ and the
maximum value for distinction integrated information is $N^{2}$. However, the
main significance of the solution studied in this section is that it
translates the problem of finding a bound
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$ to the
easier of problem finding a tighter bound for $S(o)$. In other words, Eq (16)
readily gives us the bound for
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$, for
any given bound for $S(o)$. Deriving a tighter bound for any arbitrary set of
distinctions that share a common purview unit leads to a tighter bound for
$\sum_{\boldsymbol{d}\subseteq\mathcal{D}}\varphi_{r}(\boldsymbol{d})$ and
remains an open problem.

##  4 Numerical experiments

In this section, we provide numerical evaluations of the bounds discussed
above, as well as experiments illustrating how tight the bounds are. The
calculations were performed using the freely available PyPhi toolbox111 The
code for PyPhi is available at https://github.com/wmayner/pyphi [19]. Fig 1(a)
shows the distinction integrated information of distinctions in the system
discussed in Section 2.3. The solid lines represent the integrated effect
information, $\varphi_{e}^{*}(K)$, of a mechanism of size $K$ over itself, if
all such mechanisms specify themselves with probability $1$. In this setting
the mechanism size is same as the purview size. The dotted line represent the
upper bound if we consider the mechanisms in isolation, which is simply the
number of connections, _i.e.,_ $K^{2}$. For mechanism size of $K=N$ and $K=1$,
where there is no overlap among the mechanisms, this upper bound is
achievable. However, when the mechanisms share parts with each other, the
integrated effect information cannot get close to the $K^{2}$ bound. For a
fixed mechanism size $K$, if we increase the system size $N$, the maximum
achievable $\varphi_{e}$ decreases. This is because in a larger system, there
are more mechanisms of size $K$, making each mechanism compete with
combinatorially more mechanisms. This figure also shows that for a fixed
system size $N$, the maximum achievable $\varphi_{e}$ increases with the
mechanism/purview size. However, this can be misleading. For example, although
the mechanisms of size $K=N$ can achieve the largest $\varphi_{e}$ value, they
are the least numerous mechanisms.

(a)

(b)

Fig 1: Upper bounds for integrated effect information $\varphi_{e}$ vs the
value achieved by the proposed construction, for different mechanism/purview
size $K=1,\dots,12$. In this setting, the mechanism is same as the purview.
The dotted line represents the upper bound if we consider each mechanism in
isolation, which is the number of connections. The solid lines represent the
integrated effect information achieved the proposed TPM construction,
$\varphi_{e}^{*}(K)$. 1(a) $\varphi_{e}^{*}(K)$ for a single mechanism of size
$K$ and 1(b) $\sum\varphi_{e}^{*}(K)$ summed over all the mechanisms of size
$K$ in a system of size $N$. This figure shows that the derived bound is
achievable when the mechanisms do not share parts. Also, in larger systems,
mechanisms of size close to $\frac{N}{2}$ achieve the maximum
$\sum\varphi_{e}^{*}(K)$, as they are the most numerous ones.

To emphasize this point, Fig 1(b) illustrates the sum of integrated effect
information of all the mechanisms of size $K$, _i.e.,_
$\binom{N}{K}\varphi_{e}^{*}(K)$. This figure shows that although larger
mechanisms can achieve higher $\varphi_{e}$, if the goal is to maximize
$\sum\varphi_{e}$, it is better to maximize the integrated information of the
more numerous mechanisms. For example, for the system size of $N=12$, the
maximum $\binom{N}{K}\varphi_{e}^{*}(K)$ is achieved when $K=7$, which also
illustrates the trade-off between the achievable $\varphi_{e}$ and the number
of mechanisms. Although mechanisms of size $7$ are less numerous than
mechanisms of size $6$, each of them can achieve larger integrated effect
information.

Fig 1(b) exhibits the maximum achievable $\sum\varphi_{e}(m)$ for a _specific_
mechanism size, when all such mechanisms fully specify themselves. Fig 2 shows
the sum of integrated information over all the mechanisms, if mechanisms of
certain size fully specify themselves. For each system size $N$, $N$ different
TPMs are constructed, each representing a system where all the mechanisms of
size $K$ have selectivity of $1$, $K=1,\dots,N$. The dotted lines represent
$\sum_{K=1}^{N}\binom{N}{K}\varphi_{e}^{*}(K)$. This value represents a
hypothetical system in which all the mechanisms have selectivity of $1$ over
themselves and can achieve their maximum $\varphi_{e}$. We can use this value
as a numerical upper bound.

As shown in S3 Appendix., to evaluate $\varphi_{e}^{*}(K)$, we need to compute
only $\frac{K}{2}+1$ partitions, making the computational complexity of
calculating $\sum_{K=1}^{N}\binom{N}{K}\varphi_{e}^{*}(K)$ quadratic in $N$.
The solid lines in the figure is the achieved sum of integrated effect
information $\sum_{M\subseteq S}\varphi_{e}(m)$, and the markers represent the
achieved sum of integrated information $\sum_{M\subseteq
S}\varphi(m)=\sum_{M\subseteq S}\min\\{\varphi_{e}(m),\varphi_{c}(m)\\}$. It
is evident that the sum bound is tight, as $\sum_{M\subseteq S}\varphi_{e}(m)$
and $\sum_{M\subseteq S}\varphi(m)$ can get very close to the bound. This
figure shows that we can exploit the symmetries and the constraints on the
system to find good approximations of $\sum_{M\subseteq S}\varphi(m)$ with
significantly less computation.

Fig 2: Sum of integrated effect information $\sum_{M\subseteq
S}\varphi_{e}(m)$ and sum of integrated information $\sum_{M\subseteq
S}\varphi(m)$ for a system in which all the mechanisms of size $K$ specify
themselves with probability $1$, _i.e.,_ selectivity is $1$, for different
system sizes $N=4,\dots,8$. In this setting, the mechanism is same as the
purview. The dotted line is the numerical bound derived in Section 2.3 the
solid line is $\sum_{M\subseteq S}\varphi_{e}(m)$ achieved by the proposed TPM
construction, and markers denote $\sum_{M\subseteq S}\varphi(m)$ achieved by
the construction. The bound is a tight upper bound for $\sum_{M\subseteq
S}\varphi_{e}(m)$, and $\sum_{M\subseteq S}\varphi_{e}(m)$ is the same as
$\sum_{M\subseteq S}\varphi(m)$. Furthermore, in larger systems, both of the
sums are maximized when mechanisms of size close to $\frac{N}{2}$ have
selectivity of $1$.

Table 1 summarizes the bounds discussed in this paper. Bound I and Bound II
are the bounds derived in Eq (6) and Eq (7), respectively. They represent the
absolute upper bounds without considering the inter- and intra-order
constraints. To calculate their corresponding bound of the sum of relations’
integrated information, the closed form sum in Eq (11) is used, excluding the
self-relation term for a less cluttered presentation. It is worthwhile to
mention that each of the rows in Table 1 can be used to calculate its
corresponding bound on $\Phi$, which is the sum of integrated information of
all the distinctions and the relations.

Bound III corresponds to the hypothetical system discussed in Section 2.3,
where all the mechanisms can achieve the maximal integrated effect information
over themselves while having a selectivity of $1$. As discussed earlier,
$\sum_{K=1}^{N}\binom{N}{K}\varphi_{e}^{*}(K)$ can be used as a tight upper
bound for the sum of distinctions’ integrated information in such system. To
numerically calculate its corresponding bound for $\sum\varphi_{r}$, we
further assumed $Z_{c}=S$ for all the distinctions and used Eq (11). This
assumption makes the number of relations in this system the same as the number
of relations in Bound I, as all the distinctions are related over their cause
purviews. This makes the $\sum\varphi_{r}$ in Bounds I and III grow at a
similar rate. Next, we will show Bound III is tight for both $\sum\varphi_{d}$
and $\sum\varphi_{r}$ of the proposed construction and may in fact be a
general bound.

Table 1:  The bounds for the sum of distinctions integrated information $\sum\varphi_{d}$ and the sum of relations integrated information $\sum\varphi_{r}$. | Description | $\sum\varphi_{d}$ | $\mathcal{O}(\sum\varphi_{d})$ | $\sum\varphi_{r}$ | $\mathcal{O}(\sum\varphi_{r})$
---|---|---|---|---|---
Bound I (not achievable) |  $\forall M\subseteq S,\phi_{d}=|M||S|$ $Z_{e}^{*}=Z_{c}^{*}=S$ | $\frac{N^{2}}{2}2^{N}$ | $N^{2}2^{N}$ | $N\sum_{K}K\left(2^{\sum_{j=K}^{N}\binom{N}{j}}(1-0.5^{\binom{N}{K}})-\binom{N}{K}\right)$ | $N^{2}2^{2^{N}}$
Bound II |  $\forall M\subseteq S,\phi_{d}=|M|^{2}$ $Z_{e}^{*}=Z_{c}^{*}=M$ | $\frac{N(N+1)}{4}2^{N}$ | $N^{2}2^{N}$ | $N\sum_{K}K\left(2^{\sum_{j=K-1}^{N-1}\binom{N-1}{j}}(1-0.5^{\binom{N-1}{K-1}})-\binom{N-1}{K-1}\right)$ | $N^{2}2^{2^{N-1}}$
Bound III |  The numerical bound derived in Section 2.3 | N/A | $2^{N}$ | N/A | $2^{2^{N}}$

Fig 3 illustrates how the upper bounds and the maximum achievable
$\sum_{M\subseteq S}\varphi(m)$ by different TPM construction methods grow as
we increase the system size $N$. The TPMs are constructed by the following
methods:  (i) High selectivityrefers to the construction discussed in Section
2.3 and Theorem 3. As shown in S3 Appendix., the TPM corresponding to this
construction only contains $0$s and $1$s.  (ii) Random
deterministicconstruction fills the TPM entries with only $0$s and $1$s at
random. The probability of an entry being one is drawn from a uniform
distribution over $[0,1]$.  (iii) Randomconstruction draws the entries of the
TPM from a uniform distribution over $[0,1]$.  (iv) Hammingis the decoding
procedure of the famous $(7,4)$ Hamming code. In a system of $7$ units, the
state at time $t+1$ is the closest valid codeword to the state at time $t$
with probability $1$. This construction has been suggested as a good candidate
system for high integrated information [13].

Fig 3 shows that both the numerical upper bound and the achievable values for
the proposed construction scale almost exponentially with the system size $N$
and at the rate of $\mathcal{O}(2^{N})$. For both of the random constructions,
the maximum sum achieved over $100$ runs is reported in the figure. This
figure shows that generally deterministic TPMs achieve higher sum of
integrated information, compared to nondeterministic TPMs. This is because to
achieve large $\varphi$, selectivity close to $1$ is necessary (see Lemma 4)
and to have selectivity of $1$, TPM entries need to be $1$ or $0$ (see Lemma
7). This figure also suggests that the numerical upper bound derived in
Section 2.3, _i.e.,_ $\sum_{K}\binom{N}{K}\varphi_{e}^{*}(K)$, might be a
general upper bound for any system, not just for high selectivity regime. The
generality of this upper bound remains to be investigated.

Fig 3: Growth of different upper bounds for the sum of distinctions’
integrated information w.r.t the system size $N$, as well as the maximum
achievable $\sum_{M\subseteq S}\varphi(m)$ by different TPM construction
methods. The derived numerical upper bound grows almost exactly as $2^{N}$.
$\sum_{M\subseteq S}\varphi(m)$ achievable by the proposed construction grows
exponentially with $N$ as well. The deterministic TPMs, _i.e.,_ TPMs
containing only $0$s and $1$s, outperform nondeterministic TPMs. The scale of
the $y$-axis is logarithmic.

Finally, Fig 4 illustrates the bounds and the achievable values for the sum of
integrated information of relations in a system. Similar to the distinctions
case the proposed construction can get very close to its bound. Furthermore,
this figure shows that higher sum of distinctions integrated information does
not translate to higher sum of relations integrated information. For example,
unlike Fig 3, bound III is larger than bound II in Fig 4. This is because
having larger purviews increases the number of relations exponentially, making
the purview sizes, not the integrated information value, the dominant factor
in the sum of relations integrated information. Due to the super exponential
growth of the number of the relations in terms of the number of the units, we
used double-logarithmic scale for the $y$-axis.

Fig 4: Growth of different upper bounds for the sum of relations’ integrated
information w.r.t the system size $N$, as well as the maximum achievable
values by different TPM construction methods. The derived numerical upper
bound and $\sum_{M\subseteq S}\varphi(m)$ achievable by the proposed
construction grow super exponentially with $N$. The scale of the $y$-axis is
double-logarithmic.

##  5 Discussion and future directions

In this manuscript, we presented the upper bounds for the integrated
information of relations and distinctions under various conditions.
Theoretical results were given for the maximum integrated information that a
single distinction can attain and the conditions required to achieve it.
Moreover, we demonstrated that the inter- and intra-order constraints impose
certain limits on the maximum integrated information. For instance, we proved
that a mechanism-purview pair cannot be maximally irreducible if there is a
superset or subset of it that is also maximally irreducible. In Section 2.3,
we studied the upper bound for the integrated information of the distinctions
in a system, provided that all the mechanisms fully specify their own state in
the next time step. This scenario was inspired by our analysis of mechanisms
in Sections 2.1 and 2.2 and was used to study the intra-order constraints. We
also provided the upper bound for the sum of the integrated information of
relations as a function of the distinctions’ integrated information. Our
analysis can be directly used to derive upperbunds for $\Phi$, which is
defined as the sum of the integrated information of distinctions and relations
[1].

To our knowledge, this is the first attempt at finding upper bounds and
optimal transition probability matrices (TPMs) that maximize the integrated
information. The provided results and the lines of proof can pave the way for
future research and can be used to design systems that achieve high integrated
information. For example in the proof of Theorem 3, we provide a TPM
construction method that maximizes the distinction integrated information
under certain assumptions. Similar techniques can be used to design optimal
TPMs satisfying other assumptions.

Our analysis can also be helpful to compare different families of networks,
_e.g._ , random vs homogeneous connectivity. This can lead to better
understanding of which areas of brain can have higher integrated information.
For example, in Section 3, we derive a bound for the sum of relations
integrated information for any set of cause and effect purviews. This can be
used to show certain connectivity profiles can lead to more relations among
their distinctions. Our results showed that the sum of integrated information
of relations is maximized when the distinctions’ integrated information are
proportional to the size of their purviews. This means distinctions with the
same size of purview should have the same value of integrated information.
Such regularity is not attainable in systems with random connectivity profile,
but can potentially be achieved in systems with homogeneous grid-like
connectivity.

Furthermore, some of the techniques introduced here can be employed to develop
approximate or exact measures of integrated information for mechanisms,
systems, or relations. For instance, In S3 Appendix., we show that under
certain assumptions the normalized partitioned integrated information is
simplified to average information gain over all the severed connections. This
can potentially be used in conjunction with exact or approximate subset
selection algorithms to find the optimal partition in a more computationally
feasible manner. In this work, we used this technique and the symmetries in
the system to reduce the number of candidate partitions significantly, from
more than exponential to linear in size of the mechanism.

More generally, our results have implications outside the field of theoretical
neuroscience, such as finding the signatures of complexity in biological and
artificial networks. There has been increasing interest in IIT as a formal
framework to study complex systems and non-linear dynamics [20, 12, 9, 10,
11]. Therefore, our results and analysis can also be extended to the field of
complexity science and to potentially derive approximate or heuristic measures
of complexity [21, 22, 23]. In S2 Appendix., we show that the results provided
here are still relevant even if other distance measures, such as point-wise
mutual information or KL divergence, are used for quantifying the integrated
information.

There are also many questions left open to be explored. The results provided
here are state-dependent, meaning that they are achievable only in one state
of the system and/or the mechanism. The problem of finding the conditions
under which the systems and the mechanisms can achieve high integrated
information in more than one state is open to investigation. Also, as shown in
Section 2, we can make the distinction bound tighter by considering the inter-
and intra-order constraints. In Section 2.3, we developed a linear time method
to evaluate the integrated information in a special class of systems and
numerically showed that the this bound is much smaller than the bound without
considering the constraints. Finding a closed form solution for such systems
remains an open problem. In general, finding a closed form solution for the
bound on sum of the integrated information of any arbitrary subset of
distinctions is an interesting problem and can be used in conjunction with our
results in Section 3 to derive tighter bounds for sum of integrated
information of relations.

Furthermore, in our derivation of the bounds we mainly focused on the
integrated effect information, as the bound for $\varphi_{e}$ is a bound for
$\varphi_{d}$ as well. In S1 Appendix., we show that most of our results are
applicable to the integrated cause information as well. However, there are
dependencies among the cause and effect side that can potentially be used to
make the overall bounds tighter.

## Supporting information

#### S1 Appendix.

Integrated cause information. Definition of the integrated cause information
and description of how the results for integrated effect information can be
translated to the integrated cause information.

#### S2 Appendix.

Using other difference measures. Describes how the results change if other
difference measures, such as KL divergence, are used for comparing the
distributions.

#### S3 Appendix.

Proofs

## Acknowledgments

The authors thank Larissa Albantakis, William Marshall, Leonardo Barbosa, and
Erick Chastain for helpful discussions and comments on earlier drafts of this
article, and Will Mayner for maintaining PyPhi, his advice on implementing the
experiments, and his helpful comments. In addition, this research was
supported by the Templeton World Charity Foundation (grant number TWCF0216)
and by the Tiny Blue Dot Foundation (UW 133AAG3451; G.T.).

## References

  * 1. Albantakis L, Barbosa L, Findlay G, Grasso M, Haun AM, Marshall W, et al.  Integrated information theory (IIT) 4.0: Formulating the properties of phenomenal existence in physical terms. 2022;doi:10.48550/arxiv.2212.14787.
  * 2. Marshall W, Grasso M, Mayner WGP, Zaeemzadeh A, Barbosa LS, Chastain E, et al.  System Integrated Information.  Entropy 2023, Vol 25, Page 334. 2023;25(2):334.  doi:10.3390/E25020334.
  * 3. Tononi G, Boly M, Massimini M, Koch C.  Integrated information theory: from consciousness to its physical substrate.  Nature Reviews Neuroscience 2016 17:7. 2016;17(7):450–461.  doi:10.1038/nrn.2016.44.
  * 4. Casali AG, Gosseries O, Rosanova M, Boly M, Sarasso S, Casali KR, et al.  A theoretically based index of consciousness independent of sensory processing and behavior.  Science Translational Medicine. 2013;5(198).  doi:10.1126/SCITRANSLMED.3006294/SUPPL_FILE/5-198RA105_SM.PDF.
  * 5. Haun AM, Oizumi M, Kovach CK, Kawasaki H, Oya H, Howard MA, et al.  Conscious Perception as Integrated Information Patterns in Human Electrocorticography.  eNeuro. 2017;4(5).  doi:10.1523/ENEURO.0085-17.2017.
  * 6. Gallimore AR.  Restructuring consciousness -The psychedelic state in light of integrated information theory.  Frontiers in Human Neuroscience. 2015;9(June):346.  doi:10.3389/FNHUM.2015.00346/BIBTEX.
  * 7. Lee U, Kim S, Noh GJ, Choi BM, Mashour GA.  Propofol Induction Reduces the Capacity for Neural Information Integration: Implications for the Mechanism of Consciousness and General Anesthesia.  Nature Precedings 2008. 2008; p. 1–1.  doi:10.1038/npre.2008.1244.2.
  * 8. Leung A, Cohen D, Van Swinderen B, Tsuchiya N.  Integrated information structure collapses with anesthetic loss of conscious arousal in Drosophila melanogaster.  PLOS Computational Biology. 2021;17(2):e1008722.  doi:10.1371/JOURNAL.PCBI.1008722.
  * 9. Albantakis L, Hintze A, Koch C, Adami C, Tononi G.  Evolution of Integrated Causal Structures in Animats Exposed to Environments of Increasing Complexity.  PLOS Computational Biology. 2014;10(12):e1003966.  doi:10.1371/JOURNAL.PCBI.1003966.
  * 10. Albantakis L.  Quantifying the Autonomy of Structurally Diverse Automata: A Comparison of Candidate Measures.  Entropy 2021, Vol 23, Page 1415. 2021;23(11):1415.  doi:10.3390/E23111415.
  * 11. Mediano PAM, Rosas FE, Farah JC, Shanahan M, Bor D, Barrett AB.  Integrated information as a common signature of dynamical and information-processing complexity. 2021;.
  * 12. Tajima S, Kanai R.  Integrated information and dimensionality in continuous attractor dynamics.  Neuroscience of Consciousness. 2017;2017(1).  doi:10.1093/NC/NIX011.
  * 13. Tegmark M.  Consciousness as a state of matter.  Chaos, Solitons & Fractals. 2015;76:238–270.  doi:10.1016/J.CHAOS.2015.03.014.
  * 14. Barrett AB.  An integration of integrated information theory with fundamental physics.  Frontiers in Psychology. 2014;5(FEB):63.  doi:10.3389/FPSYG.2014.00063/BIBTEX.
  * 15. Albantakis L, Prentner R, Durham I.  Computing the Integrated Information of a Quantum Mechanism.  Entropy 2023, Vol 25, Page 449. 2023;25(3):449.  doi:10.3390/E25030449.
  * 16. Barbosa LS, Marshall W, Albantakis L, Tononi G.  Mechanism Integrated Information.  Entropy 2021, Vol 23, Page 362. 2021;23(3):362.  doi:10.3390/E23030362.
  * 17. Haun A, Tononi G.  Why Does Space Feel the Way it Does? Towards a Principled Account of Spatial Experience.  Entropy 2019, Vol 21, Page 1160. 2019;21(12):1160.  doi:10.3390/E21121160.
  * 18. Barbosa LS, Marshall W, Streipert S, Albantakis L, Tononi G.  A measure for intrinsic information.  Scientific Reports 2020 10:1. 2020;10(1):1–9.  doi:10.1038/s41598-020-75943-4.
  * 19. Mayner WGP, Marshall W, Albantakis L, Findlay G, Marchman R, Tononi G.  PyPhi: A toolbox for integrated information theory.  PLOS Computational Biology. 2018;14(7):e1006343.  doi:10.1371/JOURNAL.PCBI.1006343.
  * 20. Niizato T, Sakamoto K, Mototake Yi, Murakami H, Tomaru T, Hoshika T, et al.  Finding continuity and discontinuity in fish schools via integrated information theory.  PLOS ONE. 2020;15(2):e0229573.  doi:10.1371/JOURNAL.PONE.0229573.
  * 21. Oizumi M, Tsuchiya N, Amari SI.  Unified framework for information integration based on information geometry.  Proceedings of the National Academy of Sciences of the United States of America. 2016;113(51):14817–14822.  doi:10.1073/PNAS.1603583113/-/DCSUPPLEMENTAL.
  * 22. Kanwal MS, Grochow JA, Ay N.  Comparing Information-Theoretic Measures of Complexity in Boltzmann Machines.  Entropy 2017, Vol 19, Page 310. 2017;19(7):310.  doi:10.3390/E19070310.
  * 23. Nilsen AS, Juel BE, Marshall W.  Evaluating Approximations and Heuristic Measures of Integrated Information.  Entropy 2019, Vol 21, Page 525. 2019;21(5):525.  doi:10.3390/E21050525.
  * 24. Albantakis L, Marshall W, Hoel E, Tononi G.  What Caused What? A Quantitative Account of Actual Causation Using Dynamical Causal Networks.  Entropy 2019, Vol 21, Page 459. 2019;21(5):459.  doi:10.3390/E21050459.

##  Appendix A Integrated cause information

In Section 2, we discussed the definition and the upper bounds of the
distinction integrated information. For simplicity, our discussion and
theoretical results were mostly focused on the integrated effect information.
Since $\varphi_{d}=\min\\{\varphi_{c},\varphi_{e}\\}\leq\varphi_{e}$, any
bound on $\varphi_{e}$ or $\sum\varphi_{e}$ is a bound for $\varphi_{d}$ or
$\sum\varphi_{d}$. Here, for completeness, we discuss the definition of
integrated cause information and show how the results obtained for the effect
side can be translated to the cause side.

The cause repertoire $\pi_{c}(Z_{t-1}\mid M=m)$ is defined as as the
probability distribution over a potential cause purview at time $t-1$,
$Z_{t-1}$, given a mechanism in state $m$ and can be calculated using Bayes’
rule:

$\pi_{c}(z\mid m)=\frac{\pi_{e}(m\mid z)\pi_{c}(z)}{\pi_{e}(m;Z)},$

where $\pi_{e}(m;Z)$ is the unconstrained effect probability as defined in
Section 2 and $\pi_{c}(z)=|\Omega_{Z}|^{-1}$ is the unconstrained cause
probability. The time subscripts are dropped to avoid cluttering the notation.
Similar to the effect side, the maximal cause state of the mechanism $m$ over
a potential cause purview $Z$ can be found as:

$z^{\prime}_{c}(m,Z)=\arg\max_{z\in\Omega_{Z}}\pi_{c}(z\mid
m)\log_{2}\left(\frac{\pi_{e}(m\mid z)}{\pi_{e}(m;Z)}\right).$

Since there is at least one state with $\pi_{e}(m\mid z)\geq\pi_{e}(m;Z)$, the
maximal cause state is always a state for which the cause $z$ increases the
probability of the mechanism $m$ compared to its unconstrained probability.
Finally, the integrated cause information is calculated as:

$\varphi_{c}(m,Z)=\pi_{c}(z^{\prime}_{c}\mid
m)\left|\,{\log_{2}\left(\frac{\pi_{e}(m\mid
z^{\prime}_{c})}{\pi_{e}^{\theta^{\prime}}(m\mid
z^{\prime}_{c})}\right)}\,\right|_{+},$ (18)

where $\theta^{\prime}$ is the minimum information partition (MIP), the
partition that achieves the minimum normalized integrated cause information.
We can also find the most irreducible cause purview of a mechanism as:

$z_{c}^{*}(m)=\arg\max_{\\{z^{\prime}_{c}|Z\subseteq
S\\}}\varphi_{c}(m,Z=z^{\prime}_{c}).$

These steps are similar to the steps described for the effect side in Section
2. The only difference is the definition of the repertoires and the use of a
slightly different distance measure. The measure being used for the cause side
has the form $\small\pi_{c}(z\mid m)\left|\,{\log_{2}\left(\frac{\pi_{e}(m\mid
z)}{\pi_{e}^{\prime}(m\mid z)}\right)}\,\right|_{+}$, where the selectivity
uses the backward probability and the informativeness uses the forward
probability. This measure satisfies the following properties:  (i) The measure
differs from $0$ only if the cause state increases the probability of the
mechanism state.  (ii) The measure is not an aggregate over all the states and
reflects how much change is made in an individual state.  (iii) In a scenario
where adding more units to the cause purview does not increase the probability
of the mechanism state further, having the new units in the maximally
irreducible purview is discouraged.

More importantly, since the informativeness term is the same for both
$\varphi_{e}$ and $\varphi_{c}$, all the results described for $\varphi_{e}$
hold for $\varphi_{c}$ as well. For example, the normalization factor derived
in Lemma 2 holds for both the cause and effect information, as it is a bound
on the infromativeness term. Similarly, since the proofs for Theorem 2 and
Theorem 3 only use the informativeness term to derive a bound for the
integrated effect information, they both hold for the integrated cause
information.

##  Appendix B Using other difference measures

As discussed in Section 2 and S1 Appendix., the difference measure to quantify
$\varphi_{e}$ and $\varphi_{c}$ satisfy certain properties. In this section,
we study how our results might change if we change the difference measure to
satisfy slightly different properties.

###  B.1 Absolute informativeness

Due to using the positive part operator $|.|_{+}$ in the informativeness,
integrated information is non-zero only if the state at $t-1$ increases the
probability of the state at $t$. This matches our intuition that a cause
should increase the probability of its effect. However, we can show even if we
use the absolute value operator in the difference measure, our results would
stay the same, by showing that the upper bound for the negative case is
smaller than the upper bound for the positive case. Lemma 5 states the upper
bound for the case where the mechanism _decreases_ the probability.

######  Lemma 5 (Maximum for negative cause/effect).

For $0\leq p,q\leq 1$, if $p\leq q$ then

$p\left|\,{\log_{2}(\frac{p}{q})}\,\right|\leq
q\frac{\log_{2}(e)}{e}\leq\frac{\log_{2}(e)}{e}\approx 0.531.$

###### Proof.

For $0\leq p\leq q\leq 1$, we have
$p\left|\,{\log_{2}(\frac{p}{q})}\,\right|=-p\log_{2}(\frac{p}{q})$ and

$\displaystyle\frac{d(-p\log_{2}(\frac{p}{q}))}{dp}$
$\displaystyle=\frac{-\ln(\frac{p}{q})-1}{\ln(2)}.$
$\displaystyle\frac{d^{2}(-p\log_{2}(\frac{p}{q}))}{dp^{2}}$
$\displaystyle=-\frac{1}{\ln(2)p}<0.$

Therefore, $p\left|\,{\log_{2}(\frac{p}{q})}\,\right|$ is concave for $0\leq
p\leq q\leq 1$. The maximum is obtained by setting the first derivative to
$0$:

$\displaystyle\frac{d(-p\log_{2}(\frac{p}{q}))}{dp}$
$\displaystyle=\frac{-\ln(\frac{p}{q})-1}{\ln(2)}=0$ $\displaystyle
p=\frac{q}{e}$

For $p=\frac{q}{e}$, we have
$p\left|\,{\log_{2}(\frac{p}{q})}\,\right|=\frac{q}{e}\log_{2}(e)\leq\frac{\log_{2}(e)}{e}$.
Thus for any $p\leq q$,
$p\left|\,{\log_{2}(\frac{p}{q})}\,\right|\leq\frac{\log_{2}(e)}{e}$. ∎

In other words, achieving integrated information of larger than
$\frac{\log_{2}(e)}{e}\approx 0.531$ is not possible by decreasing the
probability. Therefore, the mechanism needs to increase the probability to
achieve large values of integrated information. All the bounds discussed in
Section 2 are larger than this value, therefore changing $|.|_{+}$ to $|.|$
does not change our results.

###  B.2 Point-wise mutual information

Another candidate for the distance measure is the point-wise mutual
information, _i.e.,_ $\left|\,{\log(\frac{p}{q})}\,\right|_{+}$. Similar to
the measure used in the definition of the integrated information, this measure
is not an aggregate over the states and quantifies the change in an individual
state. Furthermore, it differs from $0$ only if $p>q$. This measure has been
used previously to quantify actual causation is discrete systems [24]. Using
this measure does not change our results because the bounds derived in Section
2 were all derived for the informativeness term of difference measure, which
has the form $\left|\,{\log(\frac{p}{q})}\,\right|_{+}$.

###  B.3 Kullback–Leibler divergence

Kullback–Leibler divergence (KLD) measure is another common distance measure
for probability distribution and is defined as
$D_{KL}(p(X)||q(X))=\sum_{x\in\Omega_{X}}p(X=x)\log(\frac{p(X=x)}{q(X=x)})$.
It is $0$, only if $p(X=x)=q(X=x),\forall x\in\Omega_{X}$, and is an aggregate
measure over all the states, unlike our default measure.

Here, we study the upper bound for $D_{KL}(\pi_{e}(Z\mid
m)||\pi_{e}^{\theta}(Z\mid m))$ and show that the results in Section 2 are
still relevant even if we use KLD. First, using the definition of the effect
repertoire and additivity of KLD, we have:

$D_{KL}(\pi_{e}(Z\mid m)||\pi_{e}^{\theta}(Z\mid m))=D_{KL}(\prod_{Z_{i}\in
Z}\pi_{e}(Z_{i}\mid m)||\prod_{Z_{i}\in Z}\pi_{e}^{\theta}(Z_{i}\mid
m))=\sum_{Z_{i}\in Z}D_{KL}(\pi_{e}(Z_{i}\mid m)||\pi_{e}^{\theta}(Z_{i}\mid
m)).$ (19)

Let us define the mechanism connected to $Z_{i}$ after the partitioning as
$M_{i}$. For each individual binary unit in the purview $Z_{i}$, we can use
the proof in lemma 1 to show that:

$\displaystyle\frac{\pi_{e}(Z_{i}=z_{i}\mid m)}{\pi_{e}(Z_{i}=z_{i}\mid
m_{i})}\leq 2^{|M|-|M_{i}|}.$

Therefore, finding the maximum value for an individual binary unit boils down
to solving the following problem:

$\displaystyle\max_{p,q}$ $\displaystyle
D_{KL}(p||q)=p\log(\frac{p}{q})+(1-p)\log(\frac{1-p}{1-q})$ subject to
$\displaystyle p\leq 2^{|M|-|M_{i}|}q$ $\displaystyle q\leq p\leq 1.$

The constraint $q\leq p$ is added without loss of generality, as it always
holds for one of the two states. We are denoting the probabilities of that
state with $p$ and $q$. Under this constraint the derivative of the objective
function with respect to $p$ is always non-negative:

$\frac{\partial D_{KL}(p||q)}{\partial
p}=\log\left(\frac{p}{q}\right)-\log\left(\frac{1-p}{1-q}\right)=\log\left(\frac{\frac{1}{q}-1}{\frac{1}{p}-1}\right)\geq
0$

This means the maximum of $D_{KL}(p||q)$ occurs at the boundary for which $p$
is the largest, which is $p=\min\\{1,2^{|M|-|M_{i}|}q\\}$. In other words,
$p=2^{|M|-|M_{i}|}q$ for $q\leq\frac{1}{2}^{|M|-|M_{i}|}$ and $p=1$,
otherwise. For the latter case, we have $D_{KL}(p||q)=\log(\frac{1}{q})$,
whose maximum occurs when $q$ is minimized, _i.e.,_
$q=\frac{1}{2}^{|M|-|M_{i}|}$, with the maximal KLD value of $|M|-|M_{i}|$.
The maximum for the former case also happens at the same point, since the
derivative of the objective function with respect to $q$ is non-negative:

$\frac{\partial}{\partial
q}\left(2^{|M|-|M_{i}|}q(|M|-|M_{i}|)+(1-2^{|M|-|M_{i}|}q)\log(\frac{1-2^{|M|-|M_{i}|}q}{1-q})\right)\geq
0,$

and we need to maximize $q$ in order to maximize $D_{KL}(p||q)$. This again
leads to the maximum value of $|M|-|M_{i}|$ at $q=\frac{1}{2}^{|M|-|M_{i}|}$.
Thus, we have:

$D_{KL}(\pi_{e}(Z_{i}\mid m)||\pi_{e}(Z_{i}\mid m_{i}))\leq|M|-|M_{i}|,$

which is the same bound as Lemma 1, but for KLD instead of our default
distance measure. $|M|-|M_{i}|$ is the number of connection severed form
$Z_{i}$. We can plug this result into (19) and arrive at:

$D_{KL}(\pi_{e}(Z\mid m)||\pi_{e}^{\theta}(Z\mid m))=\sum_{Z_{i}\in
Z}D_{KL}(\pi_{e}(Z_{i}\mid m)||\pi_{e}^{\theta}(Z_{i}\mid
m))\leq\sum_{Z_{i}\in Z}(|M|-|M_{i}|)=\mathcal{N}(\theta).$

$\mathcal{N}(\theta)$ is the number of connections severed by the partition
$\theta$. This is the same result as Lemma 2 and shows that even if we use KLD
as the distance measure, the normalization factor for finding the MIP would
not change. This can also be used to show that if we use KLD to quantify
$\varphi_{e}$, it cannot be larger than the number of connections between the
mechanism and the purview, _i.e.,_ $\varphi_{e}(m,E)\leq|M||E|$ (same results
as Theorem 1).

Furthermore, since KLD is maximized when $\pi_{e}(Z\mid m)$ is fully
deterministic, Lemma 4 and Theorem 2 hold. Finally, the assumption for Theorem
3 is that the effect repertoire is fully deterministic, _i.e.,_
$\pi_{e}(Z=z\mid m)=1$ for some $z\in\Omega_{Z}$. In this case, KLD is
simplified to $\log(\frac{1}{\pi_{e}^{\theta}(Z=z\mid m)})=\pi_{e}(Z=z\mid
m)\left|\,{\log(\frac{\pi_{e}(Z=z\mid m)}{\pi_{e}^{\theta}(Z=z\mid
m)})}\,\right|_{+}$, which coincides with our default distance measure.
Therefore, Theorem 3 holds as well.

##  Appendix C Proofs

###  C.1 Single mechanism

Before presenting our main proofs, let us revisit the definition of single-
unit effect repertoire. Given the set of units outside the mechanism $W=S-M$
and a single unit $Z_{i}$ in state $z_{i}$:

$\pi_{e}(Z_{i}=z_{i}\mid m)=\frac{1}{2^{|W|}}\sum_{w}p(Z_{i}=z_{i}\mid
m,w)=\frac{1}{|\mathcal{M}(m)|}\sum_{s\in\mathcal{M}(m)}p(Z_{i}=z_{i}\mid s),$

where $\mathcal{M}(m)\subset\Omega_{S}$ is the set of system states in which
mechanism $M$ is in state $m$ and we have
$|\mathcal{M}(m)|=2^{|W|}=2^{N-|M|}$. $\Omega_{S}$ is the set of all possible
states of the system $S$. Defining $\mathcal{M}(m)$ helps us to present our
results in a more concise manner. For example, we will use the following
simple lemma to prove Lemma 1

######  Lemma 6.

For two mechanisms $M$ and $\bar{M}$ such that $\bar{M}\subset M\subseteq S$,
we have $\mathcal{M}(m)\subset\mathcal{M}(\bar{m})$.

###### Proof.

Without loss of generality let us assume $M$ is in all-zero state. By
definition, $\forall s\in\mathcal{M}(m)$ the units corresponding to $M$ are in
all-zero state. Since $\bar{M}\subset M$, $\forall s\in\mathcal{M}(m)$ the
units corresponding to $\bar{M}$ are also in all-zero state and therefore
$s\in\mathcal{M}(\bar{m})$. Thus, $\forall s\in\mathcal{M}(m)$, we have
$s\in\mathcal{M}(\bar{m})$, which means
$\mathcal{M}(m)\subset\mathcal{M}(\bar{m})$. ∎

######  Example 1.

$\bar{M}=A$ and $M=AB$ for system $S=ABC$ in all-zero state.
$\mathcal{M}(\bar{m})=\\{ABC=000,ABC=001,ABC=010,ABC=011\\}$ and
$\mathcal{M}(m)=\\{ABC=000,ABC=001\\}$.

See 1

###### Proof.

For a single purview unit $Z_{i}\in Z$ we have:

$\displaystyle\frac{\pi_{e}(Z_{i}=z_{i}\mid
m)}{\pi_{e}(Z_{i}=z_{i}\mid\bar{m})}=\frac{\frac{1}{|\mathcal{M}(m)|}\sum_{s\in\mathcal{M}(m)}p(Z_{i}=z_{i}\mid
s)}{\frac{1}{|\mathcal{M}(\bar{m})|}\sum_{s\in\mathcal{M}(\bar{m})}p(Z_{i}=z_{i}\mid
s)}$

Since $\bar{M}\subset M$, we have $\mathcal{M}(m)\subset\mathcal{M}(\bar{m})$
(using Lemma 6), therefore $\sum_{s\in\mathcal{M}(m)}p(Z_{i}=z_{i}\mid
s)\leq\sum_{s\in\mathcal{M}(\bar{m})}p(Z_{i}=z_{i}\mid s)$. This is because we
are taking the sum over more terms on the right side. Thus

$\displaystyle\frac{\pi_{e}(Z_{i}=z_{i}\mid
m)}{\pi_{e}(Z_{i}=z_{i}\mid\bar{m})}\leq\frac{\frac{1}{|\mathcal{M}(m)|}}{\frac{1}{|\mathcal{M}(\bar{m})|}}=\frac{\frac{1}{2^{N-|M|}}}{\frac{1}{2^{N-|\bar{M}|}}}=2^{|M|-|\bar{M}|}.$

∎

See 2

###### Proof.

Due to the conditional independence of the purview units, we have:

$\log_{2}(\frac{\pi_{e}(Z=z\mid m)}{\pi_{e}^{\theta}(Z=z\mid
m)})=\log_{2}(\frac{\prod_{i}\pi_{e}(Z_{i}=z_{i}\mid
m)}{\prod_{i}\pi_{e}^{\theta}(Z_{i}=z_{i}\mid m)})=\sum_{Z_{i}\in
Z}\log_{2}(\frac{\pi_{e}(Z_{i}=z_{i}\mid m)}{\pi_{e}^{\theta}(Z_{i}=z_{i}\mid
m)})$

Let us define $M_{i}$ as the mechanism connected to $Z_{i}$ after the
partitioning. Using Lemma 1:

$\sum_{Z_{i}\in Z}\log_{2}(\frac{\pi_{e}(Z_{i}=z_{i}\mid
m)}{\pi_{e}^{\theta}(Z_{i}=z_{i}\mid m)})\leq\sum_{Z_{i}\in
Z}(|M|-|M_{i}|)=\mathcal{N}(\theta).$

$\mathcal{N}(\theta)=\sum_{Z_{i}\in Z}(|M|-|M_{i}|)$ is the total number of
connections cut by partition $\theta$. ∎

See 1

###### Proof.

For the effect side, we have:

$\displaystyle\varphi_{e}(m,E)$ $\displaystyle=\pi_{e}(E=e\mid
m)\left|\,{\log_{2}(\frac{\pi_{e}(E=e\mid
m)}{\pi_{e}^{\theta^{\prime}}(E=e\mid
m)})}\,\right|_{+}\leq\left|\,{\log_{2}(\frac{\pi_{e}(E=e\mid
m)}{\pi_{e}^{\theta^{\prime}}(E=e\mid m)})}\,\right|_{+}$
$\displaystyle\leq\max_{\theta}\left|\,{\log_{2}(\frac{\pi_{e}(E=e\mid
m)}{\pi_{e}^{\theta}(E=e\mid
m)})}\,\right|_{+}\overset{(a)}{\leq}\max_{\theta}\mathcal{N}(\theta)\leq|M||E|$

$\theta^{\prime}$ represents the MIP and equality (a) follows from Lemma 2.
Similarly for the cause side, we have:

$\displaystyle\varphi_{c}(m,C)$ $\displaystyle=\pi_{c}(C=c\mid
m)\left|\,{\log_{2}(\frac{\pi_{e}(M=m\mid
c)}{\pi_{e}^{\theta^{\prime}}(M=m\mid
c)})}\,\right|_{+}\leq\left|\,{\log_{2}(\frac{\pi_{e}(M=m\mid
c)}{\pi_{e}^{\theta^{\prime}}(M=m\mid c)})}\,\right|_{+}$
$\displaystyle\leq\max_{\theta}\left|\,{\log_{2}(\frac{\pi_{e}(M=m\mid
c)}{\pi_{e}^{\theta}(M=m\mid
c)})}\,\right|_{+}\leq\max_{\theta}\mathcal{N}(\theta)\leq|M||C|$

∎

See 4

###### Proof.

In deriving the upper bounds in Theorem 1, the upper bound is achieved by
setting $\pi_{e}(E=e\mid m)$ and $\pi_{c}(C=c\mid m)$ to $1$. Using the same
line of proof and setting $\pi_{e}(E=e\mid m)<1$ and $\pi_{c}(C=c\mid m)<1$,
we will achieve $\varphi_{e}(m,E)<|M||E|$ and $\varphi_{c}(m,C)<|M||C|$. Thus,
to achieve $\varphi_{e}(m,E)=|M||E|$ ($\varphi_{c}(m,C)=|M||C|$), we need to
have $\pi_{e}(E=e\mid m)=1$ ($\pi_{c}(C=c\mid m)=1$). ∎

###  C.2 Inter-order constraints

To prove Theroem 2, we first need to prove a few intermediate lemmas.

######  Lemma 7 (Deterministic mechanism).

For a mechanism $M\subseteq S$ and a single-unit purview $Z_{i}$, if
$\pi_{e}(Z_{i}=z_{i}\mid m)=1$, then $p(Z_{i}=z_{i}\mid s)=1,\forall
s\in\mathcal{M}(m)$. Furthermore, if $\pi_{e}(Z_{i}=z_{i}\mid m)=0$, then
$p(Z_{i}=z_{i}\mid s)=0,\forall s\in\mathcal{M}(m)$.

###### Proof.

For $\pi_{e}(Z_{i}=z_{i}\mid m)=1$:

$\pi_{e}(Z_{i}=z_{i}\mid
m)=\frac{1}{|\mathcal{M}(m)|}\sum_{s\in\mathcal{M}(m)}p(Z_{i}=z_{i}\mid s)=1.$

Therefore, $\sum_{s\in\mathcal{M}(m)}p(Z_{i}=z_{i}\mid s)=|\mathcal{M}(m)|$.
Since $p(Z_{i}=z_{i}\mid s)\leq 1,\forall s$, all the terms in the summation
need to be $1$, _i.e.,_ $p(Z_{i}=z_{i}\mid s)=1,\forall s\in\mathcal{M}(m)$.

For $\pi_{e}(Z_{i}=z_{i}\mid m)=0$,
$\sum_{s\in\mathcal{M}(m)}p(Z_{i}=z_{i}\mid s)=0$. Since $p(Z_{i}=z_{i}\mid
s)\geq 0,\forall s$, all the terms in the summation need to be $0$, _i.e.,_
$p(Z_{i}=z_{i}\mid s)=0,\forall s\in\mathcal{M}(m)$. ∎

See 3

###### Proof.

If $\pi_{e}(Z_{i}=z_{i}\mid m)=1$:

According to Lemma 7, $p(Z_{i}=z_{i}\mid s)=1,\forall s\in\mathcal{M}(m)$.
Since $M\subset\bar{M}$, we have $\mathcal{M}(\bar{m})\subset\mathcal{M}(m)$
(Lemma 6). Therefore, $p(Z_{i}=z_{i}\mid s)=1,\forall
s\in\mathcal{M}(\bar{m})$ and
$\pi_{e}(Z_{i}=z_{i}\mid\bar{m})=\frac{1}{|\mathcal{M}(\bar{m})|}\sum_{s\in\mathcal{M}(\bar{m})}p(Z_{i}=z_{i}\mid
s)=1$.

Similarly, for $\pi_{e}(Z_{i}=z_{i}\mid m)=0$:

According to Lemma 7, $p(Z_{i}=z_{i}\mid s)=0,\forall s\in\mathcal{M}(m)$.
Since $M\subset\bar{M}$, we have $\mathcal{M}(\bar{m})\subset\mathcal{M}(m)$
(Lemma 6). Therefore, $p(Z_{i}=z_{i}\mid s)=0,\forall
s\in\mathcal{M}(\bar{m})$ and
$\pi_{e}(Z_{i}=z_{i}\mid\bar{m})=\frac{1}{|\mathcal{M}(\bar{m})|}\sum_{s\in\mathcal{M}(\bar{m})}p(Z_{i}=z_{i}\mid
s)=0$. ∎

######  Lemma 8.

If $\varphi_{e}(m,Z)=|M||Z|$ then
$\varphi_{e}(\bar{m},\bar{Z})<|\bar{M}||\bar{Z}|,$ if $M\subset\bar{M}$ and
$Z\cap\bar{Z}\neq\varnothing$.

###### Proof.

Since $\varphi_{e}(m,Z)=|M||Z|$, using Lemma 4:

$\displaystyle\pi_{e}(Z=z^{*}\mid m)=\prod_{Z_{i}\in
Z}\pi_{e}(Z_{i}=z_{i}^{*}\mid m)=1$ $\displaystyle\implies$
$\displaystyle\pi_{e}(Z_{i}=z_{i}^{*}\mid m)=1,\forall Z_{i}\in Z$
$\displaystyle\overset{(a)}{\implies}$ $\displaystyle p(Z_{i}=z_{i}\mid
s)=1,\forall s\in\mathcal{M}(m),\forall Z_{i}\in Z$ $\displaystyle\implies$
$\displaystyle\pi_{e}(Z_{i}=z_{i}^{*})=\frac{1}{|\Omega_{S}|}\sum_{s\in\Omega_{S}}p(Z_{i}=z_{i}\mid
s)\geq\frac{|\mathcal{M}(m)|}{|\Omega_{S}|}=\frac{2^{N-|M|}}{2^{N}}=\frac{1}{2^{|M|}},\forall
Z_{i}\in Z,$

From Theorem 1, we already know
$\varphi_{e}(\bar{m},\bar{Z})\leq|\bar{M}||\bar{Z}|$ and from Lemma 2, we know
the only partitioning that can achieve $|\bar{M}||\bar{Z}|$ is the complete
partition, _i.e.,_ removing all the connections between $\bar{M}$ and
$\bar{Z}$. Now, we show even the complete partition cannot achieve
$|\bar{M}||\bar{Z}|$. Under the complete partition,
$\theta=\\{(\varnothing,\bar{M}),(\bar{Z},\varnothing)\\}$, we have:

$\displaystyle\varphi_{e}(\bar{m},\bar{Z},\theta)$
$\displaystyle=\pi_{e}(\bar{Z}=\bar{z}\mid\bar{m})\left|\,{\log_{2}(\frac{\pi_{e}(\bar{Z}=\bar{z}\mid\bar{m})}{\pi_{e}(\bar{Z}=\bar{z})})}\,\right|_{+}\leq\left|\,{\log_{2}(\frac{\pi_{e}(\bar{Z}=\bar{z}\mid\bar{m})}{\pi_{e}(\bar{Z}=\bar{z})})}\,\right|_{+}$
$\displaystyle=\left|\,{\sum_{Z_{i}\in\bar{Z}}\log_{2}(\frac{\pi_{e}(\bar{Z}_{i}=\bar{z}_{i}\mid\bar{m})}{\pi_{e}(\bar{Z}_{i}=\bar{z}_{i})})}\,\right|_{+}\leq\left|\,{\sum_{Z_{i}\in\bar{Z}\cap
Z}\log_{2}(\frac{\pi_{e}(\bar{Z}_{i}=\bar{z}_{i}\mid\bar{m})}{\pi_{e}(\bar{Z}_{i}=\bar{z}_{i})})}\,\right|_{+}+\left|\,{\sum_{Z_{i}\in\bar{Z}-Z}\log_{2}(\frac{\pi_{e}(\bar{Z}_{i}=\bar{z}_{i}\mid\bar{m})}{\pi_{e}(\bar{Z}_{i}=\bar{z}_{i})})}\,\right|_{+}$
$\displaystyle\overset{(a)}{\leq}|\bar{Z}\cap
Z||M|+|\bar{Z}-Z||\bar{M}|<|\bar{Z}\cap
Z||\bar{M}|+|\bar{Z}-Z||\bar{M}|=|\bar{Z}||\bar{M}|$

The first term in (a) follows from the fact that
$\pi_{e}(Z_{i}=z_{i}^{*})\geq\frac{1}{2^{|M|}},\forall Z_{i}\in Z$, as we
proved earlier, and the second term follows from Lemma 1. ∎

######  Lemma 9.

$\varphi_{e}(\bar{m},\bar{Z})<|\bar{M}||\bar{Z}|,$ if
$\varphi_{e}(m,Z)=|M||Z|$ and $\bar{M}\subset M$ and
$Z\cap\bar{Z}\neq\varnothing$.

###### Proof.

Proof by contradiction: Assume $\varphi(\bar{m},\bar{Z})=|\bar{M}||\bar{Z}|$.
Then according to Lemma 8, $\varphi(m,Z)<|M||Z|$. Contradiction. ∎

See 2

###### Proof.

Follows directly from Lemma 9 and Lemma 8. ∎

###  C.3 Intra-order constraints

In this section, we study a system consisting of $N$ units in which all the
mechanisms of size $K$ specify themselves with probability $1$:

$\pi_{e}(Z=z^{\prime}\mid m)=1,\forall M:|M|=K,Z=M.$

First, we show how we can construct a TPM that can satisfy this property.
Then, we show why such mechanisms cannot achieve their maximal value. Finally,
we show, for such mechanism, MIP can only be one of a few candidate
partitions.

Let us denote $M_{n,j}$ and $Z_{n,j}$, $j=1,\dots,\binom{N-1}{K-1}$ and
$n=1,\dots,N$ as the set of mechanisms and purviews of size $K$ that contain
$n^{\text{th}}$ unit, respectively. From the assumptions of the theorem we
also have $Z_{n,j}=M_{n,j},|Z_{n,j}|=|M_{n,j}|=K,\forall j,n$. Furthermore,
$Z_{n}$ denotes the single-unit purview only containing the $n^{\text{th}}$
unit. Starting from the assumption of the theorem, we have:

$\displaystyle\pi_{e}(Z_{n,j}=z_{n,j}^{*}\mid m_{n,j})$
$\displaystyle=1,\forall n,j\implies\pi_{e}(Z_{n}=z_{n}^{*}\mid m_{n,j})$
$\displaystyle=1,\forall n,j$

This expression means the probability of the $n^{\text{th}}$ purview unit,
given all the mechanisms of size $K$ that contain the $n^{\text{th}}$ unit is
$1$. Using Lemma 7:

$p(Z_{n}=z_{n}^{*}\mid s)=1,\forall
s\in\mathcal{M}(m_{n,j}),n=1,\dots,N,\forall j$

Note that in general $z_{n}^{*}$, which is the maximal state the purview unit,
depends on the mechanism $M_{n,j}$. But the above constraint is only
satisfiable when $z_{n}^{*}$ is the same for all $j$. To see that, first
notice that
$\mathcal{M}(m_{n,j})\cap\mathcal{M}(m_{n,j^{\prime}})\neq\varnothing,\forall
j,j^{\prime}$ and for
$s\in\mathcal{M}(m_{n,j})\cap\mathcal{M}(m_{n,j^{\prime}})$, either we have
$p(Z_{n}=0\mid s)=1$ or $p(Z_{n}=1\mid s)=1$. Therefore, $M_{n,j}$ and
$M_{n,j^{\prime}}$ should agree on the state of $Z_{n}$. This is true for any
pair $j,j^{\prime}$. Without loss of generality, we assume $z_{n}^{*}$ is $0$
for all $n$ and $j$.

$p(Z_{n}=0\mid s)=1,\forall s\in\bigcup_{j}\mathcal{M}(m_{n,j}),n=1,\dots,N.$
(20)

Furthermore, without loss of generality, let us assume that the system is also
in all-zero state at the current time. Thus, $\mathcal{M}(m_{n,j})$ is the set
of system states in which the state of the units in $M_{n,j}$ (unit $n$ and
$K-1$ other units) are $0$ and $\bigcup_{j}\mathcal{M}(m_{n,j})$ is the set of
all the system states for which the state of the unit $n$ and at least $K-1$
other units are $0$.

So far, we have shown that, for any single purview unit $Z_{n}$, the TPM entry
for $p(Z_{n}=0\mid s)$ is $1$ for all system states $s$ that the unit $n$ and
at least $K-1$ other units are $0$. To study the partitioned repertoires, we
should also derive $\pi_{e}(Z_{n}=0\mid\bar{m})$ for different mechanisms
$\bar{m}\subset m_{n,j}$ with $|\bar{M}|<K$.

First, consider the case where $\bar{M}$ contains unit $n$ and $|\bar{M}|<K$:

$\pi_{e}(Z_{n}=0\mid\bar{m}=0)=\frac{1}{|\mathcal{M}(\bar{m})|}\sum_{s\in\mathcal{M}(\bar{m})}p(Z_{n}=0\mid
s),$

Let us denote this probability as $\pi(|\bar{M}|)$. $\mathcal{M}(\bar{m})$ is
the set of system states for which unit $n$ and $|\bar{M}|-1$ other units are
$0$ and we are marginalizing over the state of the rest of $N-|\bar{M}|$
units. But as we discussed earlier, we know any state with unit $n$ and at
least $K-1$ other units in state $0$ has $p(Z_{n}=0\mid s)=1$. So out of the
$2^{N-|\bar{M}|}$ states in $\mathcal{M}(\bar{m})$, there are at least
$\sum_{b=K-|\bar{M}|}^{N-|\bar{M}|}\binom{N-|\bar{M}|}{b}$ states with
probability $1$. Therefore:

$\pi(|\bar{M}|)\geq\frac{\sum_{b=K-|\bar{M}|}^{N-|\bar{M}|}\binom{N-|\bar{M}|}{b}}{2^{N-|\bar{M}|}}.$

Similarly, we can define the probability $\pi_{e}(Z_{n}=0\mid\bar{m}=0)$ for
the case where $\bar{M}$ does not contain unit $n$ and $|\bar{M}|<K$ as
$\bar{\pi}(|\bar{M}|)$. In this case, $\mathcal{M}(\bar{m})$ is the set of
system states for which $|\bar{M}|$ units are $0$ and we are marginalizing
over the state of the rest of $N-|\bar{M}|$ units. Again, any state in
$\mathcal{M}(\bar{m})$ with unit $n$ and $K-|\bar{M}|-1$ other units in state
$0$ has probability of $1$. Therefore:

$\bar{\pi}(|\bar{M}|)\geq\frac{\sum_{b=K-|\bar{M}|-1}^{N-|\bar{M}|-1}\binom{N-|\bar{M}|-1}{b}}{2^{N-|\bar{M}|}}=\frac{\sum_{b=K-|\bar{M}|}^{N-|\bar{M}|}\binom{N-|\bar{M}|-1}{b-1}}{2^{N-|\bar{M}|}}.$

To find the MIP, we need to find the minimum normalized difference between
partitioned and unpartitioned repertoires for the pair $Z$ and $M$:

$\frac{1}{\mathcal{N}(\theta)}\pi_{e}(Z=z\mid
m)\left|\,{\log_{2}(\frac{\pi_{e}(Z=z\mid m)}{\pi_{e}^{\theta}(Z=z\mid
m)})}\,\right|_{+}=\frac{1}{\mathcal{N}(\theta)}\log_{2}(\frac{1}{\prod_{i}\pi_{e}^{\theta}(Z_{i}=z_{i}\mid
m)})=-\frac{1}{\mathcal{N}(\theta)}\sum_{Z_{i}\in
Z}\log_{2}(\pi_{e}(Z_{i}=z_{i}\mid m_{i}))$ (21)

$m_{i}$ is the mechanism connected to $Z_{i}$ after the partition and
$\pi_{e}^{\theta}(Z_{i}=z_{i}\mid m_{i})$ is either $\pi(|M_{i}|)$ and
$\bar{\pi}(|M_{i}|))$. The lower bounds for both $\pi(|\bar{M}|)$ and
$\bar{\pi}(|\bar{M}|))$, therefore the upper bound for the sum, are achieved
when:

$p(Z_{n}=0\mid s)=0,\forall
s\notin\bigcup_{j}\mathcal{M}(m_{n,j}),n=1,\dots,N.$ (22)

Eq (20) and Eq (22) provide us with $p(Z_{n}=0\mid s)$ for all system states
$s$ and purview units $n$, which gives us the full TPM.

We can even further decompose the sum in Eq (21) into sum over individual
connections. Assume we are removing connections from the mechanism $m$ to the
purview unit $z_{i}$ one by one until we arrive at the mechanism after the
partitioning $m_{i}$. Let us denote the intermediate steps as
$m_{i}^{(0)},m_{i}^{(1)},m_{i}^{(2)},\dots,m_{i}^{(N_{i})}$, where
$m_{i}^{(0)}=m$ and $m_{i}^{(N_{i})}=m_{i}$ and $N_{i}$ is the number of
connections cut from $z_{i}$. We can write the normalized partitioned
informativeness as:

$\small\frac{1}{\mathcal{N}(\theta)}\left|\,{\sum_{Z_{i}\in
Z}\sum_{c=1}^{N_{i}}\log_{2}(\frac{\pi_{e}(Z=z\mid
m_{i}^{(c-1)})}{\pi_{e}(Z=z\mid
m_{i}^{(c)})})}\,\right|_{+}=\frac{1}{\mathcal{N}(\theta)}\sum_{Z_{i}\in
Z}\sum_{c=1}^{N_{i}}\log_{2}(\frac{\pi_{e}(Z=z\mid
m_{i}^{(c-1)})}{\pi_{e}(Z=z\mid m_{i}^{(c)})})$ (23)

Positive part operator can be removed as both $\pi(|\bar{M}|)$ and
$\bar{\pi}(|\bar{M}|))$ decrease as the size of the mechanism $|\bar{M}|$
increases, making all the terms inside the sum positive. Eq (23) rewrites the
normalized partitioned informativeness as the average informativeness gain
over the individual connections severed by the partition.

From Lemma 1, we know the information gain per connection can at most be $1$.
Now, using $\pi(|\bar{M}|)$ and $\bar{\pi}(|\bar{M}|))$, we can make a few
observations about the information gain of removing different connections in
the system under consideration. First, we show cutting a self connection can
achieve the maximum information gain of $1$. This means removing the self
connection cannot decrease the normalized partitioned informativeness, as
adding $1$ to a set of numbers that can at most be $1$ cannot decrease the
average. To calculate the information gain for cutting a self connection, we
should compare $\pi(|M_{i}|)$ to $\bar{\pi}(|M_{i}|-1)$, _i.e.,_ cutting one
input connection from unit $Z_{i}$ such that the mechanism connected to it no
longer contains it:

$\displaystyle\pi(|M_{i}|))$
$\displaystyle=\frac{\sum_{b=K-|M_{i}|}^{N-|M_{i}|}\binom{N-|M_{i}|}{b}}{2^{N-|M_{i}|}}=\frac{2\sum_{b=K-|M_{i}|}^{N-|M_{i}|}\binom{N-|M_{i}|}{b}}{2^{N-|M_{i}|+1}}$
$\displaystyle=2\frac{\sum_{b=K-(|M_{i}|-1)-1}^{N-(|M_{i}|-1)-1}\binom{N-(|M_{i}|-1)-1}{b}}{2^{N-(|M_{i}|-1)}}=2\bar{\pi}(|M_{i}|-1)).$

This provides us with the proof for Theorem 3. See 3

###### Proof.

Achieving the maximum value is only possible if the MIP is the complete
partition. Since, as shown above, not having the self connections in the cut
for $1<K<N$ gives us a smaller normalized partitioned informativeness, the
complete partition cannot be the MIP. ∎

We can similarly calculate the informativeness gain for a lateral connection
as $\log_{2}(\frac{\pi(|\bar{M}|)}{\pi(|\bar{M}|-1)})$ or
$\log_{2}(\frac{\bar{\pi}(|\bar{M}|)}{\bar{\pi}(|\bar{M}|-1)})$, depending on
if the self connection is intact or not, respectively. In the first case we
have:

$\small\log_{2}(\frac{\pi(|\bar{M}|)}{\pi(|\bar{M}|-1)})=\log_{2}(2\frac{\sum_{b=K-|\bar{M}|}^{N-|\bar{M}|}\binom{N-|\bar{M}|}{b})}{\sum_{b=K-|\bar{M}|+1}^{N-|\bar{M}|+1}\binom{N-|\bar{M}|+1}{b}})=1+\log_{2}(\frac{\sum_{b=0}^{N-K}\binom{N-|\bar{M}|}{b})}{\sum_{b=0}^{N-K}\binom{N-|\bar{M}|+1}{b}})=1-\log_{2}(\frac{\sum_{b=0}^{N-K}\binom{N-|\bar{M}|+1}{b}}{\sum_{b=0}^{N-K}\binom{N-|\bar{M}|}{b})}).$

This shows the information gain of $1$ is only achievable for the special case
of $K=N$, which is the trivial case of no intra-order trade-off. Furthermore,
since the ratio inside $\log$ is decreasing with $N-|\bar{M}|$, the
information gain increases as we cut more lateral connections. Same results
hold for $\log_{2}(\frac{\bar{\pi}(|\bar{M}|)}{\bar{\pi}(|\bar{M}|-1)})$ as
well.

This helps us to narrow down the scope of our search for the MIP. Consider the
cut where one mechanism unit is removed from all the $K$ purview units. This
cut removes the minimum number of connections among all the valid cuts. It
removes $K$ connections, $1$ self connection and $K-1$ lateral connections.
Any other valid cut that removes at least one self connection can only
increase the average, compared to this cut. This is because, as shown above,
cutting more self connections can only increase the average, except the
special case of $K=N$, and cutting more lateral connections from a purview
unit also only increases the average. Therefore, the special cut discussed
above has smaller average information gain, compared to any other cut that
removes at least one self connection. This narrows our search to only this cut
and the cuts that do not remove self connections.

We can further show that among the partitions that do not cut self connections
bi-partitions have the smallest average information gain. To see this,
starting from any partition with more than two parts, merging the two smallest
parts decreases the average. This is because the purview units in the smallest
parts have the maximum number of connections removed from them. As already
shown, the information gain increases as we cut more lateral connections,
therefore by merging the smallest parts we can avoid removing the connections
with maximum information gain, which can only decrease the average. This
narrows the candidate partitions to $\frac{K}{2}+1$ partitions, _i.e.,_ linear
growth with size, and makes it computationally feasible to evaluate for bigger
networks.