Total correctness of source field inversion
ProvedExpandingCodes.Computation.SourceFieldArithmetic.inverse_stopscoding-theorycomplexity-theoryexpanding-codes-polynomial-stretch
Let , , and let encode an element of the canonical binary extension field. Let be a store with registers and buffers, an injective placement of a 31-register workspace, and any input. Suppose , every register is at most , and the initial workspace satisfies the inversion setup conditions, including the canonical field parameters and encoded operand.
The inversion program reaches its specified result store with
The operation is total, with . The designated input and parameter registers, registers outside the workspace, and tape payload are preserved, and every register remains at most . This supplies the physical inverse operation used by Gaussian elimination.
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryRuntime set_option autoImplicit false open scoped Classical open NKtLB
Formal statement
theorem ExpandingCodes.Computation.SourceFieldArithmetic.inverse_stops {R B : ℕ} (r : Fin 31 → Fin R) (hr : Function.Injective r) (inp : Inputs)
(ell : ℕ) (h : 0 < ell) (a : Fin (2^ell)) (M : ℕ) (hM : 1 ≤ M)
(d : ExpandingCodes.Computation.TapeStore R B) (hd : ∀ j,d.reg j ≤ M) (hs : ExpandingCodes.Computation.SourceFieldArithmetic.InverseSetup r ell h a d) :
∃ t e,t ≤ 20000*(M+1)^7 ∧ (ExpandingCodes.Computation.SourceFieldArithmetic.inverse r).Stops inp (d.toCfg (ExpandingCodes.Computation.SourceFieldArithmetic.inverse (B:=B) r).entry) t e ∧
e.store = ExpandingCodes.Computation.SourceFieldArithmetic.inverseResult r d ∧ e.reg (r 27) = (ExpandingCodes.PolynomialStretch.BinaryField.inverseIndex ell h a).val ∧
(∀ i,i = 0 ∨ i = 3 ∨ i = 19 ∨ i = 23 ∨ i = 24 → 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.inverse_stops; source file SHA256 82fb97d5572b62ae185bb5c6e4cda9100cd6cbac79b43d2f1a3514ef69bc0b6a. The public construction is at https://prove2.me/missions/Expanding_Codes_with_Polynomial_Stretch.