{'fraction_non_alphanumeric': 0.04794998140572704, 'fraction_numerical': 0.012388434362216438, 'mean_word_length': 3.9959359033906177, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Strengthened Landauer bound for composite systems

Many systems can be decomposed into a set of subsystems, where the dynamics of each subsystem only depends on some of the other subsystems rather than on all of them. Here I derive an infinite set of lower bounds on the entropy production of any such composite system, in terms of the initial distribution of its states, the ending distribution, and the dependencies of the dynamics of its subsystems. In contrast to previous results, these new bounds hold for arbitrary dependencies among the subsystems, not only for the case where the subsystems evolve independently. Moreover, finding the strongest of these new lower bounds is a linear programming problem. As I illustrate, often this maximal lower bound is stronger than the conventional Landauer bound, since the conventional Landauer bound does not account for the dependency structure.


I. INTRODUCTION
Perhaps the most famous result in non-equilibrium statistical physics is the classical physics formulation of Landauer's bound [2,14]. In its fully modern, generalized form [6,9,20,25,29,31,36], it says that for any thermodynamically closed system which evolves from an initial distribution p 0 (x) to an ending distribution p t f (x), the amount of heat dissipated to the heat bath is at least as large as the associated drop in entropy of the system, S(p 0 ) − S(p t f ) (in units where k B T = 1). Stated differently, it says that the minimal integrated entropy production (EP) in the system as it evolves in any thermodynamically closed process is non-negative.
Some strengthened versions of Landauer's bound have been derived by substantially restricting the process under consideration, e.g., by simultaneously imposing limits on how long the process takes and on (integrals of) certain time-varying properties of the process dynamics [10,18,19,24,27]. In addition, a version of Landauer's bound has been derived that applies quite broadly, to any composite system that comprises two interacting subsystems [21]. However, this particular version of Landauer's bound was derived by redefining terms, so that Landauer's bound applied to the composite system results in an apparent violation of the bound for a subsystem. It does not strengthen Landauer's bound for the minimal EP generated by evolving the full, composite system.
More recently, some strengthened versions of Landauer's bound for the EP generated by full, composite systems have been derived [4,34,36]. However, these results only concern the special case where the subsystems in the composite system evolve independently of one another. This is a major restriction on the results. In a more general setting, while the dynamics of each subsystem only depends on the states of some of the other subsystems, the subsystems are not independent. As an illustration of such a dependency structure, consider a composite system with three subsystems A, B and C. B evolves independently of A and C. However, B is continually observed by C as well as A. Moreover, suppose that A is really two subsystems, 1 and 2. Only subsystem 2 directly observes B, whereas subsystem 1 observes subsystem 2, e.g., to record a running average of the values of subsystem 2 (see Fig. 1). These new, strengthened Landauer bounds do not apply to such scenarios.
Physically, such a scenario where the subsystems interact with one another arises whenever any of the many stochastic thermodynamics models of one classical system observing another classical system without any back-action [13,20,22,26,32,33] are "chained together". As an example, [3,8] considers a tripartite system where receptors in the wall of a cell observe the concentration level of a ligand in a surrounding medium, with no back-action on that concentration level, while a memory observes the state of those receptors, again with no back-action. This is exactly the scenario considered in Fig. 1, just without subsystem 4; subsystem 3 is the concentration level in the medium, subsystem 2 is the set of receptors in a cell observing that concentration level, and subsystem 1 is the memory within the cell observing the state of the ligand receptors.
I use the term "dependency constraint" to mean the specification for a subsystem i in the composite system of which other subsystems can affect its dynamics. So it is a constraint on the rate matrix of the composite system. In this paper I use stochastic thermodynamics to analyze the minimal heat that a composite system must dissipate if it obeys a given set of dependency constraints (each constraint concerning the dynamics of a different subsystem). The analysis holds for arbitrary sets of dependency constraints, allowing the subsystems to interact with one another as they all evolve, e.g., as in Fig. 1.
To begin, I translate a given set of dependency constraints into a convex polytope, P , in a unit simplex. I also translate the combination of the dependency constraints, an initial distribution p 0 (x), and a final distribution p t f (x), into F, a linear function over P . My main FIG. 1. Four subsystems, {1, 2, 3, 4} interacting in a multipartite process. The red arrows indicate dependencies in the associated four rate matrices. B evolves autonomously, but is continually observed by A and C. (The implicit assumption that B is not affected by the back-action of the measurement holds for many real systems such as colloidal particles and macromolecules [23].) So the statistical coupling between A and C could grow with time, even though their rate matrices do not involve one another. The three overlapping sets indicated at the bottom of the figure specify the three units of a dependency structure for this process.
result is to show that for any point π ∈ P , F(π) is a lower bound on the total heat that must be dissipated into the baths by running any process that is consistent with the constraints and maps p 0 into p t f . Finding the strongest such bound on the dissipated heat is just a linear programming problem. The results in [4,34,36] are recovered as the special case where the constraints are maximal, in that no interactions among the subsystems are allowed whatsoever.
The new lower bound given by my main result is not always stronger than the conventional Landauer bound. However, for any set of constraints on the rate matrix, there is an initial distribution p(x(0)) and conditional distribution p x(t f ) | x(0) such that any rate matrix that obeys those constraints and implements that conditional distribution will result in a non-negative lower bound on the EP, i.e., a lower bound at least as strong as the conventional Landauer bound. Indeed, for some sets of rate matrix constraints, the new EP bound is stronger than the conventional Landauer bound no matter what p(x(0)) and p x(t f ) | x(0) are (so long as that conditional distribution is consistent with the constraints on the rate matrix).
As an example, suppose we modify the scenario considered in [3,8] by introducing a second cell, which is observing the same external medium as the first cell. Assume that the cells are far enough apart physically so that their dynamics are independent of one another. This gives us the precise scenario in Fig. 1, where subsystem 4 is the state of the receptors of that second cell. Ex. 4 below analyzes an example of this scenario. In this example |X 2 |= |X 4 |= 2 (i.e., the state of each cell's receptors is coarse-grained into two bins, which I assume are always internally thermalized). It is also assumed that x 2 = x 4 with probability 1 at the start of the process, e.g., because some molecules were flushed through the medium at the start of an experiment in order to reset those receptors, or because the cells were both just born. Finally, it is assumed that the composite system evolves long enough so that both receptors lose all information about their initial states.
Applying the main result of this paper to this scenario establishes that the minimal total EP of the composite system is at least ln 2. In contrast, the conventional Landauer bound on EP is 0. This new, strengthened bound holds no matter how the state of the medium evolves as it is being observed, and no matter how the two sets of cell receptors observe the medium.
In the next section I formalize dependency constraints for composite systems as restrictions on the rate matrix of a continuous-time Markov chain (CTMC). I then use this formalization to derive an expression for the EP of a composite system that involves the dependency constraints of its rate matrix, but also involves other factors. In the following section I derive a lower bound on that expression for EP purely in terms of those dependency constraints, the initial distribution p(0), and the ending distribution p(t f ). This lower bound is my main result. In the ending section I present examples.
II. RATE MATRIX DEPENDENCY STRUCTURES I begin by defining notation. First, I write N for a particular set of N subsystems, with finite state spaces x indicates a vector in X, the joint space of N . For any A ⊂ N , I write −A := N \ A. So for example, x −A is the vector of all components of x other than those in A. For any set L, ∆ L is the associated unit-simplex. In addition, for any function f (p), I write The set of bits is B = {0, 1}. I write the Kronecker delta as δ(a, b). For any family of sets, A distribution over a set of values x at time t is written as p X (t), with its value for x ∈ X written as p x (t), p t (x) or p(x(t)), whichever is more convenient. Similarly, I write p(x(t) | x(t )), for the conditional distribution of the state at time t given the state at time t , etc. I write Shannon entropy as S(p X (t)), S t (X), or S X (t), as convenient.
A (dependency) unit ω at time t is a set of subsystems such that for some associated rate matrix K(ω; t). Intuitively, a unit is any set of subsystems whose evolution is inde-pendent of the states of the subsystems outside the unit. Note though that in general, the evolution of the subsystems outside of a unit may depend on the states of subsystems inside the unit. Note as well that any nonempty intersection of units is a unit, as is any union of units.
As an example, [1,7,8] investigate a special type of bipartite system, where the "internal" subsystem B observes the "external" subsystem A, but cannot affect the dynamics of that external subsystem. So A is its own unit, evolving independently of B, while B is not its own unit; its dynamics depends on the state of A as well as its own state. Another example of these definitions is illustrated in Fig. 1.
I will call a set of units defined over a set of subsystems N a dependency (unit) structure, and write it as N * , if has the following properties: 1. The union of the units in N * equals all of N .

N * is closed under intersections of its units;
3. For simplicity I don't allow N * to contain any "orphan" unit ω where every subsystem i ∈ ω is already contained in some unit ω ⊂ ω.
I will sometimes say that N * represents the set of subsystems N . In general, a given process can be represented with more than one dependency structure, since for example any process over N can be represented as a dependency structure with a single unit, N itself. Also, in general there are sets of subsystems A ⊂ N which are not unions of units, and so cannot be represented by any dependency structure. For simplicity, from now on I assume that the set of units doesn't change with t. The dynamics of any two units ω, α ⊂ ω must be consistent with one another, i.e., for all p x ω (t) = p x α ,x ω\α (t), it must be that Using Eq. (1) to evaluate the two derivatives and then setting p x α (t) to a delta function, we see that for all x α , x α , and x ω\α , it must be that Note that this must hold whether or not the units ω, α are elements of some particular dependency structure. As an example, this self-consistency condition always holds (and therefore so does Eq. (3)) in a multipartite process, in which the rate matrix of the overall system can be represented as a sum of rate matrices of the individual subsystems [11,37]. It will often be convenient to re-express a dependency structure as a directed graph. Define the dependency graph Γ N * = (N * , E) by the rule that there is an edge e ∈ E from node ω ∈ N * to node ω ∈ N * iff both: ω ⊆ ω,  (1,4), (3,4), (5,4), (2,1,3,4,5), (6,1,3,4,5)}. The left panel shows the associated dependency graph, e.g., the leaf node F is unit 4, the node C is unit (3,4), node D is unit (5,4), and node A is unit (2,1,3,4,5). and there is no intervening unit ω such that ω ⊆ ω ⊆ ω. (Note that Γ N * is a directed acyclic graph (DAG).) For a dependency structure N * where N ∈ N * , there would be a single root of the dependency graph, but if N ∈ N * , the dependency graph has multiple roots.
I will abuse notation and sometimes treat a unit ω as a set of subsystems while at other times I treat it as a single node in Γ N * . I write the set of parents of any node ω ∈ Γ N * as pa(ω), and the set of its descendants as desc(ω), with fa(ω) := ω ∪ desc(ω), the "family" of node ω. The maximal number of nodes in any directed path that starts at ω is the height of ω. So any unit ω which has no sub-units contained in it is a leaf node of Γ N * , with height 1. (The maximal height of all nodes in Γ N * is simply called "the height of N * ".) I write Γ R N * for the set of root nodes in Γ N * .
As an example, the dependency graph of Fig. 1 has two root nodes, ω and α, and one leaf node, ω , which is their common child. The height of the graph is 2.
Another, more complicated example is shown in Fig. 2. This example could be used to model a simple extension of the triparitite system considered in [3,8]. To see this, label the joint concentration levels in the medium surrounding a cell of three separate ligands as subsystem 4. Label the ligand receptors in the wall of a cell that each observe a separate one of the three ligand concentrations, without any back-action, as subsystems 1, 3, 5. Finally, let subsystems 2 and 6 be two internal memories in the cell, each recording its own summary statistic concerning the states of the three sets of ligand receptors, again with no back-action. The associated dependency constraints are of the form given in Fig. 2.
Finally, define a conditional distribution for the ending joint state given an initial joint state, p x(t f ) | x(0) , to be consistent with a specified dependency structure if there is some rate matrix that obeys that dependency structure and that implements p x(t f ) | x(0) .

III. THERMODYNAMICS OF DEPENDENCY STRUCTURES
As in the conventional Landauer bound, for simplicity I assume that the composite system is connected to a work reservoir and one heat bath, with units chosen so that k B T = 1. (The results below also hold if different subsystems are connected to different heat baths all at the same temperature, as in analyses of multipartite systems [11].) So in the standard way, the expected entropy flow (EF) rate of any unit ω ⊆ N at time t is [6,31]: (Note that this is entropy flow from ω into the heat bath.) I refer to Q ω (t) as a local EF rate, and define the global EF rate as Q N (t) .
Make the associated definition that the expected EP rate of ω at time t is I refer to σ ω (t) as a local EP rate, and define the global EP rate as σ (t) := σ N (t) . For any unit ω, σ ω (t) ≥ 0, since σ ω (t) has the usual form of an EP rate of a single system. (See [37] for a discussion of the relation between local EP rates and similar quantities discussed in [11,12,28].) Write the local EP generated by a unit ω during the process as and similarly write σ = σ N for the global EP. In Appendix A, Eq. (3) and the log sum inequality [5] are used to prove that for any two units ω, α ⊂ ω, not necessarily part of a dependency structure, σ ω (t) ≥ σ α (t) at all times t. Therefore In particular, this holds if α is a union of units (since a union of units is itself a unit). In addition, it is shown in [34,36] that in the special case where there is a set of units {α j } who have no overlap with another, for any unit ω ⊃ ∪ j α j , (See also Eq. (26) below.) Let N * = {ω j : j = 1, 2, . . . , n} be a dependency structure. Suppose we have a real-valued vector f indexed by the sets of N * . The associated inclusion-exclusion sum (or just "in-ex sum") is defined as (Note that the precise assignment of integer indices to the units in N * is irrelevant.) The time-t in-ex information is defined in terms of this notation, as where all the terms in the sums on the RHS are marginal entropies over the (distributions over the subsystems in) the indicated units. As an example, if N * consists of two units, ω 1 , ω 2 , with no intersection, then the expected in-ex information at time t is just the mutual information between those units at that time. More generally, if there an arbitrary number of units in N * but none of them overlap, then the expected in-ex information is what is called the "multi-information", or "total correlation", among those units [15,30,37]. When local detailed balance holds, we want to be able to interpret Q ω (t) in the usual way as the expected rate of heat flow due to joint transitions of the states of one or more of the subsystems in unit ω, with the state of all subsystems outside of ω fixed and arbitrary. It will also be convenient to suppose that the dependency structure is rich enough so that no state transition can occur that simultaneously changes the state of all subsystems in a set α unless α ∈ N * . (So in particular, if N ∈ N * , then no state transition can occur in which every subsystem simultaneously changes its state.) As an example, this supposition would hold if each unit were attached to its own heat bath, or equivalently, to statistically decoupled portions of the same heat bath [11]. (See [37] for a detailed example involving multipartite systems.) In Appendix B, Rota's extension of the inclusionexclusion principle is combined with this supposition to show that This implies that the global EP rate is a result first derived in [37] for the special case of multipartite processes. Integrating Eq. (14) from the beginning to the end of a process gives Eq. (15) applies to any dependency structure, including dependency structures that are subsets of other dependency structures. In addition, for any dependency structure M * over a set of subsystems M ⊂ ω, Eq. (8) and the fact that the union of a set of units is itself a unit means that σ ω − σ M ≥ 0. Therefore using Eq. (15) to expand σ M gives (Note that Eq. (16) holds even if the units in M * are not in N * , which can happen because in general any process obeying a given set of dependency constraints can be represented by more than one dependency structure.)

IV. A STRENGTHENED LANDAUER BOUND
In this paper I use Eqs. (8), (9), (15) and (16) and the inclusion-exclusion principle to derive lower bounds on EP. To do this I first define V (N * ), a set of distributions over the Boolean hypercube, B |N * | . Next, I define a "centering distribution" to be any convex combination of the elements of V (N * ) which equals (1/|N * |, 1/|N * |, . . .), the uniform distribution over the Boolean hypercube. My first main result, presented in Proposition 1, is a function taking each such centering distribution to a different lower bound on global EP.
The set V (N * ) is the union of two sets of distributions over B |N * | , defined as follows: I) For any ω ∈ N * , write δ ω for the distribution in B |N * | which is all 0's except for a 1 in its ω component. Using this notation, define V 1 (N * ) as the set of all distributions α over B |N * | which obey at least one of the following three conditions: for a ω ∈ N * , v ∈ desc(ω); I will refer to any distributions that obey these conditions as type-1, type-2, and type-3 distributions, respectively.
Next, note that units A, C, D, E, F are all units contained in unit A (i.e., those nodes are contained in family of node A). Similarly, units F, C are all units contained in C. Therefore the units that are in A but not in C are A, D, E. Accordingly, the (unique) type-3 distribution for the pair of units ω = A, v = C is α = (1/3, 0, 0, 1/3, 1/3, 0). II) For any unit ω, abuse notation and define ω * as the dependency structure ω ∪ desc(ω). Using this shorthand, write M(ω) ⊂ ω for any set of subsystems which can be represented by a dependency structure M(ω) * ⊂ ω * [16]. Define V 2 (N * ) as the set of all distributions over B |N * | of the form for some ω ∈ N * and associated dependency structure M(ω) * ⊂ ω * . I will refer to any such distribution as a type-4 distribution. Note that any type-4 distribution α uniquely specifies both ω and M(ω) * . Given this, I will sometimes abuse notation and write α * for the dependency structure M(ω) * specified by a type-4 distribution α.
To illustrate type-4 distributions, again consider the left panel in Fig As shorthand, write V (N * ) := V 1 (N * ) ∪ V 2 (N * ). As a final piece of terminology, let U = {u} be any set of distributions over some shared space. I will say that U is centered if there exists a centering distribution π ∈ ∆ U such that E π u = u∈U π u u equals the uniform distribution. Note that the set of all centering distributions of any U is a convex polytope.
The following is proven in Appendix C: Note that the values of the in-ex informations I N * and ∆I α * at the beginning and end of the process are fully specified by p 0 and p t f . So given a centering distribution, Proposition 1 provides a lower bound on global EP defined purely in terms of p 0 and p t f . The precise rate matrix is irrelevant, so long as it has N * as a dependency structure and maps p 0 to p t f . As an example of Proposition 1, suppose that Γ N * has height 2. (So there are no units ω, ω , ω ∈ N * such that ω ⊂ ω ⊂ ω.) Then all delta function distributions over B |N * | are type-1 distributions, and so contained in V 1 (N * ). Accordingly, the dependency structure is centered by a distribution π that is uniform over all α ∈ V 1 (N * ) and equals 0 for all α ∈ V 2 (N * ). Plugging this into Proposition 1 establishes that the EP of any process with a height-2 dependency structure N * is lower-bounded by −∆I N * .
Note that in general, we can represent any process by using a dependency structure of height 2. (For example, we can do that by combining all subsystems that are members of some unit ω that is not a root node of Γ N * , into one, overarching unit.) Accordingly, for any process, we can always find an associated dependency structure N * for which σ ≥ −∆I N * .
In addition, it is proven in Appendix D that for any dependency structure N * , no matter what its height, V (N * ) is centered. (The set of all associated centering distributions of V (N * ) is the convex polytope discussed in the introduction.) In general, finding the optimal such centering distribution -the one that maximizes the bound in Proposition 1, and so provides the strongest lower bound on global EP -only requires solving a linear programming problem.
Unfortunately, as illustrated below, there are some dependency structures N * where the bound in Proposition 1 is negative for an appropriate initial distribution p 0 (x) and conditional distribution p(x(t f ) | x(0)) consistent with N * , no matter what centering distribution we use. In such cases, Proposition 1 does not provide a stronger bound on EP than the conventional Landauer's bound.
On the other hand, as also illustrated below, typically the bound in Proposition 1 will be stronger than the conventional Landauer's bound. Indeed, for every dependency structure N * , and every associated centering distribution, there are initial distributions p 0 (x) and conditional distributions p(x(t f ) | x(0)) that are consistent with N * where the EP bound in Proposition 1 at least as strong as Landauer's bound: Proposition 2. Let N * be any dependency structure that does not have N itself as a member. Then there exists an initial joint distribution p 0 (x) and a conditional distribution p(x(t f ) | x(0)) consistent with N * such that for any associated centering distribution π α , for every rate matrix that both implements that p(x(t f ) | x(0)) and obeys the dependency structure.
(See Appendix E for proof.) Write the polytope of all centering distributions of the dependency structure N * as P (N * ), and write the strongest lower bound on EP given by Proposition 1 as Combining Propositions 1 and 2 establishes that for any dependency structure N * there are pairs of p 0 (x) and a conditional distribution p(x(t f ) | x(0)) consistent with N * such that In contrast, the conventional Landauer's bound says only that Q + ∆S ≥ 0, no matter what p 0 , p t f or N * are. Summarizing, suppose we are given a dependency structure N * , an initial distribution p 0 (x), and a con- Then we know that −∆I N * − α∈V 2 (N * ) π α ∆I α * is a lower bound on the EP, for any π that is a centering distribution for N * . These lower bounds are simple to evaluate, and are often stronger than the Landauer bound. We can find the strongest such lower bound on EP due to the dependency structure N * by solving a linear programming problem.
Furthermore, in general, it is possible to represent any given set of constraints with more than one dependency structure. Each one of them results in its own strongest lower bound on EP, given by solving the associated linear programming problem. So to find the strongest Landauer bound for a given set of constraints, we should solve all the linear programming problems specified by the dependency structures that can represent those constraints.
This result extends the previous strengthenings of Landauer's bound derived in [4,34,36], which all assume that the units have no overlap, to the case where the units may overlap with one another in arbitrary ways, even if none of the subsystems are fixed in the dynamics. In addition to this result, going from a set of constraints, p 0 and p t f to a lower bound on EP, a secondary result is that for any set of constraints, there is a p 0 and p t f that results in a strictly positive lower bound on EP, stronger than the conventional Landauer bound. . So under dependency structure A * , subsystem 2 evolves independently, while the dynamics of both subsystems 1 and 3 depend on the state of subsystem 2. In contrast, under B * , all three subsystems evolve independently. The height of both of the associated dependency graphs is ≤ 2. Accordingly, we can choose a centering distribution that puts zero weight on all elements in V 2 (N * ), which will be assumed for these examples.
Example 1: Suppose that the conditional distribution implemented by the process erases both subsystems 1 and 3 and doesn't change the state of subsystem 2. So Suppose as well that p 0 (x) = (1/2) 1 j=0 i δ(x i (0), j). So the three bits must initially have the same state -but that shared state is uniformly randomly set.
Evaluating, since the t = 0 joint entropy of the full system is ln 2, I B * (0) = − ln 2 + 3 ln 2 = 2 ln 2. Similarly, I B * (t f ) = − ln 2 + ln 2 = 0. So plugging into Proposition 1 shows that the minimal EP is at least 2 ln 2 for dependency structure B * , in which all subsystems evolve independently while the discrete-time conditional distribution p x(t f ) | x(0) is implemented. In contrast, I A * (0) = − ln 2 + 3 ln 2 − 3 ln 2 + ln 2 = 0, and similarly I A * (t f ) = 0. So the minimal EP is only lower-bounded by 0 for dependency structure A * , in which the same conditional distribution is implemented, but both subsystems that are being erased are able to observe the (unchanging) state of subsystem 2.
In this particular scenario, we can evaluate the minimal EP for both dependency structures exactly [17]. Doing so confirms that ∆I in fact equals the minimal EP exactly, for both dependency structures. The difference between those two minimal EP values illustrates that implementing the exact same conditional distribution starting from the exact same initial distribution can result in different minimal heat dissipations, depending on the dependency structure.
We can generalize this scenario, to consider any process where no subsystem in the intersection of two or more distinct units ever changes its state. Suppose we represent this process with a dependency graph of height 2, e.g., like the one illustrated in Fig. 3. Since the leaf nodes are intersections of units, by our hypothesis none of the subsystems in those leaf nodes ever changes its state. Accordingly, where the sum runs only over the root nodes.
FIG. 3. An arbitrary example of a dependency graph of height 2. The first process considered in Ex. 1 can be represented with this kind of dependency structure, where the subsystems in the leaf nodes never change their states. The last process considered in that example relaxes this requirement.
Moreover, since any unit that never changes its state generates no EP, if no subsystem in the intersection of two units ever changes its state, then Since the lowest each σ ω can equal is zero (when each unit ω evolves semi-statically), we can use this with Eqs. (15) and (23) to establish that minimal EP equals exactly, i.e., Eq. (23) is a strict lower bound on the EP. This lower bound holds no matter what p 0 (x) and p(x(t f ) | x(0)) are (so long as p(x(t f ) | x(0)) is consistent with the dependency structure).
As an illustration of this result, suppose that in fact no two units have nonempty intersection. Then the minimal EP is This quantity is the drop among the subsystems in their multi-information, a formula for the minimal EP previously derived in [34,36]. By repeated application of the data-processing inequality, it is easy to confirm that this lower bound on the EP is non-negative.
Note though that Eq. (23) holds for any process where the dependency structure is of the type shown in Fig. 3, so long as the ending entropies of (the joint subsystems in the units corresponding to) the leaf nodes equals the starting entropies. This is true even if the subsystems in the leaf nodes do change state during the process. Since that dependency graph has height 2, Proposition 1 tells us that the expression in Eq. (23) is a lower bound on the EP of such a process, and is non-negative. However, in general, if the subsystems in the leaf nodes change their states during the process, that lower bound may not be tight.
Example 2: In light of the fact that subsystem 2 never changes its state in Ex. 1, suppose that the conditional distribution of that example is implemented using only subsystems 1 and 3. In other words, suppose we have a modified process where both 1 and 3 are erased, and are perfectly correlated under the initial joint distribution, but subsystem 2 doesn't exist, so that subsystems 1 and 3 evolve independently of each other.
The drop in in-ex information in this case is ln 2. Again, one can confirm that this lower bound on the minimal EP is actually an equality. (This parallel bit erasure scenario was previously investigated in [35,36].) Note that this minimal EP of parallel bit erasure using only two subsystems is less than the minimal EP for parallel bit erasure using three subsystems, investigated in Ex. 1 for the analogous dependency structure, B * . So even though neither subsystem 1 nor subsystem 3 observe subsystem 2 in the process analyzed in Ex. 1 for dependency structure B * , and even though subsystem 2 never changes its state in that process, simply including it in the model increases the minimal total entropy production.
Example 3: Return to the situation described in Ex. 1, with the dependency structure A * . Suppose that initially, x 1 = x 3 with uniform probability over their two possible joint states, and that x 2 is independent of both x 1 and x 3 , also with uniform probability over its states: Therefore S(p(0)) = 2 ln 2, and so I A * (p(0)) = [2 ln 2 + 2 ln 2 − ln 2] − 2 ln 2 (28) = ln 2 (29) Suppose as well that reflecting the dependency structure, x 1 and x 3 evolve independently of one another, conditioned on the state x 2 , eventually losing all information about their own initial states and the initial state of x 2 . So , and so = 0 Combining Eqs. (29) and (34) establishes that the minimal EP is lower-bounded by ln 2. Note that we can derive this lower bound on the EP even though both subsystems 1 and 3 are continually observing subsystem 2 during the process, and even if subsystem 2's state is changing throughout the process. In fact, this lower bound holds no matter what the ending distribution p t f (x) is, so long it can be written as in Eq. (32). (So in particular, as discussed in the introduction, it applies to a simple extension of the cell-sensing scenario analyzed in [3,8].) Example 4: This example presents a case where the new bound is not stronger than the Landauer bound. Again consider the three bits of Ex. 1, with dependency structure A * , with the same initial distribution p(x 0 ). However, now suppose that during the dynamics, neither x 1 nor x 3 change their state, while x 2 completely uniformly randomizes.
As in Ex. 1, I A * (p(0)) = 0. However, with this different dynamics S(p(t f )) = 2 ln 2, and so I A * (t f ) = 3 ln 2 − 2 ln 2 = ln 2. So in this scenario, ∆I A * > 0. (Since the actual minimal possible EP of the full system cannot be less than zero, this means that ω σ ω > σ ≥ 0 in this scenario.) On the other hand, by Proposition 2, we know that for some other initial distribution p(x(0)) and / or some other conditional distribution p x(t f ) | x(0) that is consistent with the dependency structure, −∆I A * is a strictly positive lower bound on EP.
As an aside, note that in this example, the composite system's initial distribution is a Markov random field, with cliques equal to the units in A * : This is why the entropy of the initial distribution equals the in-ex sum of the entropies of the units, i.e., why the initial in-ex information equals 0. In addition, of course, the conditional dependencies of the dynamics is given by the units in A * . Nonetheless, the ending distribution is not given by a Markov random field with cliques equal to the units in A * . This is why the entropy of the final distribution can differ from the in-ex sum of the entropies of the units, which in turn is what allows the These interactions are the same as in Fig. 2, except that subsystem 2 no longer observes subsystem 1, and subsystem 6 no longer observes subsystem 3.
Since π places no probability mass on any type-4 distribution, Proposition 1 tells us that the total EP is lower-bounded by where ∆S(ab...) is shorthand for the change in the joint entropy of the subsystems ab... between t = 0 and t = t f . By Proposition 2, we are guaranteed that for some initial distribution p(0), and some final distribution p(t f ) that is generated from p(0) by a process consistent with the dependency structure, the lower bound on EP given by Eq. (40) is strictly positive. Example 6: Finally, consider again the set of six subsystems, interacting with the dependency structure shown in Fig. 2. As in Ex. 5 this dependency structure has height 3, and so we cannot construct a centering distribution only using type-1 distributions over B 5 . However, unlike in Ex. 5, we cannot construct a centering distribution without using a type-4 distribution. In particular, the two distributions α 3 , α 4 introduced in Ex. 5, which are type-3 distributions for the dependency structure in Fig. 4, are not type-3 distributions for the dependency structure in Fig. 2.
Instead, consider the following six distributions over the units So the distribution π with all of its six components equal to 1/6 is a centering distribution. The associated lower bound on global EP is Expanding this expression is left as an exercise for the interested reader. (Note that since the dependency structure in Fig. 2 differs from that in Fig. 4, the term −∆I N * in Eq. (41) is not given by Eq. (40).)

