Eight-way recursion: the block effect adds its mathematical contribution
ProvedCLRS.MatrixRecursiveAnalysis.blockEffect_correctLet the block size be , and let map integer row indices to row references. No input row reference may equal any output row reference. For each row index within the stride, equality must be equivalent to . Assume the block's starting row is nonnegative and its last row lies within the stride. Other integer block offsets and queried indices remain as supplied in the formal statement. Then
Here the contribution is the specified block dot-product contribution of the original input row stores, with the same stride, recursion depth, and row, column, and inner-index offsets. Inputs may alias one another. This is a functional heap-effect identity, distinct from the later execution theorem.
Platform namespace. The imported Chapter 4 source declarations live under CLRS in this upload to avoid collisions with independently published compiler versions. The immutable source reference retains the original declaration names.
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.MatrixRecursive.correctness_and_running_time. Supporting lemmas needed by the retained results are included in their accepted proof files.
import Definitions.Def_CLRS_Chapter4_Algo2Lean import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixRecursive import Definitions.Def_CLRS_Chapter4_Algo2LeanExamples_MatrixRecursiveGenerated import Definitions.Def_CLRS_Chapter4_Algo2LeanLib_MatrixHeap import Std set_option autoImplicit false set_option backward.isDefEq.respectTransparency false set_option backward.defeqAttrib.useBackward true namespace CLRS end CLRS open CLRS open MatrixRecursiveLibrary MatrixRecursiveLibrary.Algo2LeanGenerated open Algo2LeanCore Algo2LeanGenerated namespace CLRS.MatrixRecursiveAnalysis end CLRS.MatrixRecursiveAnalysis open CLRS.MatrixRecursiveAnalysis set_option maxRecDepth 10000 set_option maxHeartbeats 2000000
theorem CLRS.MatrixRecursiveAnalysis.blockEffect_correct (depth : Nat) (heap : Heap) (a b c : Int → SeqRef)
(stride row col inner qr qc : Int) (ha : ∀ i j, a i ≠ c j) (hb : ∀ i j, b i ≠ c j)
(distinct : ∀ i j, 0 ≤ j → j < stride → (c i = c j ↔ i = j))
(row_nonnegative : 0 ≤ row) (row_bound : row + (2 ^ depth : Nat) ≤ stride) :
(blockEffect a b c stride depth heap row col inner).read (c qr) qc =
heap.read (c qr) qc +
contribution (fun i => heap.store (a i)) (fun i => heap.store (b i)) stride qr qc depth row col inner := by sorry