§6.2, p. 21 — the polynomial found in Step 3 of is unique
ProvedFuzzyExtractors.ImprovedJS.pLow_uniqueLet be a field, natural numbers, with , and any assignment of target values. If both have degree at most and each satisfies for at least points , then
This is the uniqueness half of the decoding step: the polynomial that looks for in Step 3 of Construction 5 is determined by its input.
Formalization Note. The paper's sentence reads "no two distinct polynomials of degree can get the correct on more than s"; the argument it gives ("else, they agree on at least points") and the use in Step 3 need at least , which is what is stated here. "At least " is doubled to , and "degree at most " is degree < s - t. The target values are arbitrary (in the application ). The paper leaves implicit; it is a hypothesis here.
import Mathlib import Definitions.Def_FuzzyExtractors_ImprovedJS_Basic open Polynomial
namespace FuzzyExtractors.ImprovedJS
/-- Construction 5 analysis (p. 21): two polynomials of degree at most s − t − 1 that each agree
with prescribed values b on at least s − t/2 points of an s-element set w′ (doubled:
2·#agreements ≥ 2s − t) are equal. -/
theorem pLow_unique {𝔽 : Type} [Field 𝔽] [DecidableEq 𝔽] (s t : ℕ) (hts : t ≤ s)
(w' : Finset 𝔽) (hw' : w'.card = s) (b : 𝔽 → 𝔽) (p₁ p₂ : 𝔽[X])
(hdeg₁ : p₁.degree < ((s - t : ℕ) : WithBot ℕ))
(hdeg₂ : p₂.degree < ((s - t : ℕ) : WithBot ℕ))
(hagree₁ : 2 * s - t ≤ 2 * (w'.filter fun x => p₁.eval x = b x).card)
(hagree₂ : 2 * s - t ≤ 2 * (w'.filter fun x => p₂.eval x = b x).card) :
p₁ = p₂ := by sorry
end FuzzyExtractors.ImprovedJS
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.