The tensor of Definition 5.1 and the Vandermonde products
DefinitionExplicitTensorBarrier694_Explicit_Supplement_OddWitnesscomplexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-border-rank
Let . Following Definition 5.1, let with basis , identify with the polynomials of degree less than , and put . For define
where . In coordinates, with the monomial basis of (and the dual basis of ), the entry of at is the -th coordinate of : for and for . The evaluation points are .
For a finite set of positive integers, , with the empty product equal to .
is the tensor whose central Koszul flattening is invertible (Theorem 5.2); enters Lemma 5.3.
Formalization Note The index of Fin n stands for the point ; the first coordinates of form the summand . For the derivative coordinate is .
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