op_737_two_level_submodular
For n > 2, any surjective block-assignment map proj : Fin n → Fin 2, any Gibbs vector γ in stdSimplex ℝ (Fin n) with strictly positive entries that is constant on the fibers of proj, and any initial vector x in stdSimplex ℝ (Fin n), the block population capacity block_population_capacity proj γ x is submodular.
Statement
theorem op_737_two_level_submodular {n : ℕ} (hn : 2 < n) (proj : Fin n → Fin 2) (hsurj : Function.Surjective proj) (γ : Fin n → ℝ) (hγ_simplex : γ ∈ stdSimplex ℝ (Fin n)) (hγ_pos : ∀ i, 0 < γ i) (hγ_block : ∀ i j, proj i = proj j → γ i = γ j) (x : Fin n → ℝ) (hx : x ∈ stdSimplex ℝ (Fin n)) : is_submodular (block_population_capacity proj γ x)- Source
- arXiv:2610.35433 Sec. Discussion
- Verified
- 31 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 6
- is_submodularA set function is submodular: for S inside T and j outside T, the marginal value of j over T is at most its marginal value over S.
- block_population_capacityGiven a block-assignment map proj : Fin n → Fin m, vectors γ, x : Fin n → ℝ, and a subset S : Finset (Fin m), block_population_capacity…
- thermally_reachable_block_populationsGiven a block-assignment map proj from Fin n to Fin m and vectors γ, x : Fin n → ℝ, thermally_reachable_block_populations proj γ x is the…
- thermally_reachable_microA microstate distribution x' on n energy levels is thermally reachable from an initial distribution x with respect to the Gibbs vector γ…
- fiber_sum_vecGiven an assignment of n microstates to m energy levels, the fiber sum vector of a microstate distribution y has k-th component equal to…
- is_gibbs_stochasticA square transition matrix T on n microstates is Gibbs-stochastic with respect to an equilibrium probability vector γ if its entries are…
Read back from the Lean
Given:
- a natural number $n$ such that $2 < n$,
- a surjective function $\text{proj} : \text{Fin } n \to \text{Fin } 2$,
- a probability vector $\gamma \in \text{stdSimplex } \mathbb{R} (\text{Fin } n)$,
- assuming $\gamma_i > 0$ for all $i \in \text{Fin } n$,
- assuming that $\text{proj}(i) = \text{proj}(j)$ implies $\gamma_i = \gamma_j$ for all $i, j \in \text{Fin } n$ ($\gamma$ is constant on the fibers of $\text{proj}$),
- a probability vector $x \in \text{stdSimplex } \mathbb{R} (\text{Fin } n)$,
the theorem asserts that the set function block_population_capacity proj γ x (which maps each subset $S \subseteq \text{Fin } 2$ to the supremum of $\sum_{k \in S} p_k$ over all block-population vectors $p : \text{Fin } 2 \to \mathbb{R}$ thermally reachable from $x$ under $\gamma$) is submodular.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The proof establishes submodularity of the block population capacity on a two-level system in two main phases. First, an elementary exhaustion shows that any set function on subsets of a two-element universe is submodular provided v(univ) + v(∅) ≤ v({0}) + v({1}), as this inequality directly verifies diminishing returns for every possible pair of subsets. Second, this numerical criterion is verified for the block population capacity: the empty set has capacity 0, the universal set has capacity at most 1 because reachable block populations always sum to 1, and the sum of capacities of {0} and {1} is at least 1 because the initial microstate itself is thermally reachable via the identity channel. Combining these bounds immediately establishes the criterion, concluding the proof.
To check submodularity on Fin 2, the test set T must be ∅, {0}, or {1}.
By definition, v is submodular if v(T ∪ {j}) - v(T) ≤ v(S ∪ {j}) - v(S) whenever S ⊆ T and j ∉ T. Since j ∉ T and the universe has only two elements, T cannot be the universe. A finite case exhaustion (decide) shows that T must be ∅, {0}, or {1}.
intro S T j hST hj have hT : ∀ (T : Finset (Fin 2)) (j : Fin 2), j ∉ T → T = ∅ ∨ T = {0} ∨ T = {1} := by decide rcases hT T j hj with rfl | rfl | rfl
Submodularity holds when T = ∅.
When T = ∅, the inclusion S ⊆ T implies S = ∅ by subset_empty. Both sides of the inequality are identical (v({j}) - v(∅)), so the inequality holds trivially by linear arithmetic.
uses
subset_empty· have hS : S = ∅ := subset_empty.mp hST subst hS linarith
Submodularity holds when T = {0}.
Since j ∉ {0}, we must have j = 1. Since S ⊆ {0}, either S = ∅ or S = {0}. If S = {0}, then S = T and the inequality is an identity. If S = ∅, then T ∪ {1} = univ and S ∪ {1} = {1}, so the inequality becomes v(univ) - v({0}) ≤ v({1}) - v(∅), which rearranges to v(univ) + v(∅) ≤ v({0}) + v({1}), matching the hypothesis h_univ.
· have hj0 : ∀ j : Fin 2, j ∉ ({0} : Finset (Fin 2)) → j = 1 := by decide have hj' := hj0 j hj subst hj' have hS : ∀ (S : Finset (Fin 2)), S ⊆ {0} → S = ∅ ∨ S = {0} := by decide rcases hS S hST with rfl | rfl · have hu : (insert (1 : Fin 2) {0} : Finset (Fin 2)) = univ := by decide have h1 : (insert (1 : Fin 2) (∅ : Finset (Fin 2)) : Finset (Fin 2)) = {1} := by decide rw [hu, h1] linarith · linarith
Submodularity holds when T = {1}.
Symmetrically, j ∉ {1} forces j = 0, and S ⊆ {1} leaves S = ∅ or S = {1}. If S = {1}, both sides are identical. If S = ∅, inserting 0 yields v(univ) - v({1}) ≤ v({0}) - v(∅), which again rearranges to v(univ) + v(∅) ≤ v({0}) + v({1}) and is verified by linear arithmetic.
· have hj1 : ∀ j : Fin 2, j ∉ ({1} : Finset (Fin 2)) → j = 0 := by decide have hj' := hj1 j hj subst hj' have hS : ∀ (S : Finset (Fin 2)), S ⊆ {1} → S = ∅ ∨ S = {1} := by decide rcases hS S hST with rfl | rfl · have hu : (insert (0 : Fin 2) {1} : Finset (Fin 2)) = univ := by decide have h0 : (insert (0 : Fin 2) (∅ : Finset (Fin 2)) : Finset (Fin 2)) = {0} := by decide rw [hu, h0] linarith · linarith
The block population capacity of the empty set is 0.
The capacity of ∅ is the supremum of ∑_{k ∈ ∅} p_k, which is identically 0 for every reachable block population p. The identity transition matrix shows that the set of reachable block populations is non-empty, so the image of this sum is the singleton {0}, whose supremum is 0 by csSup_singleton.
uses
Set.mem_image,Set.mem_singleton_iff,csSup_singletondsimp [block_population_capacity] have h_img : ((fun p => (0 : ℝ)) '' thermally_reachable_block_populations proj γ x) = {0} := by ext y simp only [Set.mem_image, Set.mem_singleton_iff] constructor · rintro ⟨p, hp, rfl⟩ rfl · rintro rfl have ⟨p, hp⟩ : (thermally_reachable_block_populations proj γ x).Nonempty := by use fiber_sum_vec proj x refine ⟨x, hx, ?_, rfl⟩ use fun i j => if i = j then 1 else 0 refine ⟨⟨fun i j => by dsimp; split_ifs <;> norm_num, fun j => by simp, fun i => by simp⟩, fun i => by simp⟩ exact ⟨p, hp, rfl⟩ rw [h_img, csSup_singleton]
The block population capacity of the universe is at most 1.
For any microstate x' reachable from x, x' remains in the probability simplex. Summing the block populations over all blocks groups the microstate entries by their fibers, which by Finset.sum_fiberwise equals ∑_i x'_i = 1. Since every reachable total block population is at most 1, the supremum is at most 1 by csSup_le.
uses
csSup_le,Set.mem_image_of_mem,Finset.sum_fiberwisedsimp [block_population_capacity] apply csSup_le · rcases (by use fiber_sum_vec proj x refine ⟨x, hx, ?_, rfl⟩ use fun i j => if i = j then 1 else 0 refine ⟨⟨fun i j => by dsimp; split_ifs <;> norm_num, fun j => by simp, fun i => by simp⟩, fun i => by simp⟩ : (thermally_reachable_block_populations proj γ x).Nonempty) with ⟨p, hp⟩ exact ⟨_, Set.mem_image_of_mem _ hp⟩ · rintro y ⟨p, ⟨x', hx'sim, _, rfl⟩, rfl⟩ dsimp [fiber_sum_vec] have h : ∑ k, ∑ i with proj i = k, x' i = ∑ i, x' i := Finset.sum_fiberwise Finset.univ proj x' rw [h, hx'sim.2]
For any block subset S, reachable partial block sums are bounded above by 1.
Because microstate probabilities are non-negative, each block fiber sum is non-negative by Finset.sum_nonneg. Therefore, the sum over any subset S is bounded above by the sum over all blocks by Finset.sum_le_univ_sum_of_nonneg, which sums to 1 by Finset.sum_fiberwise.
uses
Finset.sum_nonneg,Finset.sum_le_univ_sum_of_nonneg,Finset.sum_fiberwiseuse 1 rintro y ⟨q, hq, rfl⟩ rcases hq with ⟨x'', hx''sim, _, rfl⟩ dsimp [fiber_sum_vec] have hp_nonneg : ∀ k, 0 ≤ ∑ i with proj i = k, x'' i := fun k => Finset.sum_nonneg (fun i _ => hx''sim.1 i) have h_le_univ : ∑ k ∈ S, (∑ i with proj i = k, x'' i) ≤ ∑ k, (∑ i with proj i = k, x'' i) := Finset.sum_le_univ_sum_of_nonneg (fun k => hp_nonneg k) rw [Finset.sum_fiberwise Finset.univ proj x'', hx''sim.2] at h_le_univ exact h_le_univ
The sum of capacities of the two singleton blocks is at least 1.
The initial distribution x is reachable from itself via the identity transition matrix, so its fiber-sum vector p* is a reachable block population. Consequently, p*_0 ≤ capacity({0}) and p*_1 ≤ capacity({1}) by le_csSup. Since x is a probability vector, p*_0 + p*_1 = 1 by Finset.sum_fiberwise. Adding these inequalities gives 1 ≤ capacity({0}) + capacity({1}).
uses
le_csSup,op_737_two_level_submodular_capacity_bddAbove,Finset.sum_fiberwisehave hp_mem : fiber_sum_vec proj x ∈ thermally_reachable_block_populations proj γ x := by refine ⟨x, hx, ?_, rfl⟩ use fun i j => if i = j then 1 else 0 refine ⟨⟨fun i j => by dsimp; split_ifs <;> norm_num, fun j => by simp, fun i => by simp⟩, fun i => by simp⟩ have h0 : fiber_sum_vec proj x 0 ≤ block_population_capacity proj γ x {0} := by dsimp [block_population_capacity] have h_mem : fiber_sum_vec proj x 0 ∈ (fun p => ∑ k ∈ ({0} : Finset (Fin 2)), p k) '' thermally_reachable_block_populations proj γ x := by exact ⟨fiber_sum_vec proj x, hp_mem, by simp⟩ exact le_csSup (op_737_two_level_submodular_capacity_bddAbove proj γ x {0}) h_mem have h1 : fiber_sum_vec proj x 1 ≤ block_population_capacity proj γ x {1} := by dsimp [block_population_capacity] have h_mem : fiber_sum_vec proj x 1 ∈ (fun p => ∑ k ∈ ({1} : Finset (Fin 2)), p k) '' thermally_reachable_block_populations proj γ x := by exact ⟨fiber_sum_vec proj x, hp_mem, by simp⟩ exact le_csSup (op_737_two_level_submodular_capacity_bddAbove proj γ x {1}) h_mem have h_sum : fiber_sum_vec proj x 0 + fiber_sum_vec proj x 1 = 1 := by have h_tot : ∑ k : Fin 2, fiber_sum_vec proj x k = 1 := by dsimp [fiber_sum_vec] rw [Finset.sum_fiberwise Finset.univ proj x, hx.2] have h_split : ∑ k : Fin 2, fiber_sum_vec proj x k = fiber_sum_vec proj x 0 + fiber_sum_vec proj x 1 := by have h_univ : (Finset.univ : Finset (Fin 2)) = {0, 1} := by decide rw [h_univ] simp linarith linarith
The block population capacity is submodular.
By op_737_two_level_submodular_fin2_of_le, submodularity on Fin 2 reduces to capacity(univ) + capacity(∅) ≤ capacity({0}) + capacity({1}). Substituting capacity(∅) = 0, capacity(univ) ≤ 1, and 1 ≤ capacity({0}) + capacity({1}) into linear arithmetic (linarith) completes the proof.
uses
op_737_two_level_submodular_fin2_of_le,op_737_two_level_submodular_capacity_empty,op_737_two_level_submodular_capacity_univ_le,op_737_two_level_submodular_capacity_two_sum_gehave _ := hn have _ := hsurj have _ := hγ_simplex have _ := hγ_pos have _ := hγ_block apply op_737_two_level_submodular_fin2_of_le have h_empty := op_737_two_level_submodular_capacity_empty proj γ x hx have h_univ := op_737_two_level_submodular_capacity_univ_le proj γ x hx have h_sum := op_737_two_level_submodular_capacity_two_sum_ge proj γ x hx linarith
subset_empty- A finite set is a subset of the empty set if and only if it is empty.
Set.mem_image- An element y is in the image f(s) if and only if y = f(x) for some x in s.
Set.mem_singleton_iff- An element belongs to a singleton set {b} if and only if it equals b.
csSup_singleton- The supremum of a singleton set {a} in a conditionally complete lattice is a.
csSup_le- If a non-empty set in a conditionally complete lattice is bounded above by a, its supremum is at most a.
Set.mem_image_of_mem- If an element x belongs to a set a, then f(x) belongs to the image f(a).
Finset.sum_fiberwise- Summing a function over a finite set by partitioning it into fibers of a projection equals the sum over the entire set.
Finset.sum_nonneg- The sum of non-negative elements over a finite set is non-negative.
Finset.sum_le_univ_sum_of_nonneg- The sum of non-negative terms over a subset is bounded by the sum over the full finite universe.
le_csSup- Any element of a set bounded from above is less than or equal to the supremum of the set.
op_737_two_level_submodular_capacity_bddAbove- For any subset of blocks S, the sums of block populations over S across all thermally reachable states are bounded above (by 1).
op_737_two_level_submodular_fin2_of_le- A real-valued function on subsets of a two-element universe is submodular if and only if v(univ) + v(∅) ≤ v({0}) + v({1}).
op_737_two_level_submodular_capacity_empty- The block population capacity of the empty set of blocks is 0.
op_737_two_level_submodular_capacity_univ_le- The block population capacity of the set of all blocks is at most 1.
op_737_two_level_submodular_capacity_two_sum_ge- The sum of the block population capacities of the two singleton blocks {0} and {1} is at least 1.
- The hypotheses that n > 2, that proj is surjective, that γ has strictly positive entries, and that γ is constant on the fibers of proj are preserved in the context (lines 114–118) but are not actually needed for the submodularity proof.
- Several finite set relationships on Fin 2 (such as exhaustions of subsets and singleton complements) are verified automatically via the decision procedure decide.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Finsetlemma op_737_two_level_submodular_fin2_of_le (v : Finset (Fin 2) → ℝ) (h_univ : v univ + v ∅ ≤ v {0} + v {1}) : is_submodular v := by intro S T j hST hj have hT : ∀ (T : Finset (Fin 2)) (j : Fin 2), j ∉ T → T = ∅ ∨ T = {0} ∨ T = {1} := by decide rcases hT T j hj with rfl | rfl | rfl · have hS : S = ∅ := subset_empty.mp hST subst hS linarith · have hj0 : ∀ j : Fin 2, j ∉ ({0} : Finset (Fin 2)) → j = 1 := by decide have hj' := hj0 j hj subst hj' have hS : ∀ (S : Finset (Fin 2)), S ⊆ {0} → S = ∅ ∨ S = {0} := by decide rcases hS S hST with rfl | rfl · have hu : (insert (1 : Fin 2) {0} : Finset (Fin 2)) = univ := by decide have h1 : (insert (1 : Fin 2) (∅ : Finset (Fin 2)) : Finset (Fin 2)) = {1} := by decide rw [hu, h1] linarith · linarith · have hj1 : ∀ j : Fin 2, j ∉ ({1} : Finset (Fin 2)) → j = 0 := by decide have hj' := hj1 j hj subst hj' have hS : ∀ (S : Finset (Fin 2)), S ⊆ {1} → S = ∅ ∨ S = {1} := by decide rcases hS S hST with rfl | rfl · have hu : (insert (0 : Fin 2) {1} : Finset (Fin 2)) = univ := by decide have h0 : (insert (0 : Fin 2) (∅ : Finset (Fin 2)) : Finset (Fin 2)) = {0} := by decide rw [hu, h0] linarith · linarithlemma op_737_two_level_submodular_capacity_empty {n m : ℕ} (proj : Fin n → Fin m) (γ x : Fin n → ℝ) (hx : x ∈ stdSimplex ℝ (Fin n)) : block_population_capacity proj γ x ∅ = 0 := by dsimp [block_population_capacity] have h_img : ((fun p => (0 : ℝ)) '' thermally_reachable_block_populations proj γ x) = {0} := by ext y simp only [Set.mem_image, Set.mem_singleton_iff] constructor · rintro ⟨p, hp, rfl⟩ rfl · rintro rfl have ⟨p, hp⟩ : (thermally_reachable_block_populations proj γ x).Nonempty := by use fiber_sum_vec proj x refine ⟨x, hx, ?_, rfl⟩ use fun i j => if i = j then 1 else 0 refine ⟨⟨fun i j => by dsimp; split_ifs <;> norm_num, fun j => by simp, fun i => by simp⟩, fun i => by simp⟩ exact ⟨p, hp, rfl⟩ rw [h_img, csSup_singleton]lemma op_737_two_level_submodular_capacity_univ_le {n m : ℕ} (proj : Fin n → Fin m) (γ x : Fin n → ℝ) (hx : x ∈ stdSimplex ℝ (Fin n)) : block_population_capacity proj γ x univ ≤ 1 := by dsimp [block_population_capacity] apply csSup_le · rcases (by use fiber_sum_vec proj x refine ⟨x, hx, ?_, rfl⟩ use fun i j => if i = j then 1 else 0 refine ⟨⟨fun i j => by dsimp; split_ifs <;> norm_num, fun j => by simp, fun i => by simp⟩, fun i => by simp⟩ : (thermally_reachable_block_populations proj γ x).Nonempty) with ⟨p, hp⟩ exact ⟨_, Set.mem_image_of_mem _ hp⟩ · rintro y ⟨p, ⟨x', hx'sim, _, rfl⟩, rfl⟩ dsimp [fiber_sum_vec] have h : ∑ k, ∑ i with proj i = k, x' i = ∑ i, x' i := Finset.sum_fiberwise Finset.univ proj x' rw [h, hx'sim.2]lemma op_737_two_level_submodular_capacity_bddAbove {n m : ℕ} (proj : Fin n → Fin m) (γ x : Fin n → ℝ) (S : Finset (Fin m)) : BddAbove ((fun p => ∑ k ∈ S, p k) '' thermally_reachable_block_populations proj γ x) := by use 1 rintro y ⟨q, hq, rfl⟩ rcases hq with ⟨x'', hx''sim, _, rfl⟩ dsimp [fiber_sum_vec] have hp_nonneg : ∀ k, 0 ≤ ∑ i with proj i = k, x'' i := fun k => Finset.sum_nonneg (fun i _ => hx''sim.1 i) have h_le_univ : ∑ k ∈ S, (∑ i with proj i = k, x'' i) ≤ ∑ k, (∑ i with proj i = k, x'' i) := Finset.sum_le_univ_sum_of_nonneg (fun k => hp_nonneg k) rw [Finset.sum_fiberwise Finset.univ proj x'', hx''sim.2] at h_le_univ exact h_le_univlemma op_737_two_level_submodular_capacity_two_sum_ge {n : ℕ} (proj : Fin n → Fin 2) (γ x : Fin n → ℝ) (hx : x ∈ stdSimplex ℝ (Fin n)) : 1 ≤ block_population_capacity proj γ x {0} + block_population_capacity proj γ x {1} := by have hp_mem : fiber_sum_vec proj x ∈ thermally_reachable_block_populations proj γ x := by refine ⟨x, hx, ?_, rfl⟩ use fun i j => if i = j then 1 else 0 refine ⟨⟨fun i j => by dsimp; split_ifs <;> norm_num, fun j => by simp, fun i => by simp⟩, fun i => by simp⟩ have h0 : fiber_sum_vec proj x 0 ≤ block_population_capacity proj γ x {0} := by dsimp [block_population_capacity] have h_mem : fiber_sum_vec proj x 0 ∈ (fun p => ∑ k ∈ ({0} : Finset (Fin 2)), p k) '' thermally_reachable_block_populations proj γ x := by exact ⟨fiber_sum_vec proj x, hp_mem, by simp⟩ exact le_csSup (op_737_two_level_submodular_capacity_bddAbove proj γ x {0}) h_mem have h1 : fiber_sum_vec proj x 1 ≤ block_population_capacity proj γ x {1} := by dsimp [block_population_capacity] have h_mem : fiber_sum_vec proj x 1 ∈ (fun p => ∑ k ∈ ({1} : Finset (Fin 2)), p k) '' thermally_reachable_block_populations proj γ x := by exact ⟨fiber_sum_vec proj x, hp_mem, by simp⟩ exact le_csSup (op_737_two_level_submodular_capacity_bddAbove proj γ x {1}) h_mem have h_sum : fiber_sum_vec proj x 0 + fiber_sum_vec proj x 1 = 1 := by have h_tot : ∑ k : Fin 2, fiber_sum_vec proj x k = 1 := by dsimp [fiber_sum_vec] rw [Finset.sum_fiberwise Finset.univ proj x, hx.2] have h_split : ∑ k : Fin 2, fiber_sum_vec proj x k = fiber_sum_vec proj x 0 + fiber_sum_vec proj x 1 := by have h_univ : (Finset.univ : Finset (Fin 2)) = {0, 1} := by decide rw [h_univ] simp linarith linarith/-- For a two-level degenerate system, the block population capacity is submodular. -/theorem op_737_two_level_submodular {n : ℕ} (hn : 2 < n) (proj : Fin n → Fin 2) (hsurj : Function.Surjective proj) (γ : Fin n → ℝ) (hγ_simplex : γ ∈ stdSimplex ℝ (Fin n)) (hγ_pos : ∀ i, 0 < γ i) (hγ_block : ∀ i j, proj i = proj j → γ i = γ j) (x : Fin n → ℝ) (hx : x ∈ stdSimplex ℝ (Fin n)) : is_submodular (block_population_capacity proj γ x) := by have _ := hn have _ := hsurj have _ := hγ_simplex have _ := hγ_pos have _ := hγ_block apply op_737_two_level_submodular_fin2_of_le have h_empty := op_737_two_level_submodular_capacity_empty proj γ x hx have h_univ := op_737_two_level_submodular_capacity_univ_le proj γ x hx have h_sum := op_737_two_level_submodular_capacity_two_sum_ge proj γ x hx linarith