Lemma 5.3 — for vanishing on
OpenExplicitTensorBarrier694.Explicit.Supplement.lemma_5_3complexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-border-rank
Let and , and write . For let (empty product ). If a complex polynomial of degree less than vanishes at every point of a -element subset , then
where is the derivative of .
This interpolation identity is used in the proof of Theorem 5.2. This is a paper-proved result awaiting a formal proof.
Differences from the source:
- encoding: ℂ[t]_{<n} → Polynomial.degreeLT ℂ (2p+1); reason: the same space; the zero polynomial is included
- encoding: (p+1)-subsets S ⊆ [n] → S : Finset ℕ with S ⊆ Icc 1 (2p+1) and card S = p+1; reason: the same sets of integers, used as complex evaluation points
Preamble
import Mathlib import Definitions.Def_ExplicitTensorBarrier694_Explicit_Supplement_OddWitness open scoped BigOperators open Polynomial
Formal statement
namespace ExplicitTensorBarrier694.Explicit.Supplement
/-- Lovitz, STOC 2027 submission #694 (October 2026), Lemma 5.3, p.16 (standing context
of §5, p.15: n = 2p+1 ≥ 3, [n] = {1,…,n}). If f ∈ ℂ[t]_{<n} vanishes on a (p+1)-subset
S ⊆ [n], then Σ_{i∈S} Δ²_{S∖{i}} f′(i) = 0. -/
theorem lemma_5_3 (p : ℕ) (hp : 1 ≤ p) (f : ℂ[X])
(hf : f ∈ Polynomial.degreeLT ℂ (2 * p + 1))
(S : Finset ℕ) (hS : S ⊆ Finset.Icc 1 (2 * p + 1)) (hcard : S.card = p + 1)
(hvan : ∀ i ∈ S, f.eval (i : ℂ) = 0) :
∑ i ∈ S, vandermondeDelta (S.erase i) ^ 2 * (derivative f).eval (i : ℂ) = 0 := by sorry
end ExplicitTensorBarrier694.Explicit.Supplement
Source
Benjamin Lovitz, STOC 2027 submission #694 (October 2026), Lemma 5.3, p.16; standing context of §5 and Δ_S, p.15 (PDF same); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/694.pdf