One finite polynomial-time machine for the expanding-code rank test
ProvedExpandingCodes.PolynomialStretch.binary_tester_implementation_sourcecoding-theorycomplexity-theoryexpanding-codes-polynomial-stretch
Let be rational and use the specified binary-field geometry in dimension . There are one finite deterministic machine , integers , , and , depending on and independent of the input size and received word, such that for every and binary word of length ,
The test is the canonical finite-field Gram-matrix rank predicate, with its specified row ordering and input/output encodings. This supplies the operational deterministic-testing clause of the efficient-family theorem.
Preamble
import Definitions.Def_ExpandingCodes_PolynomialStretch_BinaryRuntime set_option autoImplicit false open scoped Classical open ExpandingCodes.PolynomialStretch
Formal statement
theorem ExpandingCodes.PolynomialStretch.binary_tester_implementation_source (θ : ℚ)
(hθ : 0 < (θ : ℝ) ∧ (θ : ℝ) < 1/2) :
TesterImplementation θ (fun n => binaryGeometry (dimension (θ : ℝ)) n) := by sorry
Source
Isaac M Hair and Amit Sahai, Expanding Codes with Polynomial Stretch, user-supplied 824.pdf, Section 2, Theorem 2.1 (pp. 7-9), https://prove2.me/missions/Expanding_Codes_with_Polynomial_Stretch. Machine-level implementation details were developed in the accompanying Lean formalization; the checked local proof archive has SHA256 694ed62f8511cd5a41c6354a96349e0a72f820296592e4f312215e403a2722d5. Section 2.2, equation (5) and the following displayed rank test, p. 9; formal implementation endpoint ExpandingCodes/Computation/TesterImplementation.lean, binary_tester_implementation_source.