AFTD Auto-Formalizing Theoretical Domains

op_737_two_level_submodular

theoremverified

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.

  1. 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}.

    lines 6–9

      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
  2. 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.

    lines 10–12

    uses subset_empty

      · have hS : S = ∅ := subset_empty.mp hST
        subst hS
        linarith
  3. 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.

    lines 13–22

      · 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
  4. 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.

    lines 23–32

      · 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
  5. 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.

    lines 37–51

    uses Set.mem_image, Set.mem_singleton_iff, csSup_singleton

      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]
  6. 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.

    lines 56–68

    uses csSup_le, Set.mem_image_of_mem, Finset.sum_fiberwise

      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]
  7. 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.

    lines 73–82

    uses Finset.sum_nonneg, Finset.sum_le_univ_sum_of_nonneg, Finset.sum_fiberwise

      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_univ
  8. 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}).

    lines 87–110

    uses le_csSup, op_737_two_level_submodular_capacity_bddAbove, Finset.sum_fiberwise

      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
  9. 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.

    lines 114–123

    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_ge

      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
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.

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

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
See it in the graphDiscuss this resultChallenge it