Lemma 8.7 — forces multiplicity of as a root of
ProvedQuadExt.Main.lemma_8_7linear-algebrap2o-gran-per-chapterp2o-plan-paperp2o-v1polynomial-matrices
Let be a field and a matrix of polynomials with . If satisfies , then is a root of of multiplicity at least :
In the proof of Theorem 8.5 this converts "many bad field elements" into "a determinant polynomial with too many roots".
Differences from the source:
- encoding: → computed in , a natural number; reason: avoids truncated subtraction (for the claim is trivial either way).
Preamble
import Mathlib
Formal statement
namespace QuadExt.Main
open Polynomial in
/-- **Lemma 8.7** (p. 28): if `P(t) ∈ F[t]^{k×k}` has non-zero determinant and `β ∈ F` has
`rank_F P(β) ≤ r`, then `β` is a root of `det P(t)` of multiplicity at least `k − r`. -/
theorem lemma_8_7 {F : Type} [Field F] (k r : ℕ) (P : Matrix (Fin k) (Fin k) F[X])
(hP : P.det ≠ 0) (β : F) (hrank : (P.map fun q => q.eval β).rank ≤ r) :
(k : ℤ) - r ≤ (P.det.rootMultiplicity β : ℤ) := by sorry
end QuadExt.Main
Source
Chandrasekaran, Goodman, Zuckerman, Quadratic Extractors, STOC 2027 submission (manuscript sha256 ddc80a9a…), p. 28 (PDF 29), Lemma 8.7
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.