target_prefix_capacity_eq_population
For any natural number n, population vector y in stdSimplex ℝ (Fin n), Gibbs vector γ in stdSimplex ℝ (Fin n) with strictly positive entries (∀ i, 0 < γ i), permutation π of Fin n satisfying Antitone (fun i : Fin n => y (π i) / γ (π i)), and natural number k ≤ n, the population capacity population_capacity γ y (thermomajorization_prefix π k) equals the sum ∑ i ∈ thermomajorization_prefix π k, y i.
Statement
theorem target_prefix_capacity_eq_population {n : ℕ} {y γ : Fin n → ℝ} (hy : y ∈ stdSimplex ℝ (Fin n)) (hγ : γ ∈ stdSimplex ℝ (Fin n)) (hγ_pos : ∀ i, 0 < γ i) (π : Equiv.Perm (Fin n)) (hπ : Antitone (fun i : Fin n => y (π i) / γ (π i))) (k : ℕ) (hk : k ≤ n) : population_capacity γ y (thermomajorization_prefix π k) = ∑ i ∈ thermomajorization_prefix π k, y i
- Source
- arXiv:2610.35433, Eq. (6)
- Verified
- 08 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- 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…
- thermomajorization_prefixGiven a permutation π of Fin n and a natural number k, the k-th prefix set thermomajorization_prefix π k is the finite set (Finset (Fin…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - thermally_reachable_microA microstate distribution x' on n energy levels is thermally reachable from an initial distribution x with respect to the Gibbs vector γ…
- 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…
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - 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
Let $n$ be an arbitrary natural number, and let $y, \gamma : \text{Fin } n \to \mathbb{R}$ be vectors.
Assume:
1. $y$ lies in the standard simplex $\Delta^{n-1}$ (stdSimplex ℝ (Fin n)),
2. $\gamma$ lies in the standard simplex $\Delta^{n-1}$ (stdSimplex ℝ (Fin n)),
3. each entry of $\gamma$ is strictly positive ($\forall i \in \text{Fin } n,\ 0 < \gamma(i)$),
4. $\pi$ is a permutation of $\text{Fin } n$,
5. the ratio function $i \mapsto \frac{y(\pi(i))}{\gamma(\pi(i))}$ is antitone on $\text{Fin } n$ (i.e., non-increasing with respect to the standard order on $\text{Fin } n$), and
6. $k$ is a natural number with $k \le n$.
Then the population capacity with respect to reference distribution $\gamma$ and state $y$ of the prefix set $P = \pi(\{j \in \text{Fin } n \mid (j : \mathbb{N}) < k\})$ equals the sum of the entries of $y$ on that prefix set:
$$\text{population\_capacity}\ \gamma\ y\ P = \sum_{i \in P} 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 theorem states that for a target state y and Gibbs state γ, the population capacity on the thermomajorization prefix S of the first k states equals the target population ∑_{i ∈ S} y_i. The proof first establishes a continuous knapsack lemma: because the prefix contains the states with the highest thermoratios y_j / γ_j, any set of weights c_j ∈ [0, 1] matching the Gibbs content of S achieves at most the target population of S. Since any thermally reachable state is obtained via a Gibbs-stochastic matrix T, its prefix sum can be rewritten as ∑_j c_j y_j with c_j = ∑_{i ∈ S} T_ij, which satisfies the knapsack bounds, showing that the prefix sum of any reachable state is bounded above by ∑_{i ∈ S} y_i. Because y is reachable from itself via the identity matrix, this upper bound is achieved, and thus the supremum (the population capacity) is exactly ∑_{i ∈ S} y_i.
For d_j = c_j - 1_S(j), the inner product with γ is 0, and the inner product with y is ∑ c_j y_j - ∑_{j ∈ S} y_j.
We define the prefix set S = {π(0), ..., π(k-1)} and the difference vector d_j = c_j - 1_S(j). We show that summing the indicator of S against any vector recovers the sum over S. Distributing the sum over subtraction shows that ∑ d_j γ_j = ∑ c_j γ_j - ∑_{j ∈ S} γ_j, which vanishes by the hypothesis that c has the same γ-weight as S. Similarly, ∑ d_j y_j = ∑ c_j y_j - ∑_{j ∈ S} y_j.
uses
sub_selfclassical set S := thermomajorization_prefix π k with hSdef set d : Fin n → ℝ := fun j => c j - (if j ∈ S then (1:ℝ) else 0) with hddef have hmem : ∀ j : Fin n, j ∈ S ↔ ∃ i : Fin n, (i : ℕ) < k ∧ π i = j := by intro j; rw [hSdef] rw [thermomajorization_prefix, Finset.mem_map] simp only [Equiv.coe_toEmbedding, Finset.mem_filter, Finset.mem_univ, true_and] have hind : ∀ f : Fin n → ℝ, ∑ j, (if j ∈ S then (1:ℝ) else 0) * f j = ∑ j ∈ S, f j := by intro f have h1 : ∑ j, (if j ∈ S then (1:ℝ) else 0) * f j = ∑ j, (if j ∈ S then f j else 0) := by apply Finset.sum_congr rfl intro j _ split_ifs with h <;> simp rw [h1, ← Finset.sum_filter] congr 1 ext j simp have hdγ : ∑ j, d j * γ j = 0 := by have hsplit : ∑ j, d j * γ j = ∑ j, c j * γ j - ∑ j, (if j ∈ S then (1:ℝ) else 0) * γ j := by rw [← Finset.sum_sub_distrib] apply Finset.sum_congr rfl intro j _ rw [hddef] simp only ring rw [hsplit, hind γ, hsum, sub_self] have hdy : ∑ j, d j * y j = ∑ j, c j * y j - ∑ j ∈ S, y j := by have hsplit : ∑ j, d j * y j = ∑ j, c j * y j - ∑ j, (if j ∈ S then (1:ℝ) else 0) * y j := by rw [← Finset.sum_sub_distrib] apply Finset.sum_congr rfl intro j _ rw [hddef] simp only ring rw [hsplit, hind y]
When k = 0, the key inequality holds trivially since all c_j must be 0.
If k = 0, the prefix S is empty, so the target sum ∑ c_j γ_j is zero. Because each c_j ≥ 0 and γ_j > 0, every individual product c_j γ_j is non-negative and bounded above by the total sum 0, forcing each c_j = 0. Therefore both sides of the inequality are zero.
uses
Finset.single_le_sum,ne_of_gt,mul_eq_zero.mpby_cases hk0 : k = 0 · have hSe : S = ∅ := by rw [hSdef, hk0] ext j simp [thermomajorization_prefix] have hsum0 : ∑ j, c j * γ j = 0 := by rw [hsum, hSe]; simp have hcz : ∀ j, c j = 0 := by intro j have hle : c j * γ j ≤ ∑ i, c i * γ i := Finset.single_le_sum (f := fun i => c i * γ i) (fun i _ => mul_nonneg (hc0 i) (le_of_lt (hγ_pos i))) (Finset.mem_univ j) have hnonneg : 0 ≤ c j * γ j := mul_nonneg (hc0 j) (le_of_lt (hγ_pos j)) have hzero : c j * γ j = 0 := by linarith exact (mul_eq_zero.mp hzero).resolve_right (ne_of_gt (hγ_pos j)) simp [hcz, hSe]
When k > 0, the thermoratio y_j / γ_j is at least the threshold r* on S, and at most r* outside S.
Let m = k - 1, and define the threshold ratio r* = y(π(m)) / γ(π(m)). Since the permutation π sorts the thermoratios in descending order (antitone), any index j ∈ S corresponds to some i < k, so i ≤ m, which gives y_j / γ_j ≥ r*. Conversely, any j ∉ S corresponds to π⁻¹(j) ≥ k > m, so y_j / γ_j ≤ r*.
uses
Nat.pos_of_ne_zero,Fin.le_iff_val_le_val· have hk1 : 0 < k := Nat.pos_of_ne_zero hk0 have hmk : k - 1 < n := by omega set m : Fin n := ⟨k - 1, hmk⟩ with hmdef have hmval : (m : ℕ) = k - 1 := rfl set rstar : ℝ := y (π m) / γ (π m) with hrstardef have hFj_ge : ∀ j : Fin n, j ∈ S → rstar ≤ y j / γ j := by intro j hj obtain ⟨i, hi, rfl⟩ := (hmem j).mp hj have hle : i ≤ m := by simp only [Fin.le_iff_val_le_val, hmval]; omega have hh := hπ hle simpa [hrstardef] using hh have hFj_le : ∀ j : Fin n, j ∉ S → y j / γ j ≤ rstar := by intro j hj have hge : ¬ ((π.symm j : Fin n) : ℕ) < k := by intro hlt exact hj ((hmem j).mpr ⟨π.symm j, hlt, by simp⟩) have hle : m ≤ π.symm j := by simp only [Fin.le_iff_val_le_val, hmval]; omega have hh := hπ hle simpa [hrstardef] using hh
The sum ∑ c_j y_j is at most ∑_{j ∈ S} y_j.
For each j ∈ S, d_j ≤ 0 because c_j ≤ 1, while y_j - r* γ_j ≥ 0; for j ∉ S, d_j ≥ 0 because c_j ≥ 0, while y_j - r* γ_j ≤ 0. In both cases, d_j (y_j - r* γ_j) ≤ 0, so d_j y_j ≤ d_j (r* γ_j). Summing over all j gives ∑ d_j y_j ≤ r* ∑ d_j γ_j = 0. Since ∑ d_j y_j = ∑ c_j y_j - ∑_{j ∈ S} y_j, this immediately implies ∑ c_j y_j ≤ ∑_{j ∈ S} y_j.
uses
mul_le_mul_of_nonneg_right,div_mul_cancel₀,mul_nonpos_of_nonpos_of_nonneg,mul_nonpos_of_nonneg_of_nonpos,Finset.sum_le_sum,Finset.mul_sumhave hpoint : ∀ j, d j * y j ≤ d j * (rstar * γ j) := by intro j by_cases hj : j ∈ S · have hdle : d j ≤ 0 := by have : d j = c j - 1 := by rw [hddef]; simp [hj] rw [this]; linarith [hc1 j] have hγj := hγ_pos j have h1 : rstar * γ j ≤ (y j / γ j) * γ j := mul_le_mul_of_nonneg_right (hFj_ge j hj) (le_of_lt hγj) have h2 : (y j / γ j) * γ j = y j := div_mul_cancel₀ _ (ne_of_gt hγj) have hnn : 0 ≤ y j - rstar * γ j := by linarith have h3 := mul_nonpos_of_nonpos_of_nonneg hdle hnn nlinarith [h3] · have hdge : 0 ≤ d j := by have : d j = c j := by rw [hddef]; simp [hj] rw [this]; exact hc0 j have hγj := hγ_pos j have h1 : (y j / γ j) * γ j ≤ rstar * γ j := mul_le_mul_of_nonneg_right (hFj_le j hj) (le_of_lt hγj) have h2 : (y j / γ j) * γ j = y j := div_mul_cancel₀ _ (ne_of_gt hγj) have hnn : y j - rstar * γ j ≤ 0 := by linarith have h3 := mul_nonpos_of_nonneg_of_nonpos hdge hnn nlinarith [h3] have hbound : ∑ j, d j * y j ≤ 0 := by calc ∑ j, d j * y j ≤ ∑ j, d j * (rstar * γ j) := Finset.sum_le_sum (fun j _ => hpoint j) _ = rstar * ∑ j, d j * γ j := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro j _ ring _ = 0 := by rw [hdγ]; ring linarith
The vector y is thermally reachable from itself, so ∑_{i ∈ S} y_i belongs to the set of reachable block population sums.
We verify that y is thermally reachable from y using the identity matrix T_ij = 1 if i = j else 0. The identity matrix is non-negative, column-stochastic, preserves γ (T γ = γ), and satisfies T y = y. Under the identity block projection, fiber sums collapse to the entries themselves, showing y is reachable and hence ∑_{i ∈ S} y_i lies in the set A of prefix sums of reachable populations.
uses
Finset.sum_ite_eq',Finset.sum_ite_eqclassical have _ := hγ set S := thermomajorization_prefix π k with hSdef have hself : y ∈ thermally_reachable_block_populations (id : Fin n → Fin n) γ y := by refine ⟨y, hy, ?_, ?_⟩ · exact ⟨fun i j => if i = j then (1:ℝ) else 0, by refine ⟨?_, ?_, ?_⟩ · intro i j; dsimp only; split_ifs <;> norm_num · intro j; rw [Finset.sum_ite_eq']; simp · intro i have h1 : ∑ j, (if i = j then (1:ℝ) else 0) * γ j = ∑ j, (if i = j then γ j else 0) := by apply Finset.sum_congr rfl intro j _ split_ifs <;> simp rw [h1, Finset.sum_ite_eq]; simp, by intro i have h1 : ∑ j, (if i = j then (1:ℝ) else 0) * y j = ∑ j, (if i = j then y j else 0) := by apply Finset.sum_congr rfl intro j _ split_ifs <;> simp rw [h1, Finset.sum_ite_eq]; simp⟩ · funext j unfold fiber_sum_vec rw [Finset.sum_filter] simp only [id] rw [Finset.sum_ite_eq'] simp set A := (fun p : Fin n → ℝ => ∑ i ∈ S, p i) '' thermally_reachable_block_populations (id : Fin n → Fin n) γ y with hAdef have hmem : ∑ i ∈ S, y i ∈ A := ⟨y, hself, rfl⟩
Every reachable block population sum on S is at most ∑_{i ∈ S} y_i.
Any reachable population p satisfies p_i = x'_i = ∑_j T_ij y_j for a Gibbs-stochastic matrix T. Summing over i ∈ S and exchanging the order of summation gives ∑_{i ∈ S} x'_i = ∑_j c_j y_j, where c_j = ∑_{i ∈ S} T_ij. Since T is non-negative and column-stochastic, 0 ≤ c_j ≤ 1. Furthermore, since T preserves γ, ∑_j c_j γ_j = ∑_{i ∈ S} γ_i. By the key lemma, ∑_j c_j y_j ≤ ∑_{i ∈ S} y_i, so every element of A is bounded above by ∑_{i ∈ S} y_i.
uses
Finset.sum_ite_eq',target_prefix_capacity_eq_population_keyhave hupper : ∀ a ∈ A, a ≤ ∑ i ∈ S, y i := by rintro a ⟨p, hp, rfl⟩ obtain ⟨x', hx', htr, hp_eq⟩ := hp subst hp_eq obtain ⟨T, hT, hTx⟩ := htr have hfib : ∀ i : Fin n, fiber_sum_vec (id : Fin n → Fin n) x' i = x' i := by intro i unfold fiber_sum_vec rw [Finset.sum_filter] simp only [id] rw [Finset.sum_ite_eq'] simp simp only [hfib] have hrewrite : ∑ i ∈ S, x' i = ∑ j, (∑ i ∈ S, T i j) * y j := by have step1 : ∑ i ∈ S, x' i = ∑ i ∈ S, ∑ j, T i j * y j := by apply Finset.sum_congr rfl intro i _ exact hTx i have step2 : ∑ i ∈ S, ∑ j, T i j * y j = ∑ j, ∑ i ∈ S, T i j * y j := Finset.sum_comm have step3 : ∑ j, ∑ i ∈ S, T i j * y j = ∑ j, (∑ i ∈ S, T i j) * y j := by apply Finset.sum_congr rfl intro j _ rw [Finset.sum_mul] rw [step1, step2, step3] rw [hrewrite] have hc0 : ∀ j, 0 ≤ ∑ i ∈ S, T i j := fun j => Finset.sum_nonneg (fun i _ => hT.1 i j) have hc1 : ∀ j, ∑ i ∈ S, T i j ≤ 1 := by intro j have hle : ∑ i ∈ S, T i j ≤ ∑ i, T i j := Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ S) (fun i _ _ => hT.1 i j) rw [hT.2.1 j] at hle exact hle have hsumc : ∑ j, (∑ i ∈ S, T i j) * γ j = ∑ j ∈ S, γ j := by have step1 : ∑ j, (∑ i ∈ S, T i j) * γ j = ∑ j, ∑ i ∈ S, T i j * γ j := by apply Finset.sum_congr rfl intro j _ rw [Finset.sum_mul] have step2 : ∑ j, ∑ i ∈ S, T i j * γ j = ∑ i ∈ S, ∑ j, T i j * γ j := Finset.sum_comm have step3 : ∑ i ∈ S, ∑ j, T i j * γ j = ∑ i ∈ S, γ i := by apply Finset.sum_congr rfl intro i _ exact hT.2.2 i rw [step1, step2, step3] exact target_prefix_capacity_eq_population_key hγ_pos π hπ k hk hc0 hc1 hsumc
The population capacity on the prefix S equals ∑_{i ∈ S} y_i.
The population capacity is defined as the supremum of A. Because A is bounded above by ∑_{i ∈ S} y_i and contains ∑_{i ∈ S} y_i, the supremum must equal this maximum value, which establishes the theorem by anti-symmetry.
uses
le_csSup,csSup_le,le_antisymmhave hbdd : BddAbove A := ⟨_, hupper⟩ have h1 : ∑ i ∈ S, y i ≤ sSup A := le_csSup hbdd hmem have h2 : sSup A ≤ ∑ i ∈ S, y i := csSup_le ⟨_, hmem⟩ hupper rw [population_capacity, block_population_capacity, ← hAdef] exact le_antisymm h2 h1
sub_self- Subtracting a number from itself yields zero.
Finset.single_le_sum- A term in a sum of non-negative elements is at most the total sum.
ne_of_gt- A strictly positive element is non-zero.
mul_eq_zero.mp- If the product of two real numbers is zero, at least one of them is zero.
Nat.pos_of_ne_zero- A non-zero natural number is strictly positive.
Fin.le_iff_val_le_val- The inequality between two elements of Fin n is equivalent to the inequality between their underlying natural values.
mul_le_mul_of_nonneg_right- Multiplying an inequality on the right by a non-negative number preserves the inequality.
div_mul_cancel₀- Multiplying a non-zero quotient by its denominator recovers the numerator.
mul_nonpos_of_nonpos_of_nonneg- The product of a non-positive number and a non-negative number is non-positive.
mul_nonpos_of_nonneg_of_nonpos- The product of a non-negative number and a non-positive number is non-positive.
Finset.sum_le_sum- If f i ≤ g i for all i in a finite set, then the sum of f is at most the sum of g.
Finset.mul_sum- A constant factor distributes over a finite sum.
Finset.sum_ite_eq'- The sum of an indicator function matching a single target point equals the value at that point if present, and 0 otherwise.
Finset.sum_ite_eq- The sum of an indicator function matching a single point equals the value at that point if present, and 0 otherwise.
target_prefix_capacity_eq_population_key- For a family of weights bounded between 0 and 1 having the same total Gibbs weight as the prefix, the weighted target sum is bounded by the prefix target sum.
le_csSup- An element of a set bounded above is at most the supremum of the set.
csSup_le- If every element of a non-empty set is bounded above by a constant, the supremum of the set is at most that constant.
le_antisymm- If a ≤ b and b ≤ a, then a = b.
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.
private lemma target_prefix_capacity_eq_population_key {n : ℕ} {y γ : Fin n → ℝ} (hγ_pos : ∀ i, 0 < γ i) (π : Equiv.Perm (Fin n)) (hπ : Antitone (fun i : Fin n => y (π i) / γ (π i))) (k : ℕ) (hk : k ≤ n) {c : Fin n → ℝ} (hc0 : ∀ j, 0 ≤ c j) (hc1 : ∀ j, c j ≤ 1) (hsum : ∑ j, c j * γ j = ∑ j ∈ thermomajorization_prefix π k, γ j) : ∑ j, c j * y j ≤ ∑ j ∈ thermomajorization_prefix π k, y j := by classical set S := thermomajorization_prefix π k with hSdef set d : Fin n → ℝ := fun j => c j - (if j ∈ S then (1:ℝ) else 0) with hddef have hmem : ∀ j : Fin n, j ∈ S ↔ ∃ i : Fin n, (i : ℕ) < k ∧ π i = j := by intro j; rw [hSdef] rw [thermomajorization_prefix, Finset.mem_map] simp only [Equiv.coe_toEmbedding, Finset.mem_filter, Finset.mem_univ, true_and] have hind : ∀ f : Fin n → ℝ, ∑ j, (if j ∈ S then (1:ℝ) else 0) * f j = ∑ j ∈ S, f j := by intro f have h1 : ∑ j, (if j ∈ S then (1:ℝ) else 0) * f j = ∑ j, (if j ∈ S then f j else 0) := by apply Finset.sum_congr rfl intro j _ split_ifs with h <;> simp rw [h1, ← Finset.sum_filter] congr 1 ext j simp have hdγ : ∑ j, d j * γ j = 0 := by have hsplit : ∑ j, d j * γ j = ∑ j, c j * γ j - ∑ j, (if j ∈ S then (1:ℝ) else 0) * γ j := by rw [← Finset.sum_sub_distrib] apply Finset.sum_congr rfl intro j _ rw [hddef] simp only ring rw [hsplit, hind γ, hsum, sub_self] have hdy : ∑ j, d j * y j = ∑ j, c j * y j - ∑ j ∈ S, y j := by have hsplit : ∑ j, d j * y j = ∑ j, c j * y j - ∑ j, (if j ∈ S then (1:ℝ) else 0) * y j := by rw [← Finset.sum_sub_distrib] apply Finset.sum_congr rfl intro j _ rw [hddef] simp only ring rw [hsplit, hind y] by_cases hk0 : k = 0 · have hSe : S = ∅ := by rw [hSdef, hk0] ext j simp [thermomajorization_prefix] have hsum0 : ∑ j, c j * γ j = 0 := by rw [hsum, hSe]; simp have hcz : ∀ j, c j = 0 := by intro j have hle : c j * γ j ≤ ∑ i, c i * γ i := Finset.single_le_sum (f := fun i => c i * γ i) (fun i _ => mul_nonneg (hc0 i) (le_of_lt (hγ_pos i))) (Finset.mem_univ j) have hnonneg : 0 ≤ c j * γ j := mul_nonneg (hc0 j) (le_of_lt (hγ_pos j)) have hzero : c j * γ j = 0 := by linarith exact (mul_eq_zero.mp hzero).resolve_right (ne_of_gt (hγ_pos j)) simp [hcz, hSe] · have hk1 : 0 < k := Nat.pos_of_ne_zero hk0 have hmk : k - 1 < n := by omega set m : Fin n := ⟨k - 1, hmk⟩ with hmdef have hmval : (m : ℕ) = k - 1 := rfl set rstar : ℝ := y (π m) / γ (π m) with hrstardef have hFj_ge : ∀ j : Fin n, j ∈ S → rstar ≤ y j / γ j := by intro j hj obtain ⟨i, hi, rfl⟩ := (hmem j).mp hj have hle : i ≤ m := by simp only [Fin.le_iff_val_le_val, hmval]; omega have hh := hπ hle simpa [hrstardef] using hh have hFj_le : ∀ j : Fin n, j ∉ S → y j / γ j ≤ rstar := by intro j hj have hge : ¬ ((π.symm j : Fin n) : ℕ) < k := by intro hlt exact hj ((hmem j).mpr ⟨π.symm j, hlt, by simp⟩) have hle : m ≤ π.symm j := by simp only [Fin.le_iff_val_le_val, hmval]; omega have hh := hπ hle simpa [hrstardef] using hh have hpoint : ∀ j, d j * y j ≤ d j * (rstar * γ j) := by intro j by_cases hj : j ∈ S · have hdle : d j ≤ 0 := by have : d j = c j - 1 := by rw [hddef]; simp [hj] rw [this]; linarith [hc1 j] have hγj := hγ_pos j have h1 : rstar * γ j ≤ (y j / γ j) * γ j := mul_le_mul_of_nonneg_right (hFj_ge j hj) (le_of_lt hγj) have h2 : (y j / γ j) * γ j = y j := div_mul_cancel₀ _ (ne_of_gt hγj) have hnn : 0 ≤ y j - rstar * γ j := by linarith have h3 := mul_nonpos_of_nonpos_of_nonneg hdle hnn nlinarith [h3] · have hdge : 0 ≤ d j := by have : d j = c j := by rw [hddef]; simp [hj] rw [this]; exact hc0 j have hγj := hγ_pos j have h1 : (y j / γ j) * γ j ≤ rstar * γ j := mul_le_mul_of_nonneg_right (hFj_le j hj) (le_of_lt hγj) have h2 : (y j / γ j) * γ j = y j := div_mul_cancel₀ _ (ne_of_gt hγj) have hnn : y j - rstar * γ j ≤ 0 := by linarith have h3 := mul_nonpos_of_nonneg_of_nonpos hdge hnn nlinarith [h3] have hbound : ∑ j, d j * y j ≤ 0 := by calc ∑ j, d j * y j ≤ ∑ j, d j * (rstar * γ j) := Finset.sum_le_sum (fun j _ => hpoint j) _ = rstar * ∑ j, d j * γ j := by rw [Finset.mul_sum] apply Finset.sum_congr rfl intro j _ ring _ = 0 := by rw [hdγ]; ring linarith/-- The target state saturates its own population capacity on all thermomajorization prefix sets. -/theorem target_prefix_capacity_eq_population {n : ℕ} {y γ : Fin n → ℝ} (hy : y ∈ stdSimplex ℝ (Fin n)) (hγ : γ ∈ stdSimplex ℝ (Fin n)) (hγ_pos : ∀ i, 0 < γ i) (π : Equiv.Perm (Fin n)) (hπ : Antitone (fun i : Fin n => y (π i) / γ (π i))) (k : ℕ) (hk : k ≤ n) : population_capacity γ y (thermomajorization_prefix π k) = ∑ i ∈ thermomajorization_prefix π k, y i := by classical have _ := hγ set S := thermomajorization_prefix π k with hSdef have hself : y ∈ thermally_reachable_block_populations (id : Fin n → Fin n) γ y := by refine ⟨y, hy, ?_, ?_⟩ · exact ⟨fun i j => if i = j then (1:ℝ) else 0, by refine ⟨?_, ?_, ?_⟩ · intro i j; dsimp only; split_ifs <;> norm_num · intro j; rw [Finset.sum_ite_eq']; simp · intro i have h1 : ∑ j, (if i = j then (1:ℝ) else 0) * γ j = ∑ j, (if i = j then γ j else 0) := by apply Finset.sum_congr rfl intro j _ split_ifs <;> simp rw [h1, Finset.sum_ite_eq]; simp, by intro i have h1 : ∑ j, (if i = j then (1:ℝ) else 0) * y j = ∑ j, (if i = j then y j else 0) := by apply Finset.sum_congr rfl intro j _ split_ifs <;> simp rw [h1, Finset.sum_ite_eq]; simp⟩ · funext j unfold fiber_sum_vec rw [Finset.sum_filter] simp only [id] rw [Finset.sum_ite_eq'] simp set A := (fun p : Fin n → ℝ => ∑ i ∈ S, p i) '' thermally_reachable_block_populations (id : Fin n → Fin n) γ y with hAdef have hmem : ∑ i ∈ S, y i ∈ A := ⟨y, hself, rfl⟩ have hupper : ∀ a ∈ A, a ≤ ∑ i ∈ S, y i := by rintro a ⟨p, hp, rfl⟩ obtain ⟨x', hx', htr, hp_eq⟩ := hp subst hp_eq obtain ⟨T, hT, hTx⟩ := htr have hfib : ∀ i : Fin n, fiber_sum_vec (id : Fin n → Fin n) x' i = x' i := by intro i unfold fiber_sum_vec rw [Finset.sum_filter] simp only [id] rw [Finset.sum_ite_eq'] simp simp only [hfib] have hrewrite : ∑ i ∈ S, x' i = ∑ j, (∑ i ∈ S, T i j) * y j := by have step1 : ∑ i ∈ S, x' i = ∑ i ∈ S, ∑ j, T i j * y j := by apply Finset.sum_congr rfl intro i _ exact hTx i have step2 : ∑ i ∈ S, ∑ j, T i j * y j = ∑ j, ∑ i ∈ S, T i j * y j := Finset.sum_comm have step3 : ∑ j, ∑ i ∈ S, T i j * y j = ∑ j, (∑ i ∈ S, T i j) * y j := by apply Finset.sum_congr rfl intro j _ rw [Finset.sum_mul] rw [step1, step2, step3] rw [hrewrite] have hc0 : ∀ j, 0 ≤ ∑ i ∈ S, T i j := fun j => Finset.sum_nonneg (fun i _ => hT.1 i j) have hc1 : ∀ j, ∑ i ∈ S, T i j ≤ 1 := by intro j have hle : ∑ i ∈ S, T i j ≤ ∑ i, T i j := Finset.sum_le_sum_of_subset_of_nonneg (Finset.subset_univ S) (fun i _ _ => hT.1 i j) rw [hT.2.1 j] at hle exact hle have hsumc : ∑ j, (∑ i ∈ S, T i j) * γ j = ∑ j ∈ S, γ j := by have step1 : ∑ j, (∑ i ∈ S, T i j) * γ j = ∑ j, ∑ i ∈ S, T i j * γ j := by apply Finset.sum_congr rfl intro j _ rw [Finset.sum_mul] have step2 : ∑ j, ∑ i ∈ S, T i j * γ j = ∑ i ∈ S, ∑ j, T i j * γ j := Finset.sum_comm have step3 : ∑ i ∈ S, ∑ j, T i j * γ j = ∑ i ∈ S, γ i := by apply Finset.sum_congr rfl intro i _ exact hT.2.2 i rw [step1, step2, step3] exact target_prefix_capacity_eq_population_key hγ_pos π hπ k hk hc0 hc1 hsumc have hbdd : BddAbove A := ⟨_, hupper⟩ have h1 : ∑ i ∈ S, y i ≤ sSup A := le_csSup hbdd hmem have h2 : sSup A ≤ ∑ i ∈ S, y i := csSup_le ⟨_, hmem⟩ hupper rw [population_capacity, block_population_capacity, ← hAdef] exact le_antisymm h2 h1