Fact 2.10 — the (d+1)-th alternating difference of a polynomial of degree at most d vanishes
ProvedLowRankShifts.MatPoly.fact_2_10p2o-gran-per-chapterp2o-plan-paperp2o-v1polynomialsworst-case-to-average-case
Let be any field, a commutative polynomial of total degree at most , and . Then
This identity is what makes a low-degree function locally correctable: the value at is a signed sum of the values at the points , . Lemma 2.11 and Corollary 2.12 rest on it.
Formalization Note. is an MvPolynomial (Fin ℓ) F with totalDegree ≤ d; is Fin (d + 1).
Differences from the source:
- encoding: [d+1] = {1, …, d+1} and S ⊆ [d+1] →
Fin (d + 1)andS : Finset (Fin (d + 1)); reason: 0-based indices; the same sum - encoding: f ∈ F[x_1, …, x_ℓ] with degree at most d →
f : MvPolynomial (Fin ℓ) Fwithf.totalDegree ≤ d; reason: Mathlib's multivariate polynomials; the same objects
Preamble
import Mathlib set_option autoImplicit false
Formal statement
namespace LowRankShifts.MatPoly
/-- Fact 2.10 (p. 13): for any field `F`, any commutative polynomial `f ∈ F[x_1, …, x_ℓ]` of total
degree at most `d`, and any `x, a_1, …, a_{d+1} ∈ F^ℓ`,
`Σ_{S ⊆ [d+1]} (−1)^{|S|} f(x + Σ_{i∈S} a_i) = 0`. -/
theorem fact_2_10 {F : Type*} [Field F] {ℓ d : ℕ} (f : MvPolynomial (Fin ℓ) F)
(hf : f.totalDegree ≤ d) (x : Fin ℓ → F) (a : Fin (d + 1) → Fin ℓ → F) :
∑ S : Finset (Fin (d + 1)),
(-1 : F) ^ S.card * MvPolynomial.eval (x + ∑ i ∈ S, a i) f = 0 := by sorry
end LowRankShifts.MatPoly
Source
Golovnev, Nagargoje, Shinkar, Singh, Stephens-Davidowitz, Worst-Case to Average-Case Reductions for Linear Algebra: Optimal, Simple, and General, STOC 2027 submission (manuscript sha256 ebcf9677…), p. 13 (PDF 16), Fact 2.10
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.