Documentation

Complexity.Algorithms.WordRAM.MatrixMultiplication.Schonhage.Callable.Width

Every-wide-width initialized callable product #

The width threshold depends only on original row/occurrence counts and the length/word bound of the protected caller prefix. The actual program never reads physical width. Generic execution does not assume query sparsity; only the final quantitative saving does.

Positive logarithmic physical width derived entirely from original input and caller data.

Instances For

    The concrete threshold remains positive at all boundary parameters.

    theorem Cslib.Algorithms.WordRAM.MatrixMultiplication.Schonhage.CallableProduct.admission_bounds {W N Q P : ℕ} (caller : List ℕ) (hP : ∀ v ∈ caller, v ≤ P) (hW : admissionWidth caller N Q P ≤ W) :
    WordRAM.Fits W (inputBase caller + 4 * windowSize N Q + 1024) ∧ ∀ v ∈ caller, WordRAM.Fits W v

    Physical admission covers both the computed virtual window and all caller-prefix words.

    theorem Cslib.Algorithms.WordRAM.MatrixMultiplication.Schonhage.CallableProduct.caller_prefix_bounded {W b N Q P k : ℕ} {x : WordRAM.Data 163} {z : WordRAM.State 163} (hregs : ∀ (i : Fin 163), x.regs i ≤ P) (hmem : ∀ (a : ℕ), x.mem a ≤ P) (hW : 256 * Nat.clog 2 (b + N + Q + P + 5) ≤ W) (hr : WordRAM.Runs W (program.program Reg.result) { pc := 0, data := x } z k) :

    Every native caller prefix is physically word-bounded, including a loaded dirty word before the following remainder. Here P bounds every initial register and memory word, not merely the source input or normalized values. It is an initial-data bound, not a bound on intermediates supplied by the caller.

    theorem Cslib.Algorithms.WordRAM.MatrixMultiplication.Schonhage.CallableProduct.runs_caller {W b m N P : ℕ} (X : Matrix (Fin N) (Fin (MatrixMultiplication.Schonhage.D m)) ℤ) (Y : Matrix (Fin (MatrixMultiplication.Schonhage.D m)) (Fin N) ℤ) (qs : List (Fin N × Fin N)) (x : WordRAM.Data 163) (hb : x.regs Reg.base = b) (hinput : ∀ a < QueriedProduct.inputEnd m N qs.length, x.mem (b + a) = (WordRAM.State.init (QueriedProduct.input true (19 * m) X Y qs)).data.mem a) (hX : ∀ (i : Fin N) (k : Fin (MatrixMultiplication.Schonhage.D m)), 0 ≤ X i k ∧ X i k ≤ 1) (hY : ∀ (k : Fin (MatrixMultiplication.Schonhage.D m)) (j : Fin N), 0 ≤ Y k j ∧ Y k j ≤ 1) (hN : MatrixMultiplication.Schonhage.D m ^ 18 ≤ N) (hregs : ∀ (i : Fin 163), x.regs i ≤ P) (hmem : ∀ (a : ℕ), x.mem a ≤ P) (hW : 256 * Nat.clog 2 (b + N + qs.length + P + 5) ≤ W) :
    ∃ (y : WordRAM.Data 163), ∃ n ≤ timeBound qs, WordRAM.Runs W (program.program Reg.result) { pc := 0, data := x } { pc := program.size, data := y } n ∧ WordRAM.Executes W (program.program Reg.result) { pc := 0, data := x } (b + QueriedProduct.outputBase (19 * m) m N qs.length) (n + 1) ∧ WordRAM.Data.Bounded W y ∧ (∀ (i : Fin qs.length), y.mem (b + (QueriedProduct.outputBase (19 * m) m N qs.length + ↑i)) = WordRAM.Signed.encode ((X * Y) (qs.get i).1 (qs.get i).2)) ∧ (∀ a < QueriedProduct.inputEnd m N qs.length, y.mem (b + a) = x.mem (b + a)) ∧ ∀ (a : ℕ), a < b ∨ b + windowSize N qs.length ≤ a → y.mem a = x.mem a

    Actual callable flat runs at every admitted physical width, with arbitrary dirty initial workspace bounded by P. This is the interface for a real producer's reachable caller state: P bounds all its initial words, including dirty pre-modulo loads. Original local input words derive the concrete source execution; no solver, run, time, routing or layout certificate is assumed. The same final y contains exact answers, restored input and the caller frame.

    theorem Cslib.Algorithms.WordRAM.MatrixMultiplication.Schonhage.CallableProduct.runs_wide {W m N P : ℕ} (caller : List ℕ) (X : Matrix (Fin N) (Fin (MatrixMultiplication.Schonhage.D m)) ℤ) (Y : Matrix (Fin (MatrixMultiplication.Schonhage.D m)) (Fin N) ℤ) (qs : List (Fin N × Fin N)) (hN : MatrixMultiplication.Schonhage.D m ^ 18 ≤ N) (hX : ∀ (i : Fin N) (k : Fin (MatrixMultiplication.Schonhage.D m)), 0 ≤ X i k ∧ X i k ≤ 1) (hY : ∀ (k : Fin (MatrixMultiplication.Schonhage.D m)) (j : Fin N), 0 ≤ Y k j ∧ Y k j ≤ 1) (hP : ∀ v ∈ caller, v ≤ P) (hW : admissionWidth caller N qs.length P ≤ W) :
    WordRAM.InputFits W (input caller X Y qs) ∧ ∃ (y : WordRAM.Data 163) (n : ℕ), n + 1 ≤ timeBound qs + 3 ∧ WordRAM.Runs W (entryProgram.program Reg.result) (WordRAM.State.init (input caller X Y qs)) { pc := entryProgram.size, data := y } n ∧ WordRAM.Executes W (entryProgram.program Reg.result) (WordRAM.State.init (input caller X Y qs)) (inputBase caller + QueriedProduct.outputBase (19 * m) m N qs.length) (n + 1) ∧ WordRAM.Data.Bounded W y ∧ (∀ (i : Fin qs.length), y.mem (inputBase caller + (QueriedProduct.outputBase (19 * m) m N qs.length + ↑i)) = WordRAM.Signed.encode ((X * Y) (qs.get i).1 (qs.get i).2)) ∧ (∀ a < QueriedProduct.inputEnd m N qs.length, y.mem (inputBase caller + a) = (WordRAM.State.init (input caller X Y qs)).data.mem (inputBase caller + a)) ∧ ∀ (a : ℕ), a < inputBase caller ∨ inputBase caller + windowSize N qs.length ≤ a → y.mem a = (WordRAM.State.init (input caller X Y qs)).data.mem a

    At every admitted physical width, the initialized callable program returns all requested exact product words and preserves caller/local-input memory. No sparsity premise is used.

    theorem Cslib.Algorithms.WordRAM.MatrixMultiplication.Schonhage.CallableProduct.bounded_reachable {W m N P k : ℕ} (caller : List ℕ) (X : Matrix (Fin N) (Fin (MatrixMultiplication.Schonhage.D m)) ℤ) (Y : Matrix (Fin (MatrixMultiplication.Schonhage.D m)) (Fin N) ℤ) (qs : List (Fin N × Fin N)) (hN : MatrixMultiplication.Schonhage.D m ^ 18 ≤ N) (hX : ∀ (i : Fin N) (k : Fin (MatrixMultiplication.Schonhage.D m)), 0 ≤ X i k ∧ X i k ≤ 1) (hY : ∀ (k : Fin (MatrixMultiplication.Schonhage.D m)) (j : Fin N), 0 ≤ Y k j ∧ Y k j ≤ 1) (hP : ∀ v ∈ caller, v ≤ P) (hW : admissionWidth caller N qs.length P ≤ W) {z : WordRAM.State 163} (hz : WordRAM.Runs W (entryProgram.program Reg.result) (WordRAM.State.init (input caller X Y qs)) z k) :

    Every initialized prefix, including raw dirty loads before normalization, fits the admitted physical width. Outside the explicit original input the initialized memory is zero. Thus P in this initialized interface need only bound the protected caller prefix.

    theorem Cslib.Algorithms.WordRAM.MatrixMultiplication.Schonhage.CallableProduct.runs_thin {W m N P : ℕ} (caller : List ℕ) (X : Matrix (Fin N) (Fin (MatrixMultiplication.Schonhage.D m)) ℤ) (Y : Matrix (Fin (MatrixMultiplication.Schonhage.D m)) (Fin N) ℤ) (qs : List (Fin N × Fin N)) (hN : MatrixMultiplication.Schonhage.D m ^ 18 ≤ N) (hQ : qs.length * 2 ^ m ≤ N ^ 2) (hX : ∀ (i : Fin N) (k : Fin (MatrixMultiplication.Schonhage.D m)), 0 ≤ X i k ∧ X i k ≤ 1) (hY : ∀ (k : Fin (MatrixMultiplication.Schonhage.D m)) (j : Fin N), 0 ≤ Y k j ∧ Y k j ≤ 1) (hP : ∀ v ∈ caller, v ≤ P) (hW : admissionWidth caller N qs.length P ≤ W) :
    WordRAM.InputFits W (input caller X Y qs) ∧ ∃ (y : WordRAM.Data 163) (n : ℕ), WordRAM.Runs W (entryProgram.program Reg.result) (WordRAM.State.init (input caller X Y qs)) { pc := entryProgram.size, data := y } n ∧ WordRAM.Executes W (entryProgram.program Reg.result) (WordRAM.State.init (input caller X Y qs)) (inputBase caller + QueriedProduct.outputBase (19 * m) m N qs.length) (n + 1) ∧ ↑(n + 1) ≤ 17301504 * ↑(19 * m + 1) * ↑N ^ 2 / ↑(MatrixMultiplication.Schonhage.D m) ^ (1 / 18) ∧ WordRAM.Data.Bounded W y ∧ (∀ (i : Fin qs.length), y.mem (inputBase caller + (QueriedProduct.outputBase (19 * m) m N qs.length + ↑i)) = WordRAM.Signed.encode ((X * Y) (qs.get i).1 (qs.get i).2)) ∧ (∀ a < QueriedProduct.inputEnd m N qs.length, y.mem (inputBase caller + a) = (WordRAM.State.init (input caller X Y qs)).data.mem (inputBase caller + a)) ∧ ∀ (a : ℕ), a < inputBase caller ∨ inputBase caller + windowSize N qs.length ≤ a → y.mem a = (WordRAM.State.init (input caller X Y qs)).data.mem a

    Complete actual initialized thin saving, including base loading, all translated memory accesses, span normalization and halt. The occurrence bound is explicit and stronger than a distinct-set bound for lists containing duplicate requests.