AFTD Auto-Formalizing Theoretical Domains

thermomajorization_pointwise_missed_error_ge_gap_error

theoremverified

For any dimension n ≥ 2, probe set F ⊆ {1,...,n-1}, and unprobed rank j ∈ {1,...,n-1} \ F, the pointwise missed error thermomajorization_pointwise_missed_error n F j is bounded below by thermomajorization_probe_gap_error a b j, where a = max({0} ∪ {k ∈ F : k < j}) and b = min({n} ∪ {k ∈ F : k > j}).

Statement

theorem thermomajorization_pointwise_missed_error_ge_gap_error
    (n : ℕ) (hn : 2 ≤ n) (F : Finset ℕ) (hF : F ⊆ Finset.Ioo 0 n)
    (j : ℕ) (hj : j ∈ Finset.Ioo 0 n \ F) :
    let a := (insert 0 (F.filter (· < j))).max' (Finset.insert_nonempty 0 _)
    let b := (insert n (F.filter (j < ·))).min' (Finset.insert_nonempty n _)
    thermomajorization_probe_gap_error a b j ≤
      thermomajorization_pointwise_missed_error n F j
Source
arXiv:2610.35433, Population capacity and the geometry of thermomajorization
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 6
  • thermomajorization_pointwise_missed_errorFor dimension n : ℕ, probe set F : Finset ℕ, and rank j : ℕ, the pointwise missed error thermomajorization_pointwise_missed_error n F j is…
  • thermomajorization_probe_gap_errorFor natural numbers a, b, and j, the thermomajorization probe gap error thermomajorization_probe_gap_error a b j is defined as ((j - a :…
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
  • thermomajorization_probe_errorFor population vectors x, y : Fin n → ℝ and a finite set of probe ranks F : Finset ℕ, the detected conversion error…
  • thermomajorization_diffFor population vectors x and y in ℝⁿ and an index j : ℕ, thermomajorization_diff x y j is the prefix difference ∑_{i < j} (y i - x i)…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
Used by 1

Read back from the Lean

For any natural number $n \ge 2$, any subset $F \subseteq \{1, \dots, n-1\}$ (represented as Finset.Ioo 0 n), and any natural number $j \in \{1, \dots, n-1\} \setminus F$: Let $a$ be the maximum of $\{0\} \cup \{k \in F \mid k < j\}$, and let $b$ be the minimum of $\{n\} \cup \{k \in F \mid j < k\}$. Then the probe gap error $$\frac{(j - a)(b - j)}{j(b - a)}$$ is less than or equal to the pointwise missed error $\text{thermomajorization\_pointwise\_missed\_error}(n, F, j)$, which is the supremum over all pairs of antitone vectors $x, y$ in the standard simplex $\Delta(\operatorname{Fin} n)$ of the difference between $\sum_{i < j} (y_i - x_i)$ and the probe error $\max\left(\{0\} \cup \left\{\sum_{i < k} (y_i - x_i) : k \in F\right\}\right)$.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

theorem thermomajorization_pointwise_missed_error_ge_gap_error_card_fin_filter_lt (n j : ℕ) (hj : j ≤ n) :
    (Finset.filter (fun (i : Fin n) => (i : ℕ) < j) Finset.univ).card = j := by
  obtain hj_lt | rfl := lt_or_eq_of_le hj
  · have h_set : Finset.filter (fun (i : Fin n) => (i : ℕ) < j) Finset.univ = Finset.Iio ⟨j, hj_lt⟩ := by
      ext ⟨i, hi⟩
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, Finset.mem_Iio, Fin.lt_def]
    rw [h_set, Fin.card_Iio]
  · have h_set : Finset.filter (fun (i : Fin j) => (i : ℕ) < j) Finset.univ = Finset.univ := by
      ext ⟨i, hi⟩
      simp only [Finset.mem_filter, Finset.mem_univ, true_and, hi]
    rw [h_set, Finset.card_univ, Fintype.card_fin]

theorem thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter (n k c : ℕ) (hc : c ≤ n) (val : ℝ) :
    (Finset.filter (fun (i : Fin n) => (i : ℕ) < k) Finset.univ).sum
      (fun i => if (i : ℕ) < c then val else 0) = ((min k c : ℕ) : ℝ) * val := by
  have h_eq : (Finset.filter (fun (i : Fin n) => (i : ℕ) < k) Finset.univ).sum
      (fun i => if (i : ℕ) < c then val else 0) =
      ∑ i : Fin n, (if (i : ℕ) < min k c then val else 0) := by
    rw [Finset.sum_filter]
    have : ∀ i : Fin n, (if (i : ℕ) < k then if (i : ℕ) < c then val else 0 else 0) =
        (if (i : ℕ) < min k c then val else 0) := by
      intro i
      by_cases h1 : (i : ℕ) < k <;> by_cases h2 : (i : ℕ) < c <;> simp [h1, h2]
    simp_rw [this]
  rw [h_eq]
  rw [Finset.sum_ite, Finset.sum_const_zero, add_zero, Finset.sum_const, nsmul_eq_mul]
  have h_card := thermomajorization_pointwise_missed_error_ge_gap_error_card_fin_filter_lt n (min k c) ((min_le_right k c).trans hc)
  rw [h_card]

theorem thermomajorization_pointwise_missed_error_ge_gap_error_antitone_indicator (n c : ℕ) (val : ℝ) (hval : 0 ≤ val) :
    Antitone (fun (i : Fin n) => if (i : ℕ) < c then val else 0) := by
  intro i₁ i₂ hle
  by_cases h2 : (i₂ : ℕ) < c
  · have h1 : (i₁ : ℕ) < c := lt_of_le_of_lt hle h2
    simp [h1, h2]
  · simp [h2]
    split_ifs
    · exact hval
    · rfl

theorem thermomajorization_pointwise_missed_error_ge_gap_error_diff_sub_probe_le_one (n : ℕ) (F : Finset ℕ) (j : ℕ)
    (x y : Fin n → ℝ) (hx : x ∈ stdSimplex ℝ (Fin n)) (hy : y ∈ stdSimplex ℝ (Fin n)) :
    thermomajorization_diff x y j - thermomajorization_probe_error n F x y ≤ 1 := by
  have h_diff : thermomajorization_diff x y j ≤ 1 := by
    unfold thermomajorization_diff
    have h1 : (Finset.filter (fun (i : Fin n) => (i.val < j)) Finset.univ).sum (fun i => y i - x i) ≤
              (Finset.filter (fun (i : Fin n) => (i.val < j)) Finset.univ).sum (fun i => y i) := by
      apply Finset.sum_le_sum
      intro i _
      have : 0 ≤ x i := hx.1 i
      linarith
    have h2 : (Finset.filter (fun (i : Fin n) => (i.val < j)) Finset.univ).sum (fun i => y i) ≤
              Finset.univ.sum (fun i => y i) := by
      apply Finset.sum_le_univ_sum_of_nonneg
      intro i
      exact hy.1 i
    have h3 : Finset.univ.sum (fun i => y i) = 1 := hy.2
    linarith
  have h_probe : 0 ≤ thermomajorization_probe_error n F x y := by
    dsimp [thermomajorization_probe_error]
    exact Finset.le_max' _ 0 (Finset.mem_insert_self 0 _)
  linarith

theorem thermomajorization_pointwise_missed_error_ge_gap_error_le_iSup_2 {α β : Type*} (f : α → β → ℝ) (S : Set α) (T : Set β)
    (M : ℝ) (hM0 : 0 ≤ M) (hM : ∀ a ∈ S, ∀ b ∈ T, f a b ≤ M)
    {x : α} (hx : x ∈ S) {y : β} (hy : y ∈ T) :
    f x y ≤ ⨆ a ∈ S, ⨆ b ∈ T, f a b := by
  have h4 : f x y ≤ ⨆ (_ : y ∈ T), f x y := by
    have hbdd : BddAbove (Set.range (fun (_ : y ∈ T) => f x y)) := by
      refine ⟨M, ?_⟩
      rintro z ⟨hy', rfl⟩
      exact hM x hx y hy'
    exact le_ciSup hbdd hy
  have h3 : (⨆ (_ : y ∈ T), f x y) ≤ ⨆ b, ⨆ (_ : b ∈ T), f x b := by
    have hbdd : BddAbove (Set.range (fun b => ⨆ (_ : b ∈ T), f x b)) := by
      refine ⟨M, ?_⟩
      rintro z ⟨b, rfl⟩
      refine Real.iSup_le (fun hb => hM x hx b hb) hM0
    exact le_ciSup hbdd y
  have h2 : (⨆ b, ⨆ (_ : b ∈ T), f x b) ≤ ⨆ (_ : x ∈ S), ⨆ b, ⨆ (_ : b ∈ T), f x b := by
    have hbdd : BddAbove (Set.range (fun (_ : x ∈ S) => ⨆ b, ⨆ (_ : b ∈ T), f x b)) := by
      refine ⟨M, ?_⟩
      rintro z ⟨hx', rfl⟩
      refine Real.iSup_le (fun b => ?_) hM0
      refine Real.iSup_le (fun hb => hM x hx b hb) hM0
    exact le_ciSup hbdd hx
  have h1 : (⨆ (_ : x ∈ S), ⨆ b, ⨆ (_ : b ∈ T), f x b) ≤
      ⨆ a, ⨆ (_ : a ∈ S), ⨆ b, ⨆ (_ : b ∈ T), f a b := by
    have hbdd : BddAbove (Set.range (fun a => ⨆ (_ : a ∈ S), ⨆ b, ⨆ (_ : b ∈ T), f a b)) := by
      refine ⟨M, ?_⟩
      rintro z ⟨a, rfl⟩
      refine Real.iSup_le (fun ha => ?_) hM0
      refine Real.iSup_le (fun b => ?_) hM0
      refine Real.iSup_le (fun hb => hM a ha b hb) hM0
    exact le_ciSup hbdd x
  exact h4.trans (h3.trans (h2.trans h1))

/-- Lower bound on the pointwise thermomajorization missed error by the adjacent probe gap error. -/
theorem thermomajorization_pointwise_missed_error_ge_gap_error
    (n : ℕ) (hn : 2 ≤ n) (F : Finset ℕ) (hF : F ⊆ Finset.Ioo 0 n)
    (j : ℕ) (hj : j ∈ Finset.Ioo 0 n \ F) :
    let a := (insert 0 (F.filter (· < j))).max' (Finset.insert_nonempty 0 _)
    let b := (insert n (F.filter (j < ·))).min' (Finset.insert_nonempty n _)
    thermomajorization_probe_gap_error a b j ≤
      thermomajorization_pointwise_missed_error n F j := by
  intro a b
  have hj_ioo : j ∈ Finset.Ioo 0 n := Finset.mem_sdiff.mp hj |>.1
  have hj_not_F : j ∉ F := Finset.mem_sdiff.mp hj |>.2
  rw [Finset.mem_Ioo] at hj_ioo
  obtain ⟨hj0, hjn⟩ := hj_ioo
  have ha_lt_j : a < j := by
    dsimp [a]
    have : ∀ x ∈ insert 0 (F.filter (· < j)), x < j := by
      intro x hx
      simp only [Finset.mem_insert, Finset.mem_filter] at hx
      rcases hx with rfl | ⟨hx1, hx2⟩
      · exact hj0
      · exact hx2
    exact this a (Finset.max'_mem _ _)
  have hj_lt_b : j < b := by
    dsimp [b]
    have : ∀ x ∈ insert n (F.filter (j < ·)), j < x := by
      intro x hx
      simp only [Finset.mem_insert, Finset.mem_filter] at hx
      rcases hx with rfl | ⟨hx1, hx2⟩
      · exact hjn
      · exact hx2
    exact this b (Finset.min'_mem _ _)
  have hb_le_n : b ≤ n := by
    dsimp [b]
    have hn_mem : n ∈ insert n (F.filter (j < ·)) := Finset.mem_insert_self _ _
    exact Finset.min'_le _ n hn_mem
  have ha_lt_b : a < b := ha_lt_j.trans hj_lt_b
  have ha_le_n : a ≤ n := (ha_lt_b.trans_le hb_le_n).le
  have hj_le_n : j ≤ n := hjn.le

  have hj_pos : (0 : ℝ) < (j : ℝ) := Nat.cast_pos.mpr hj0
  have hba_pos : (0 : ℝ) < ((b : ℝ) - (a : ℝ)) := by
    rw [sub_pos]; exact Nat.cast_lt.mpr ha_lt_b
  have hdenom_pos : 0 < (j : ℝ) * ((b : ℝ) - (a : ℝ)) := mul_pos hj_pos hba_pos
  have hdenom_ne : (j : ℝ) * ((b : ℝ) - (a : ℝ)) ≠ 0 := hdenom_pos.ne'

  let d₁ : ℝ := ((b : ℝ) - (j : ℝ)) / ((j : ℝ) * ((b : ℝ) - (a : ℝ)))
  let d₂ : ℝ := ((j : ℝ) - (a : ℝ)) / ((j : ℝ) * ((b : ℝ) - (a : ℝ)))
  have hd₁_nonneg : 0 ≤ d₁ := by
    dsimp [d₁]
    apply div_nonneg
    · rw [sub_nonneg]; exact Nat.cast_le.mpr hj_lt_b.le
    · exact hdenom_pos.le
  have hd₂_nonneg : 0 ≤ d₂ := by
    dsimp [d₂]
    apply div_nonneg
    · rw [sub_nonneg]; exact Nat.cast_le.mpr ha_lt_j.le
    · exact hdenom_pos.le

  have hd_sum : d₁ + d₂ = 1 / (j : ℝ) := by
    dsimp [d₁, d₂]
    rw [← add_div]
    have h_num : ((b : ℝ) - (j : ℝ)) + ((j : ℝ) - (a : ℝ)) = (b : ℝ) - (a : ℝ) := by ring
    rw [h_num]
    have h_cancel : ((b : ℝ) - (a : ℝ)) / ((j : ℝ) * ((b : ℝ) - (a : ℝ))) =
        (1 : ℝ) / (j : ℝ) := by
      rw [mul_comm (j : ℝ)]
      have hx : ((b : ℝ) - (a : ℝ)) = ((b : ℝ) - (a : ℝ)) * 1 := (mul_one _).symm
      nth_rw 1 [hx]
      exact mul_div_mul_left 1 (j : ℝ) hba_pos.ne'
    exact h_cancel

  let x : Fin n → ℝ := fun i => (if (i : ℕ) < a then d₁ else 0) + (if (i : ℕ) < b then d₂ else 0)
  let y : Fin n → ℝ := fun i => if (i : ℕ) < j then d₁ + d₂ else 0

  have hx_nonneg : ∀ i, 0 ≤ x i := by
    intro i
    dsimp [x]
    apply add_nonneg <;> split_ifs <;> linarith
  have hy_nonneg : ∀ i, 0 ≤ y i := by
    intro i
    dsimp [y]
    split_ifs
    · linarith
    · rfl

  have hx_sum : ∑ i : Fin n, x i = 1 := by
    dsimp [x]
    rw [Finset.sum_add_distrib]
    have h_sum_a : ∑ i : Fin n, (if (i : ℕ) < a then d₁ else 0) = (a : ℝ) * d₁ := by
      have := thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter n n a ha_le_n d₁
      have h_univ : (Finset.filter (fun (i : Fin n) => (i : ℕ) < n) Finset.univ) = Finset.univ := by
        ext ⟨i, hi⟩; simp
      rw [h_univ] at this
      rw [min_eq_right ha_le_n] at this
      exact this
    have h_sum_b : ∑ i : Fin n, (if (i : ℕ) < b then d₂ else 0) = (b : ℝ) * d₂ := by
      have := thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter n n b hb_le_n d₂
      have h_univ : (Finset.filter (fun (i : Fin n) => (i : ℕ) < n) Finset.univ) = Finset.univ := by
        ext ⟨i, hi⟩; simp
      rw [h_univ] at this
      rw [min_eq_right hb_le_n] at this
      exact this
    rw [h_sum_a, h_sum_b]
    dsimp [d₁, d₂]
    have : (a : ℝ) * (((b : ℝ) - (j : ℝ)) / ((j : ℝ) * ((b : ℝ) - (a : ℝ)))) +
           (b : ℝ) * (((j : ℝ) - (a : ℝ)) / ((j : ℝ) * ((b : ℝ) - (a : ℝ)))) =
           ((a : ℝ) * ((b : ℝ) - (j : ℝ)) + (b : ℝ) * ((j : ℝ) - (a : ℝ))) / ((j : ℝ) * ((b : ℝ) - (a : ℝ))) := by
      ring
    rw [this]
    have h_alg : (a : ℝ) * ((b : ℝ) - (j : ℝ)) + (b : ℝ) * ((j : ℝ) - (a : ℝ)) =
                 (j : ℝ) * ((b : ℝ) - (a : ℝ)) := by ring
    rw [h_alg]
    exact div_self hdenom_ne

  have hy_sum : ∑ i : Fin n, y i = 1 := by
    dsimp [y]
    have := thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter n n j hj_le_n (d₁ + d₂)
    have h_univ : (Finset.filter (fun (i : Fin n) => (i : ℕ) < n) Finset.univ) = Finset.univ := by
      ext ⟨i, hi⟩; simp
    rw [h_univ] at this
    rw [min_eq_right hj_le_n] at this
    rw [this, hd_sum, mul_one_div_cancel hj_pos.ne']

  have hx_anti : Antitone x := by
    dsimp [x]
    have h1 := thermomajorization_pointwise_missed_error_ge_gap_error_antitone_indicator n a d₁ hd₁_nonneg
    have h2 := thermomajorization_pointwise_missed_error_ge_gap_error_antitone_indicator n b d₂ hd₂_nonneg
    exact fun i₁ i₂ hle => add_le_add (h1 hle) (h2 hle)

  have hy_anti : Antitone y := by
    dsimp [y]
    have hd_sum_nonneg : 0 ≤ d₁ + d₂ := add_nonneg hd₁_nonneg hd₂_nonneg
    exact thermomajorization_pointwise_missed_error_ge_gap_error_antitone_indicator n j (d₁ + d₂) hd_sum_nonneg

  have hx_mem : x ∈ {v | v ∈ stdSimplex ℝ (Fin n) ∧ Antitone v} :=
    ⟨⟨hx_nonneg, hx_sum⟩, hx_anti⟩
  have hy_mem : y ∈ {v | v ∈ stdSimplex ℝ (Fin n) ∧ Antitone v} :=
    ⟨⟨hy_nonneg, hy_sum⟩, hy_anti⟩

  have h_diff_k : ∀ k, thermomajorization_diff x y k =
      ((min k j : ℕ) : ℝ) * (d₁ + d₂) - (((min k a : ℕ) : ℝ) * d₁ + ((min k b : ℕ) : ℝ) * d₂) := by
    intro k
    unfold thermomajorization_diff
    dsimp [x, y]
    rw [Finset.sum_sub_distrib, Finset.sum_add_distrib]
    rw [thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter n k j hj_le_n (d₁ + d₂)]
    rw [thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter n k a ha_le_n d₁]
    rw [thermomajorization_pointwise_missed_error_ge_gap_error_sum_indicator_filter n k b hb_le_n d₂]

  have h_diff_F : ∀ k ∈ F, thermomajorization_diff x y k = 0 := by
    intro k hk
    have hkj : k ≠ j := by rintro rfl; exact hj_not_F hk
    rcases lt_or_gt_of_ne hkj with h_lt | h_gt
    · have hka : k ≤ a := by
        dsimp [a]
        have hk_mem : k ∈ insert 0 (F.filter (· < j)) := by simp [hk, h_lt]
        exact Finset.le_max' _ k hk_mem
      rw [h_diff_k k]
      have h1 : min k j = k := min_eq_left (hka.trans ha_lt_j.le)
      have h2 : min k a = k := min_eq_left hka
      have h3 : min k b = k := min_eq_left (hka.trans ha_lt_b.le)
      rw [h1, h2, h3]
      ring
    · have hbk : b ≤ k := by
        dsimp [b]
        have hk_mem : k ∈ insert n (F.filter (j < ·)) := by simp [hk, h_gt]
        exact Finset.min'_le _ k hk_mem
      rw [h_diff_k k]
      have h1 : min k j = j := min_eq_right (hj_lt_b.le.trans hbk)
      have h2 : min k a = a := min_eq_right (ha_lt_b.le.trans hbk)
      have h3 : min k b = b := min_eq_right hbk
      rw [h1, h2, h3]
      dsimp [d₁, d₂]
      ring

  have h_probe_zero : thermomajorization_probe_error n F x y = 0 := by
    dsimp [thermomajorization_probe_error]
    apply le_antisymm
    · rw [Finset.max'_le_iff]
      intro z hz
      simp only [Finset.mem_insert, Finset.mem_image] at hz
      rcases hz with rfl | ⟨k, hk, rfl⟩
      · rfl
      · rw [h_diff_F k hk]
    · exact Finset.le_max' _ 0 (Finset.mem_insert_self 0 _)

  have h_diff_j : thermomajorization_diff x y j = thermomajorization_probe_gap_error a b j := by
    rw [h_diff_k j]
    have h1 : min j j = j := min_self j
    have h2 : min j a = a := min_eq_right ha_lt_j.le
    have h3 : min j b = j := min_eq_left hj_lt_b.le
    rw [h1, h2, h3]
    dsimp [d₁, d₂, thermomajorization_probe_gap_error]
    ring

  have h_target : thermomajorization_probe_gap_error a b j =
      thermomajorization_diff x y j - thermomajorization_probe_error n F x y := by
    rw [h_diff_j, h_probe_zero, sub_zero]

  rw [h_target]
  have hM : ∀ x' ∈ {v | v ∈ stdSimplex ℝ (Fin n) ∧ Antitone v},
            ∀ y' ∈ {v | v ∈ stdSimplex ℝ (Fin n) ∧ Antitone v},
            thermomajorization_diff x' y' j - thermomajorization_probe_error n F x' y' ≤ 1 := by
    intro x' hx' y' hy'
    exact thermomajorization_pointwise_missed_error_ge_gap_error_diff_sub_probe_le_one n F j x' y' hx'.1 hy'.1
  exact thermomajorization_pointwise_missed_error_ge_gap_error_le_iSup_2 (fun x' y' => thermomajorization_diff x' y' j - thermomajorization_probe_error n F x' y')
    {v | v ∈ stdSimplex ℝ (Fin n) ∧ Antitone v} {v | v ∈ stdSimplex ℝ (Fin n) ∧ Antitone v}
    1 zero_le_one hM hx_mem hy_mem
See it in the graphDiscuss this resultChallenge it