Eight-way multiplication: every completed output has distinct fresh rows
ProvedCLRS.MatrixRecursiveAnalysis.every_execution_fresh_rowsSuppose a completed recursive multiplication on represented nested inputs has dimension . Its returned outer reference is the initial next unused outer-array identifier. Write for the initial next unused row identifier. For every integer , the returned row is , is fresh, and is allocated in the final heap. For integer indices inside this square,
This statement applies to every completed return and permits arbitrary sharing among the input rows. It separates the result's allocation identities from the mathematical equality of its row values.
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 open Algo2LeanCore.MatrixHeap
theorem CLRS.MatrixRecursiveAnalysis.every_execution_fresh_rows (heap finalHeap : Heap) (a b result : CollectionRef)
(av bv : Values) (depth : Nat) (ha : Stored heap a av) (hb : Stored heap b bv)
(run : matrix_recursive.Returns (heap, a, b, (2 ^ depth : Nat)) (finalHeap, result)) :
result = heap.nextCollection ∧
(∀ i : Int, 0 ≤ i → i < (2 ^ depth : Nat) →
seq_Seq_Int.get finalHeap result i = some (heap.nextRef + 1 + i.toNat) ∧
heap.nextRef < heap.nextRef + 1 + i.toNat ∧ heap.nextRef + 1 + i.toNat < finalHeap.nextRef) ∧
(∀ i j : Int, 0 ≤ i → i < (2 ^ depth : Nat) → 0 ≤ j → j < (2 ^ depth : Nat) →
(seq_Seq_Int.get finalHeap result i = seq_Seq_Int.get finalHeap result j ↔ i = j)) := by sorry