Source-linked Strassen work and balanced recurrence examples
DefinitionCLRS_Chapter4_RecurrenceApplicationsThe Strassen work function sums the products, calls, linear_cells and copied_cells increments of the exact nested-matrix execution costs. At depth k it has W(0)=2 and W(k+1)=7W(k)+30*4^k+1. Other definitions provide strengthened comparison candidates and a balanced linear-toll example. Execution and asymptotic theorems are separate nodes; the source-linked work counts explicit ticks, not all generated transitions or integer bit complexity.
Formalization Note. This content is transcribed from Algo2Lean development snapshot fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41, with explicit platform import and namespace adaptation. It is not attributed to public compiler v0.1.4. The submitted definition bundle must be checked without unfinished-proof assumptions.
Catalog organization (2026-10-11). This record was retired from the active Chapter 4 catalog to focus the presentation on three algorithms and four reusable recurrence results. Its mathematical statement and proof status are unchanged, and existing imports and links remain valid. The retained results are CLRS.Chapter4Publication.Strassen.correctness_and_running_time. This example-only definition module is not required by the seven retained proofs.
import Definitions.Def_CLRS_Chapter4_Algo2Lean
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassen
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassenGenerated
import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixStrassenPoints
import Definitions.Def_CLRS_Chapter4_Algo2LeanLib_MatrixHeap
import Definitions.Def_CLRS_Chapter4_RecursionTree
import Definitions.Def_CLRS_Chapter4_Substitution
import Std
set_option autoImplicit false
set_option backward.isDefEq.respectTransparency false
set_option backward.defeqAttrib.useBackward true
namespace CLRS
open MatrixStrassenLibrary MatrixStrassenLibrary.Algo2LeanGenerated
/-!
Worked uses of the general §4.3–4.4 methods. The Strassen theorems concern the
existing compiled program and all four of its measured work categories.
The balanced linear-work example is a numerical recurrence, not a new proof
of merge sort's source-level runtime.
-/
namespace Chapter4RecurrenceApplications
open Algo2LeanCore Algo2LeanGenerated
open Algo2LeanCore.MatrixHeap
open Chapter4Substitution Chapter4RecursionTree
/-- Sum exactly the four clocks already linked to Strassen's source execution. -/
def strassenWork (depth : Nat) : Nat :=
MatrixStrassenExecution.costs depth "products" +
MatrixStrassenExecution.costs depth "calls" +
MatrixStrassenExecution.costs depth "linear_cells" +
MatrixStrassenExecution.costs depth "copied_cells"
/-- Strengthening the induction hypothesis absorbs the additive toll. A plain
candidate C*7^k cannot close substitution while a positive toll remains. -/
def strengthenedWork (depth : Nat) : Nat := strassenWork depth + 10*4^depth+1
end Chapter4RecurrenceApplications
end CLRS