VI. DISCUSSION
In this paper I derive a strengthened version of the conventional Landauer bound, which applies to any composite system whose constituent subsystems obey a given set of constraints on how their dynamics can depend on one another. In contrast to earlier related work, this bound applies even if the subsystems are all evolving in time, with arbitrary overlaps in the dependencies of their dynamics.
To derive this new bound, first I translate any set of dependency constraints into a set of "dependency units", where each dependency unit ω is a set of subsystems whose dynamics is self-contained, not depending on the state of any subsystems outside of ω. The precise strengthened form of Landauer's bound derived here is defined in terms of a "dependency structure", which is any collection of dependency units which jointly encompass all subsystems in the composite system. The bound is expressed in terms of a novel informationtheoretic function, specified by the dependency structure, evaluated for the initial joint distribution over the state of all the subsystems and for the final such joint distribution.
In general, any set of dependency constraints can be represented by more than one dependency structure. For example, this can usually be done by coarsegraining the units in a dependency structure, i.e., by replacing a set of multiple units {ω, ω , . . .} in the dependency structure with a single unit, which encompasses all of the subsystems in {ω, ω , . . .}. Each of these dependency structures, all representing the same set of dependency constraints, provide a different lower bound on EP. It is left for future work to find general rules for which of a set of candidate dependency structures representing the same set of dependency constraints result in the strongest lower bound on EP (other than simply trying them all).
where the second line uses Eq. (A1). Combining and using Eq. (A1) again establishes that Again plugging into Eq. (6), this time for the EP rate of unit α, completes the proof. Next, by our supposition that no state transition can occur that simultaneously changes the state of all subsystems α unless α ∈ N * , every element of T that can occur is contained in at least one element of T N * . So T N * is a cover of the set of all state transitions that can occur. Accordingly, by Rota's extension of the inclusionexclusion principle, (Note that unlike in the conventional inclusionexclusion principle, in this extension we don't need to have f (i) defined for individual subsystems i.) Identifying f (T N * ) with Q N (t) and identifying f (τ ω ) with Q ω (t) for each ω ∈ N * completes the proof. The proof has two parts. First, I construct a function f : N → R such that for all units ω ∈ N * , i∈ω f i = σ ω . (Note that in general, any subsystem i will be in more than one unit ω, and so this function f is the solution to a set of coupled equations.) I will then apply the inclusion-exclusion principle with this f in order to replace the first in-ex sums over unit ω on the RHS of Eq. (15) with a conventional sum over subsystems, i f i .
In the second part of the proof I use the hypothesized existence of a centering distribution to provide a lower bound on i f i , expressed purely in terms of p 0 and p t f . Plugging in to Eq. (15) then completes the proof.
To begin, for each unit ω, define ω as the set of all subsystems in ω that are not in any of the units in desc(ω).
(As an example, in Fig. 1, ω is the pair of subsystems 1 and 2.) Because N * is closed under intersections and covers N , every subsystem is in ω for exactly one unit ω ∈ N * . Moreover, because there are no orphan units allowed, ω is nonempty for every unit ω. Note that if ω ⊂ ω for two units ω, ω , then the subsystems in ω must evolve independently of the states of any subsystems in ω , but the reverse need not be true. In other words, if there is an edge from ω to ω, then there may be subsystems in ω whose dynamics depends on the state of subsystems in ω, but not vice-versa.
For all j ∈ N, let Ω j be the set of all nodes in Γ N * , with height j. So in particular, Ω 1 is the the set all units with no subunits. For every ω ∈ Ω 1 , for all subsystems i ∈ ω, set So by construction, for all ω ∈ Ω 1 , i∈ω f i = σ ω (C2) Since σ ω ≥ 0 for all ω ∈ N * , this means that i∈ω f i ≥ 0 for all ω ∈ Ω 1 . Next, note that any for any ω ∈ N * , the set of units in desc(ω) is closed under intersections. This allows us to define for all j ∈ N , all ω ∈ Ω j , and all i ∈ ω. (Note that any such i will be assigned a value f i exactly once in this procedure.) In general, it could be that f i is negative. Note though that since no two units in Ω 1 have any overlap, for all ω ∈ Ω 2 , i.e., Eq. (C2) holds for unit ω. Next, assume that Eq. (C2) holds for all ω ∈ Ω k−1 for some integer k > 2. Then by Eq. (C3) and the inclusionexclusion principle, for any v ∈ Ω k , (Note that the inclusion-exclusion principle holds for arbitrary functions f , not just for nowhere-negative functions.) Since σ v ≥ 0, this means that we are guaranteed that i∈v f i ≥ 0. Iterate this procedure going from nodes in Ω k−1 to those in Ω k until all units have been considered, so that values f i have been assigned to all subsystems i ∈ N . By induction, at the end of this procedure, for all units ω ∈ N * , Eq. (C2) will hold and i∈ω f i ≥ 0. In addition, by the inclusion-exclusion principle, (Note that since N ∈ N * , Eq. (C12) does not imply that i∈N f i = σ N . So we cannot combine Eq. (C14) with the fact that global EP is ≥ 0 to establish that ω∈N * σ ω is also non-negative.) It will be convenient to define new variables that equal sums of f i over small sets of subsystems i. For all ω ∈ N * , define where the second line follows from Eq. (C3). Since each subsystem i is in ω for exactly one unit ω, for any v ∈ N * , where the last line uses Eq. (C12). Using similar reasoning shows that ω∈N * g ω = i∈N f i . Combining this with Eq. (C14) and Eq. (15) gives This completes the first part of the proof. In the second part I derive a lower bound on the RHS of Eq. (C20). First, to reduce the complexity of the equations, I will translate all distributions α into binary-valued vectors: 1.α = α for any type-1 distribution α; 2.α = α ω ∈fa(ω) 1for any type-2 distribution α; 3.α = α ω ∈fa(ω)\fa(v) 1 for any type-3 distribution α; 4.α = α ω ∈ω * \M * (ω) 1 for any type-4 distribution α; Note that every component of every vectorα is either a 0 or a 1. I will refer to any vectors that obey condition (1) as type-1 vectors, and similarly for vectors obeying conditions (2), (3) and / or (4). Now make three suppositions. First, suppose that for all vectorsα of types 1, 2 or 3, ω∈N * g ωαω ≥ 0 (C21) Next, suppose that for all vectorsα of type-4, and all associated dependency structuresα * , ω∈N * g ωαω ≥ −∆Iα * Now, hypothesize that there is a centering vector γ all of whose components are non-negative such that