Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The tensor SnS_nSn​ of Definition 5.1 and the Vandermonde products ΔS\Delta_SΔS​

Definition
ExplicitTensorBarrier694_Explicit_Supplement_OddWitness

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

complexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-border-rank

Let n=2p+1n=2p+1n=2p+1. Following Definition 5.1, let A=CnA=\mathbb C^nA=Cn with basis a1,…,ana_1,\dots,a_na1​,…,an​, identify B∗B^*B∗ with the polynomials C[t]<n\mathbb C[t]_{<n}C[t]<n​ of degree less than nnn, and put C=Cp+1⊕CpC=\mathbb C^{p+1}\oplus\mathbb C^pC=Cp+1⊕Cp. For vq(t)=(1,t,…,tq−1)Tv_q(t)=(1,t,\dots,t^{q-1})^Tvq​(t)=(1,t,…,tq−1)T define

Sn=∑i=1nai⊗Xi,Xi(f)=f(i) vp+1(i)⊕f′(i) vp(i),S_n=\sum_{i=1}^n a_i\otimes X_i,\qquad X_i(f)=f(i)\,v_{p+1}(i)\oplus f'(i)\,v_p(i),Sn​=i=1∑n​ai​⊗Xi​,Xi​(f)=f(i)vp+1​(i)⊕f′(i)vp​(i),

where Xi∈B⊗C=Hom(B∗,C)X_i\in B\otimes C=\mathrm{Hom}(B^*,C)Xi​∈B⊗C=Hom(B∗,C). In coordinates, with the monomial basis t0,…,tn−1t^0,\dots,t^{n-1}t0,…,tn−1 of B∗B^*B∗ (and the dual basis of BBB), the entry of SnS_nSn​ at (ai,tu,w)(a_i,t^u,w)(ai​,tu,w) is the www-th coordinate of Xi(tu)X_i(t^u)Xi​(tu): iuiwi^{u}i^{w}iuiw for w<p+1w<p+1w<p+1 and u iu−1iw−p−1u\,i^{u-1}i^{w-p-1}uiu−1iw−p−1 for p+1≤w<2p+1p+1\le w<2p+1p+1≤w<2p+1. The evaluation points are 1,…,n1,\dots,n1,…,n.

For a finite set SSS of positive integers, ΔS=∏i<j, i,j∈S(j−i)\Delta_S=\prod_{i<j,\ i,j\in S}(j-i)ΔS​=∏i<j, i,j∈S​(j−i), with the empty product equal to 111.

SnS_nSn​ is the tensor whose central Koszul flattening is invertible (Theorem 5.2); ΔS\Delta_SΔS​ enters Lemma 5.3.

Formalization Note The index i∈{0,…,n−1}i\in\{0,\dots,n-1\}i∈{0,…,n−1} of Fin n stands for the point i+1i+1i+1; the first p+1p+1p+1 coordinates of CCC form the summand Cp+1\mathbb C^{p+1}Cp+1. For u=0u=0u=0 the derivative coordinate is 000.

Definition code
import Mathlib
import Definitions.Def_ExplicitTensorBarrier694_Explicit_Tensors

open scoped BigOperators

namespace ExplicitTensorBarrier694.Explicit.Supplement

open ExplicitTensorBarrier694.Explicit

/-- Definition 5.1, equation (5.1), p.15, with n = 2p+1. Coordinates: A = ℂⁿ with basis
a_1,…,a_n (index `i : Fin n` is the point i+1); B* = ℂ[t]_{<n} with the monomial basis
t^0,…,t^{n−1} (column index `u`, the dual basis of B); C = ℂ^{p+1} ⊕ ℂ^p (index `w`, the
first p+1 coordinates are the first summand). The entry (i,u,w) is the w-th coordinate of
X_i(t^u) = (t^u)(i) v_{p+1}(i) ⊕ (t^u)'(i) v_p(i), v_q(t) = (1,t,…,t^{q−1}). Evaluation
points are 1,…,n. For u = 0 the derivative coordinate is 0 (the factor u vanishes). -/
noncomputable def oddWitness (p : ℕ) : Tensor (2 * p + 1) (2 * p + 1) (2 * p + 1) :=
  fun i u w =>
    let x : ℂ := ((i : ℕ) : ℂ) + 1
    if (w : ℕ) < p + 1 then x ^ (u : ℕ) * x ^ (w : ℕ)
    else ((u : ℕ) : ℂ) * x ^ ((u : ℕ) - 1) * x ^ ((w : ℕ) - (p + 1))

/-- Δ_S = ∏_{i<j, i,j ∈ S} (j − i), p.15, for a finite set S of natural numbers (used for
S ⊆ [n] = {1,…,n}); the empty product is 1. -/
def vandermondeDelta (S : Finset ℕ) : ℂ :=
  ∏ i ∈ S, ∏ j ∈ S.filter (fun j => i < j), ((j : ℂ) - (i : ℂ))

end ExplicitTensorBarrier694.Explicit.Supplement
Source
Benjamin Lovitz, STOC 2027 submission #694 (October 2026), Definition 5.1, equation (5.1), p.15, and the definition of Δ_S, p.15 (PDF same); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/694.pdf

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me