Construction of a canonical binary field environment
ProvedExpandingCodes.Computation.SourceFieldSetup.setup_stopscoding-theorycomplexity-theoryexpanding-codes-polynomial-stretch
Let , , and let be a source-machine store with registers and buffers. Let injectively place a 32-register workspace in its register bank, and let be any input. Initially every register is at most , workspace registers 20 and 23 contain and , and
The field-setup program reaches its specified final store and the canonical binary-field environment in time
All registers remain at most . Registers outside the workspace and the read heads, buffer contents, buffer heads and output are preserved. This provides field construction from runtime size parameters for both the sampler and the tester.
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryRuntime set_option autoImplicit false open scoped Classical open NKtLB
Formal statement
theorem ExpandingCodes.Computation.SourceFieldSetup.setup_stops {R B : ℕ} (r : Fin 32 → Fin R) (hr : Function.Injective r) (inp : Inputs)
(ell : ℕ) (h : 0 < ell) (M : ℕ) (d : ExpandingCodes.Computation.TapeStore R B) (hd : ∀ j,d.reg j ≤ M)
(hell : d.reg (r 20) = ell) (hq : d.reg (r 23) = 2^ell)
(hN : 3*ell+1 ≤ M) (h2q : 2*(2^ell) ≤ M) (hQ : 2^(2*ell) ≤ M) :
∃ t e,t ≤ 40000*(M+1)^7 ∧ (ExpandingCodes.Computation.SourceFieldSetup.setup r).Stops inp (d.toCfg (ExpandingCodes.Computation.SourceFieldSetup.setup (B:=B) r).entry) t e ∧
e.store = ExpandingCodes.Computation.SourceFieldSetup.setupStore r d ∧ ExpandingCodes.Computation.SourceFieldSetup.Environment r ell h e.store ∧
(∀ 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.SourceFieldSetup. Supporting formal implementation contract, rather than a verbatim statement in the paper. Exact local source: ExpandingCodes/Computation/SourceFieldSetup.lean, declaration ExpandingCodes.Computation.SourceFieldSetup.setup_stops; source file SHA256 c4b3734751e49abfbcdb60b20015f726d583a9eb75323343af23f73b179261c1. The public construction is at https://prove2.me/missions/Expanding_Codes_with_Polynomial_Stretch.