trace_distance_lower_bound_subset
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.
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.
uses
Finset.sum_filterhave 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
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.
uses
le_csSup,Finset.sum_filter,Finset.sum_le_univ_sum_of_nonneg,Set.mem_image_of_memhave 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'
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.
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_commhave 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
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.
uses
Finset.sum_sub_distribhave 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
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.
/-- 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