Correctness and running time of source field addition
ProvedExpandingCodes.Computation.SourceFieldArithmetic.addition_stopscoding-theorycomplexity-theoryexpanding-codes-polynomial-stretch
Let , , and let encode binary coefficient vectors of length . Let be a store with registers and buffers, an injective placement of a 27-register workspace, and any input. Suppose , every register is at most , and workspace registers contain .
The addition program reaches its specified result store with
Here is coefficientwise addition modulo two, including the empty-vector case . The designated input and parameter registers, registers outside the workspace, and tape payload are preserved, and all registers remain at most . When , this is addition in the corresponding binary extension field.
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryRuntime set_option autoImplicit false open scoped Classical open NKtLB
Formal statement
theorem ExpandingCodes.Computation.SourceFieldArithmetic.addition_stops {R B : ℕ} (r : Fin 27 → Fin R) (hr : Function.Injective r)
(inp : Inputs) (ell : ℕ) (a b : Fin (2^ell)) (M : ℕ) (hM : 1 ≤ M)
(d : ExpandingCodes.Computation.TapeStore R B) (hd : ∀ j,d.reg j ≤ M) (ha : d.reg (r 0) = a.val) (hb : d.reg (r 3) = b.val)
(hN : d.reg (r 19) = 3*ell+1) (hq : d.reg (r 23) = 2^ell) :
∃ t e,t ≤ 3000*(M+1)^5 ∧
(ExpandingCodes.Computation.SourceFieldArithmetic.addition r).Stops inp (d.toCfg (ExpandingCodes.Computation.SourceFieldArithmetic.addition (B:=B) r).entry) t e ∧ e.store = ExpandingCodes.Computation.SourceFieldArithmetic.additionResult r d ∧
e.reg (r 20) = (ExpandingCodes.PolynomialStretch.BinaryField.addIndex ell a b).val ∧
(∀ i,i = 0 ∨ i = 3 ∨ i = 19 ∨ 23 ≤ i → i ≠ 25 → e.reg (r i) = d.reg (r i)) ∧
(∀ j,(∀ i,j ≠ r i) → e.reg j = d.reg j) ∧ (∀ j,e.reg j ≤ M) ∧ ExpandingCodes.Computation.FieldConvolution.tapeData e.store = ExpandingCodes.Computation.FieldConvolution.tapeData d := by sorry
Source
Algorithmic supporting lemma for Section 2 of Isaac M Hair and Amit Sahai, Expanding Codes with Polynomial Stretch; the explicit tape-machine implementation is formalized in ExpandingCodes.Computation.SourceFieldArithmetic. Supporting formal implementation contract, rather than a verbatim statement in the paper. Exact local source: ExpandingCodes/Computation/SourceFieldArithmetic.lean, declaration ExpandingCodes.Computation.SourceFieldArithmetic.addition_stops; source file SHA256 82fb97d5572b62ae185bb5c6e4cda9100cd6cbac79b43d2f1a3514ef69bc0b6a. The public construction is at https://prove2.me/missions/Expanding_Codes_with_Polynomial_Stretch.