Appendix E — every low-degree solution of the key equation has
ProvedFuzzyExtractors.EditSketch.appendix_E_ratio_uniqueLet be a finite field of characteristic , , and with ; let , and be the error locator, error evaluator and syndrome polynomial of . Suppose and are polynomials of degree at most with
Then , that is,
This is the uniqueness step of the decoding argument: any low-degree solution of the key equation determines the reduced fraction , hence the error locator (the solution with constant term and coprime to ).
Formalization Note. The ratio identity is stated cross-multiplied. The paper writes for the second unknown polynomial; it is (a misprint of the Greek letter, not the string ). "Nonzero solution" is read as ; given the congruence and the degree bounds, a solution with forces , so this is the same as asking the pair to be nonzero. The weight bound is the standing assumption of Lemma E.1(2). The designed distance is positive; at the congruence modulo is vacuous and the conclusion can fail. Degree bounds use natDegree with integer division .
import Mathlib import Definitions.Def_FuzzyExtractors_EditSketch_Basic
namespace FuzzyExtractors.EditSketch
open Polynomial in
theorem appendix_E_ratio_unique {K : Type} [Field K] [Fintype K] [DecidableEq K] [CharP K 2]
(δ : ℕ) (hδ : 1 ≤ δ) (M : Finset Kˣ) (hM : M.card ≤ (δ - 1) / 2)
(σ' ω' : K[X]) (hσ' : σ' ≠ 0)
(hdegσ : σ'.natDegree ≤ (δ - 1) / 2) (hdegω : ω'.natDegree ≤ (δ - 1) / 2)
(hcong : X ^ δ ∣ synPoly δ M * σ' - ω') :
omega M * σ' = sigma M * ω' := by sorry
end FuzzyExtractors.EditSketch
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.