AFTD Auto-Formalizing Theoretical Domains

trace_distance_lower_bound_subset

theoremverified

For any natural number n, vectors x, y, γ : Fin n → ℝ with y in stdSimplex ℝ (Fin n), subset S : Finset (Fin n), and vector x' in thermally_reachable_populations γ x, the population deficit (∑ i ∈ S, y i) - population_capacity γ x S is at most (1 / 2 : ℝ) * ∑ i : Fin n, |x' i - y i|.

Statement

theorem trace_distance_lower_bound_subset {n : ℕ}
    {x y γ : Fin n → ℝ} (hy : y ∈ stdSimplex ℝ (Fin n)) (S : Finset (Fin n))
    {x' : Fin n → ℝ} (hx' : x' ∈ thermally_reachable_populations γ x) :
    (∑ i ∈ S, y i) - population_capacity γ x S ≤ (1 / 2 : ℝ) * ∑ i : Fin n, |x' i - y i|
Source
arXiv:2610.35433, Eq. (51)
Verified
08 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 5
  • population_capacityGiven a Gibbs vector γ, an initial state x on Fin n, and a subset S of energy levels, the population capacity is the supremum over all…
  • thermally_reachable_populationsGiven a Gibbs vector γ and an initial distribution x on Fin n, the thermally reachable populations are the population vectors x' in 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 γ…
  • 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…
  • 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…

Read back from the Lean

For any natural number $n$, vectors $x, y, γ : Fin n → ℝ$, assuming $y$ is in the standard probability simplex stdSimplex ℝ (Fin n), for any subset $S ⊆ Fin n$, and for any vector $x' : Fin n → ℝ$ belonging to thermally_reachable_populations γ x: the sum $\sum_{i \in S} y_i$ minus the population capacity of $S$ (with respect to $γ$ and $x$) is less than or equal to half the $\ell_1$-distance between $x'$ and $y$, namely $(1/2) \sum_{i : Fin n} |x'_i - y_i|$.

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 that for any thermally reachable population x', the population deficit on S is bounded by half the ℓ₁ distance between x' and y. First, x' is shown to belong to the probability simplex, which implies its subset sum on S is at most the population capacity. Second, because both y and x' sum to 1, their difference sums to zero across the entire space; bounding the sum on S by the ℓ₁ norm on both S and Sᶜ shows that the subset difference is at most half the total ℓ₁ distance. Combining these two inequalities gives the deficit bound.

  1. The reachable population vector x' belongs to the standard simplex Δ(Fin n).

    By definition of thermally reachable populations, x' is the fiber sum under the identity map of a microscopic state z in the simplex. Because fiber summation under the identity projection degenerates to the identity map (x' k = z k), x' equals z and therefore lies in the standard simplex.

    lines 7–14

    uses Finset.sum_filter

      have hx'_sim : x' ∈ stdSimplex ℝ (Fin n) := by
        obtain ⟨z, hz, _, hxz⟩ := hx'
        have h : x' = z := by
          funext k
          rw [hxz]
          simp [fiber_sum_vec, Finset.sum_filter]
        rw [h]
        exact hz
  2. The subset sum ∑ i ∈ S, x' i is bounded above by the population capacity.

    The population capacity is defined as the supremum of subset sums ∑ k ∈ S, q k over all thermally reachable populations q. Since each such population q corresponds to a simplex vector z, its entries are non-negative and sum to 1, implying ∑ k ∈ S, q k ≤ ∑ k, q k = 1. Hence 1 is an upper bound on this set of subset sums. Because x' is thermally reachable, its subset sum belongs to this set and is thus bounded by the supremum via le_csSup.

    lines 16–30

    uses le_csSup, Finset.sum_filter, Finset.sum_le_univ_sum_of_nonneg, Set.mem_image_of_mem

      have hcap : ∑ i ∈ S, x' i ≤ population_capacity γ x S := by
        dsimp [population_capacity, block_population_capacity]
        apply le_csSup
        · refine ⟨1, ?_⟩
          rintro p ⟨q, hq, rfl⟩
          rcases hq with ⟨z, hz, _, hqz⟩
          have hzq : q = z := by
            funext k
            rw [hqz]
            simp [fiber_sum_vec, Finset.sum_filter]
          subst hzq
          calc ∑ i ∈ S, q i ≤ ∑ i, q i :=
                Finset.sum_le_univ_sum_of_nonneg (fun i => hz.1 i)
            _ = 1 := hz.2
        · exact Set.mem_image_of_mem _ hx'
  3. The subset difference ∑ i ∈ S, (y i - x' i) is at most half the ℓ₁ distance, (1 / 2) * ∑ i, |x' i - y i|.

    Because y and x' both lie in the simplex, their coordinates each sum to 1, so the total sum of their difference is zero: ∑ i, (y i - x' i) = 0. Splitting this sum into S and its complement Sᶜ shows that ∑ i ∈ Sᶜ, (y i - x' i) = -∑ i ∈ S, (y i - x' i). The sum over S is directly bounded by ∑ i ∈ S, |y i - x' i|, and it also equals ∑ i ∈ Sᶜ, -(y i - x' i) ≤ ∑ i ∈ Sᶜ, |y i - x' i|. Averaging these two upper bounds gives ∑ i ∈ S, (y i - x' i) ≤ (1 / 2) * ∑ i, |y i - x' i|. Rewriting |y i - x' i| as |x' i - y i| by symmetry yields the claim.

    lines 32–52

    uses Finset.sum_sub_distrib, sub_self, Finset.sum_add_sum_compl, Finset.sum_le_sum, le_abs_self, Finset.sum_neg_distrib, Finset.sum_congr, abs_neg, abs_sub_comm

      have hkey : ∑ i ∈ S, (y i - x' i) ≤ (1 / 2 : ℝ) * ∑ i : Fin n, |x' i - y i| := by
        have hmain : ∑ i ∈ S, (y i - x' i) ≤ (1 / 2 : ℝ) * ∑ i : Fin n, |y i - x' i| := by
          have hd : ∑ i, (y i - x' i) = 0 := by
            rw [Finset.sum_sub_distrib, hy.2, hx'_sim.2, sub_self]
          have hdecomp := Finset.sum_add_sum_compl S (fun i => y i - x' i)
          have hdabs := Finset.sum_add_sum_compl S (fun i => |y i - x' i|)
          have hSc : ∑ i ∈ Sᶜ, (y i - x' i) = -(∑ i ∈ S, (y i - x' i)) := by
            rw [hd] at hdecomp; linarith
          have h1 : ∑ i ∈ S, (y i - x' i) ≤ ∑ i ∈ S, |y i - x' i| :=
            Finset.sum_le_sum (fun i _ => le_abs_self _)
          have h2 : ∑ i ∈ S, (y i - x' i) ≤ ∑ i ∈ Sᶜ, |y i - x' i| := by
            have h3 : ∑ i ∈ Sᶜ, (-(y i - x' i)) ≤ ∑ i ∈ Sᶜ, |(-(y i - x' i))| :=
              Finset.sum_le_sum (fun i _ => le_abs_self _)
            rw [Finset.sum_neg_distrib, hSc] at h3
            have habs : ∑ i ∈ Sᶜ, |(-(y i - x' i))| = ∑ i ∈ Sᶜ, |y i - x' i| :=
              Finset.sum_congr rfl (fun i _ => by rw [abs_neg])
            linarith
          linarith
        have habs : ∑ i : Fin n, |y i - x' i| = ∑ i : Fin n, |x' i - y i| :=
          Finset.sum_congr rfl (fun i _ => abs_sub_comm _ _)
        linarith
  4. The deficit (∑ i ∈ S, y i) - population_capacity γ x S is at most (1 / 2) * ∑ i, |x' i - y i|.

    Distributing subtraction across the sum gives (∑ i ∈ S, y i) - ∑ i ∈ S, x' i = ∑ i ∈ S, (y i - x' i). Since ∑ i ∈ S, x' i is bounded above by the population capacity from Step 2, the deficit (∑ i ∈ S, y i) - population_capacity γ x S is at most ∑ i ∈ S, (y i - x' i). Combining this with the bound from Step 3 via linear arithmetic completes the proof.

    lines 53–55

    uses Finset.sum_sub_distrib

      have hdiff : (∑ i ∈ S, y i) - ∑ i ∈ S, x' i = ∑ i ∈ S, (y i - x' i) :=
        (Finset.sum_sub_distrib (s := S) (f := y) (g := x')).symm
      linarith
Finset.sum_filter
The sum of a function over elements of a finite set satisfying a predicate equals the sum over the entire set with terms not satisfying the predicate replaced by zero.
le_csSup
In a conditionally complete lattice, any element of a set that is bounded above is at most the supremum of the set.
Finset.sum_le_univ_sum_of_nonneg
For non-negative terms, the sum over any subset of a finite type is at most the sum over the entire type.
Set.mem_image_of_mem
If an element belongs to a set, its image under a function belongs to the image of that set.
Finset.sum_sub_distrib
The sum of differences over a finite set equals the difference of the sums.
sub_self
In an additive group, subtracting any element from itself gives zero.
Finset.sum_add_sum_compl
The sum of a function over a subset plus the sum over its complement equals the total sum over the entire finite type.
Finset.sum_le_sum
If one function is pointwise bounded by another on a finite set, its sum over that set is at most the sum of the other.
le_abs_self
Any element in an ordered additive group is less than or equal to its absolute value.
Finset.sum_neg_distrib
The sum of negated terms over a finite set equals the negation of the sum.
Finset.sum_congr
If two finite index sets are equal and two functions agree pointwise on that set, their sums are equal.
abs_neg
The absolute value of the negation of a number equals its absolute value.
abs_sub_comm
The absolute difference is symmetric: |a - b| = |b - a|.

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

/-- Every thermally reachable state has trace distance to y at least the capacity deficit y(S) - C_ρ(S). -/theorem trace_distance_lower_bound_subset {n : ℕ}    {x y γ : Fin n → ℝ} (hy : y ∈ stdSimplex ℝ (Fin n)) (S : Finset (Fin n))    {x' : Fin n → ℝ} (hx' : x' ∈ thermally_reachable_populations γ x) :    (∑ i ∈ S, y i) - population_capacity γ x S ≤ (1 / 2 : ℝ) * ∑ i : Fin n, |x' i - y i| := by  -- Step 1: any reachable population vector lies in the simplex  have hx'_sim : x' ∈ stdSimplex ℝ (Fin n) := by    obtain ⟨z, hz, _, hxz⟩ := hx'    have h : x' = z := by      funext k      rw [hxz]      simp [fiber_sum_vec, Finset.sum_filter]    rw [h]    exact hz  -- Step 2: the capacity is an upper bound for the reachable subset sums  have hcap : ∑ i ∈ S, x' i ≤ population_capacity γ x S := by    dsimp [population_capacity, block_population_capacity]    apply le_csSup    · refine ⟨1, ?_⟩      rintro p ⟨q, hq, rfl⟩      rcases hq with ⟨z, hz, _, hqz⟩      have hzq : q = z := by        funext k        rw [hqz]        simp [fiber_sum_vec, Finset.sum_filter]      subst hzq      calc ∑ i ∈ S, q i ≤ ∑ i, q i :=            Finset.sum_le_univ_sum_of_nonneg (fun i => hz.1 i)        _ = 1 := hz.2    · exact Set.mem_image_of_mem _ hx'  -- Step 3: for two probability vectors, a subset deficit is at most half the L1 distance  have hkey : ∑ i ∈ S, (y i - x' i) ≤ (1 / 2 : ℝ) * ∑ i : Fin n, |x' i - y i| := by    have hmain : ∑ i ∈ S, (y i - x' i) ≤ (1 / 2 : ℝ) * ∑ i : Fin n, |y i - x' i| := by      have hd : ∑ i, (y i - x' i) = 0 := by        rw [Finset.sum_sub_distrib, hy.2, hx'_sim.2, sub_self]      have hdecomp := Finset.sum_add_sum_compl S (fun i => y i - x' i)      have hdabs := Finset.sum_add_sum_compl S (fun i => |y i - x' i|)      have hSc : ∑ i ∈ Sᶜ, (y i - x' i) = -(∑ i ∈ S, (y i - x' i)) := by        rw [hd] at hdecomp; linarith      have h1 : ∑ i ∈ S, (y i - x' i) ≤ ∑ i ∈ S, |y i - x' i| :=        Finset.sum_le_sum (fun i _ => le_abs_self _)      have h2 : ∑ i ∈ S, (y i - x' i) ≤ ∑ i ∈ Sᶜ, |y i - x' i| := by        have h3 : ∑ i ∈ Sᶜ, (-(y i - x' i)) ≤ ∑ i ∈ Sᶜ, |(-(y i - x' i))| :=          Finset.sum_le_sum (fun i _ => le_abs_self _)        rw [Finset.sum_neg_distrib, hSc] at h3        have habs : ∑ i ∈ Sᶜ, |(-(y i - x' i))| = ∑ i ∈ Sᶜ, |y i - x' i| :=          Finset.sum_congr rfl (fun i _ => by rw [abs_neg])        linarith      linarith    have habs : ∑ i : Fin n, |y i - x' i| = ∑ i : Fin n, |x' i - y i| :=      Finset.sum_congr rfl (fun i _ => abs_sub_comm _ _)    linarith  have hdiff : (∑ i ∈ S, y i) - ∑ i ∈ S, x' i = ∑ i ∈ S, (y i - x' i) :=    (Finset.sum_sub_distrib (s := S) (f := y) (g := x')).symm  linarith
See it in the graphDiscuss this resultChallenge it