Lemma A.5 —
ProvedMultiThinkCoT.lemma_A_5boostingchain-of-thoughtlearning-theoryp2o-gran-per-chapterp2o-plan-paperp2o-v1
For every there is a constant , depending only on , such that for every , every and every ,
Theorem 7 uses it with to turn the implicit sample-size condition of Lemma F.4, in which depends on , into the explicit .
Formalization Note with the natural logarithm; is a real number and the power is a real power.
Differences from the source:
- reading: for every k ≥ 1 (the paper does not say whether k is an integer) → every real k ≥ 1, log^k u = (log u)^k as a real power; reason: the more general of the two readings; it contains every integer k, in particular k = 2 used in Theorem 7
Preamble
import Mathlib
Formal statement
namespace MultiThinkCoT
/-- **Lemma A.5 (Algebraic inequality)**, p.35 (PDF p.35).
N. Joshi, R. Magen, N. Srebro, N. Tsilivis, G. Vardi, *Learning to Think from Multiple Thinkers:
How Chain-of-Thought Heterogeneity Affects Efficient Learnability*, arXiv:2604.24737 (held
version, sha256 e663a640…).
For every `k ≥ 1` there exists a constant `c > 0`, depending only on `k`, such that for every
`a ≥ e`, every `b ≥ 0` and every `x > 0`: if `x ≥ c (a log^k(a) + b)` then
`x ≥ a log^k(x) + b`.
**Formalization Note.** `k` is a real number `≥ 1` (the paper does not say whether `k` is an
integer; Theorem 7 uses `k = 2`), and `log^k u = (log u)^k` is a real power (`Real.rpow`) of the
natural logarithm.
-/
theorem lemma_A_5 :
∀ k : ℝ, 1 ≤ k → ∃ c : ℝ, 0 < c ∧
∀ a b x : ℝ, Real.exp 1 ≤ a → 0 ≤ b → 0 < x →
c * (a * Real.log a ^ k + b) ≤ x → a * Real.log x ^ k + b ≤ x := by sorry
end MultiThinkCoT
Source
Joshi, Magen, Srebro, Tsilivis, Vardi, Learning to Think from Multiple Thinkers: How Chain-of-Thought Heterogeneity Affects Efficient Learnability, arXiv:2604.24737 (held version, sha256 e663a640…), Appendix A, Lemma A.5, p.35 (PDF p.35)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.