PR #6453: the recursion composing the invoices into the bound
ProvedPr6453.recursionThe recursion of the PR #6453 word: the price inequality is exactly the statement that one level of the call tree costs a strictly smaller fraction of what the level above it produces, and consequently the whole tree costs at most a constant multiple of its root — with the same exponent on the logarithm.
The first conjunct identifies the contraction ratio. At the claimed saving a call of the word produces units and pays , and the price inequality says their ratio is strictly below one.
The second conjunct is the geometric composition. If the cost of level is at most times the cost of level , then the sum over any number of levels is at most : the depth of the recursion costs a constant factor, not a factor that grows with the depth.
The third conjunct puts the logarithms back in. If the root costs at most then the whole tree costs at most , for every depth . The exponent survives the recursion; only the constant is multiplied by , which is about at the claimed saving — the numerical reason the source's claims are conditional.
import Definitions.Def_Pr6453_RankMoments import Definitions.Def_Pr6453_Recursion import Definitions.Def_IntMul_MultitapeModel import Theorems.Thm_Pr6453_moment_kappa_gt set_option autoImplicit false
namespace Pr6453
theorem recursion :
gamma < 1 ∧
(∀ (C : ℕ → ℝ), 0 ≤ C 0 → (∀ j, C (j + 1) ≤ gamma * C j) →
∀ L : ℕ, (∑ j ∈ Finset.range L, C j) ≤ C 0 / (1 - gamma)) ∧
(∀ (C : ℕ → ℝ) (c : ℝ) (n L : ℕ), 0 ≤ c → 0 ≤ C 0 →
C 0 ≤ c * (n : ℝ) * ((IntMul.lg n : ℝ) ^ (1 - (kappa : ℝ))) →
(∀ j, C (j + 1) ≤ gamma * C j) →
(∑ j ∈ Finset.range L, C j) ≤
(c / (1 - gamma)) * (n : ℝ) * ((IntMul.lg n : ℝ) ^ (1 - (kappa : ℝ)))) := by
sorry
end Pr6453