Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Source-linked Strassen work and balanced recurrence examples

Definition
CLRS_Chapter4_RecurrenceApplications

by Chutong · Oct 11, 2026 · Mathlib 0df444a (Lean v4.33.1)

algo2leanalgo2lean-clrs-chapter4-fd33cf9algorithmsclrsrunning-timetextbook

The 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.

Definition code
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
Source
Algo2Lean Chapter 4 development, module RecurrenceApplications, immutable source fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41: https://github.com/chutongyang98/Lean_formalization/blob/fd33cf959b39f9e4a9fcfda4ef31d5a36b784d41/proofs/chapter4/RecurrenceApplications.lean

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me