Correctness and time bound of the canonical rank program
ProvedExpandingCodes.Computation.GaussianDriver.rankProgram_stops_canonicalcoding-theorycomplexity-theoryexpanding-codes-polynomial-stretch
Fix a point dimension , an input size , and a binary word of length . Let be a Gaussian-program store satisfying the common field, size and workspace invariant with bound . Assume buffer zero contains the canonical encoded binary test table for and buffer one contains an arbitrary workspace table. Let be any input.
The finite rank program has an execution to satisfying
Here is the specified field size and is the canonical auxiliary-monomial evaluation matrix. The common invariant is preserved, register 62 is zero, and the read heads and output are unchanged. This certifies the physical Gaussian-elimination stage used by the rank test.
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryRuntime set_option autoImplicit false open scoped Classical open NKtLB
Formal statement
theorem ExpandingCodes.Computation.GaussianDriver.rankProgram_stops_canonical (degree n M : ℕ) (inp : Inputs) (d : ExpandingCodes.Computation.GaussianProgram.Store)
(y : ExpandingCodes.PolynomialStretch.Word (ExpandingCodes.PolynomialStretch.rowCount degree n))
(hc : ExpandingCodes.Computation.GaussianDriver.Common (ExpandingCodes.PolynomialStretch.fieldExponent degree n) (ExpandingCodes.PolynomialStretch.fieldExponent_pos degree n) (ExpandingCodes.PolynomialStretch.rowCount degree n) M d)
(B : ExpandingCodes.Computation.Gaussian.Table (Fin (ExpandingCodes.PolynomialStretch.fieldSize degree n)) (ExpandingCodes.PolynomialStretch.rowCount degree n) (ExpandingCodes.PolynomialStretch.rowCount degree n))
(ha : ExpandingCodes.Computation.GaussianProgram.MatrixStored d 0 (ExpandingCodes.PolynomialStretch.binaryTestTable degree n y)) (hb : ExpandingCodes.Computation.GaussianProgram.MatrixStored d 1 B) :
∃ (t : ℕ) (e : ExpandingCodes.Computation.TapeCfg 64 2 4260),t ≤ 100000*(M+1)^9 ∧
ExpandingCodes.Computation.GaussianDriver.rankProgram.Stops inp (d.toCfg ExpandingCodes.Computation.GaussianDriver.rankProgram.entry) t e ∧
ExpandingCodes.Computation.GaussianDriver.Common (ExpandingCodes.PolynomialStretch.fieldExponent degree n) (ExpandingCodes.PolynomialStretch.fieldExponent_pos degree n) (ExpandingCodes.PolynomialStretch.rowCount degree n) M e.store ∧
e.reg 48 = (ExpandingCodes.PolynomialStretch.testMatrix (ExpandingCodes.PolynomialStretch.binaryGeometry degree n) y).rank ∧
e.reg 62 = 0 ∧ e.roHead = d.roHead ∧ e.output = d.output := 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.GaussianDriverBounds. Supporting formal implementation contract, rather than a verbatim statement in the paper. Exact local source: ExpandingCodes/Computation/GaussianDriverBounds.lean, declaration ExpandingCodes.Computation.GaussianDriver.rankProgram_stops_canonical; source file SHA256 21ac36267db9cb35247b70f64f4de0e4809631950f41bd79dad4d7348ddc0b7c. The public construction is at https://prove2.me/missions/Expanding_Codes_with_Polynomial_Stretch.