Proof of Theorem 2.6, p. 9 — Λ_k[F^{|C*|+1}] ≤ α₃^{|C*|+1} − (α₃ − α₁)α₂^{|C*|} < 1 for every row k of sum ≥ 1
ProvedSubSuperStoch.SuperSpec.R2_rows_power_boundnonnegative-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1row-sumsuper-stochastic-matrix
Let be an super-stochastic matrix, and let and be non-empty. Suppose that for each a non-zero element chain with is given, and let be the largest number of elements of these chains. With
assume condition (2.5):
Then for every ,
This is the second step of the proof of Theorem 2.6: it lifts the chain bound from to the common power for every row of sum at least one.
Formalization Note The chosen chains are given by a length function on rows: for each there are and a chain from to of elements, and is the greatest of over . The -th root is the real power ; its radicand is nonnegative under the hypotheses ( and ), and since condition (2.5) is equivalent to .
Preamble
import Mathlib import Definitions.Def_SubSuperStoch_SuperSpec_Setting
Formal statement
namespace SubSuperStoch.SuperSpec
theorem R2_rows_power_bound {n : ℕ} (F : Matrix (Fin n) (Fin n) ℝ) (hF : IsSuperStochastic F)
(hR₁ : ∃ s, SubSuperStoch.SubSpec.rowSum F s < 1) (hR₂ : ∃ s, 1 ≤ SubSuperStoch.SubSpec.rowSum F s)
(len : Fin n → ℕ)
(hchain : ∀ k, 1 ≤ SubSuperStoch.SubSpec.rowSum F k → ∃ i, SubSuperStoch.SubSpec.rowSum F i < 1 ∧
∃ c : ℕ → Fin n, c 0 = i ∧ c (len k) = k ∧ 1 ≤ len k ∧ SubSuperStoch.SubSpec.IsChain F c (len k))
(α₁ : ℝ) (hα₁ : IsGreatest {x | ∃ s, SubSuperStoch.SubSpec.rowSum F s < 1 ∧ x = SubSuperStoch.SubSpec.rowSum F s} α₁)
(α₂ : ℝ) (hα₂ : IsLeast {x | ∃ i j, 0 < F i j ∧ x = F i j} α₂)
(α₃ : ℝ) (hα₃ : IsGreatest {x | ∃ s, 1 ≤ SubSuperStoch.SubSpec.rowSum F s ∧ x = SubSuperStoch.SubSpec.rowSum F s} α₃)
(C : ℕ) (hC : IsGreatest {m | ∃ k, 1 ≤ SubSuperStoch.SubSpec.rowSum F k ∧ m = len k} C)
(h25 : (α₃ ^ (C + 1) - (α₃ - α₁) * α₂ ^ C) ^ (1 / (C : ℝ)) < 1) :
∀ k, 1 ≤ SubSuperStoch.SubSpec.rowSum F k →
SubSuperStoch.SubSpec.rowSum (F ^ (C + 1)) k ≤ α₃ ^ (C + 1) - (α₃ - α₁) * α₂ ^ C ∧
α₃ ^ (C + 1) - (α₃ - α₁) * α₂ ^ C < 1 := by sorry
end SubSuperStoch.SuperSpec
Source
Shi, Zheng, Shao, Cheng, arXiv:2004.01867v2, p. 9, proof of Theorem 2.6, second display; condition (2.5)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.