Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Linear flattenings: ρ(L)\rho(L)ρ(L), potency Pot(L)\mathrm{Pot}(L)Pot(L), optimal potency Π(n)\Pi(n)Π(n), and Schatten norms

Definition
ExplicitTensorBarrier694_Explicit_Supplement_Flattening

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≥0n\ge0n≥0 and let FFF be a map from tensors T∈(Cn)⊗3T\in(\mathbb C^n)^{\otimes3}T∈(Cn)⊗3 to complex matrices (rows and columns indexed by finite sets). Following equation (1.2) of the source define

ρ(F)=max⁡x,y,z∈Cnrank⁡F(x⊗y⊗z),Pot(F)=max⁡Trank⁡F(T)ρ(F).\rho(F)=\max_{x,y,z\in\mathbb C^n}\operatorname{rank}F(x\otimes y\otimes z),\qquad \mathrm{Pot}(F)=\frac{\max_T\operatorname{rank}F(T)}{\rho(F)}.ρ(F)=x,y,z∈Cnmax​rankF(x⊗y⊗z),Pot(F)=ρ(F)maxT​rankF(T)​.

Both maxima exist: the rank sets are nonempty and bounded by the number of columns. A linear flattening is a nonzero C\mathbb CC-linear map L:(Cn)⊗3→Matu,v(C)L:(\mathbb C^n)^{\otimes3}\to\mathrm{Mat}_{u,v}(\mathbb C)L:(Cn)⊗3→Matu,v​(C) with arbitrary positive u,vu,vu,v; for it ρ(L)≥1\rho(L)\ge1ρ(L)≥1 because pure tensors span. The optimal potency is

Π(n)=sup⁡{Pot(L):u,v≥1, L≠0 linear},\Pi(n)=\sup\{\mathrm{Pot}(L): u,v\ge1,\ L\neq0\text{ linear}\},Π(n)=sup{Pot(L):u,v≥1, L=0 linear},

with no restriction on u,vu,vu,v. The module also defines M(x,y,z)=∑ijkxiyjzkMijkM(x,y,z)=\sum_{ijk}x_iy_jz_kM_{ijk}M(x,y,z)=∑ijk​xi​yj​zk​Mijk​ for a family of r×rr\times rr×r matrices, the squared Schatten 2-norm ∥X∥22=∑a,b∣Xab∣2=tr⁡(XX†)\|X\|_2^2=\sum_{a,b}|X_{ab}|^2=\operatorname{tr}(XX^\dagger)∥X∥22​=∑a,b​∣Xab​∣2=tr(XX†) and the fourth power of the Schatten 4-norm ∥X∥44=tr⁡((X†X)2)=∑jσj(X)4\|X\|_4^4=\operatorname{tr}((X^\dagger X)^2)=\sum_j\sigma_j(X)^4∥X∥44​=tr((X†X)2)=∑j​σj​(X)4.

These are the objects of Theorem 1.2 and its supporting Lemmas 4.1 and 4.2.

Formalization Note Π(n)\Pi(n)Π(n) is an EReal supremum, so an unbounded potency set would give +∞+\infty+∞ and not a junk real value. ρ\rhoρ and Pot\mathrm{Pot}Pot are defined for maps into matrices over arbitrary finite index types, so the Koszul matrices of the published Koszul definition (indexed by exterior bases) use the same ρ\rhoρ and Pot\mathrm{Pot}Pot; for the Koszul flattening ρ\rhoρ coincides with the published koszulRho. The trace in ∥X∥44\|X\|_4^4∥X∥44​ is of a positive semidefinite matrix and its real part is taken.

Definition code
import Mathlib
import Definitions.Def_ExplicitTensorBarrier694_Explicit_Tensors

open scoped BigOperators Matrix

namespace ExplicitTensorBarrier694.Explicit.Supplement

open ExplicitTensorBarrier694.Explicit

/-- ρ(L), equation (1.2), p.2: the largest rank of `F (x ⊗ y ⊗ z)` over ALL pure tensors
(zero factors allowed). The set is nonempty and bounded by the number of columns, so the
natural-number supremum is an attained maximum. Defined for any map to matrices over
finite index types, so that Koszul matrices (indexed by exterior bases) are covered by
the same definition as `Mat_{u,v}`-valued flattenings. -/
noncomputable def flatRho {n : ℕ} {ι κ : Type*} [Fintype κ]
    (F : Tensor n n n → Matrix ι κ ℂ) : ℕ :=
  sSup {r : ℕ | ∃ x y z : Fin n → ℂ, (F (pure x y z)).rank = r}

/-- max_T rank F(T), equation (1.2), p.2, over ALL tensors T; an attained maximum
(nonempty, bounded by the number of columns). -/
noncomputable def flatMaxRank {n : ℕ} {ι κ : Type*} [Fintype κ]
    (F : Tensor n n n → Matrix ι κ ℂ) : ℕ :=
  sSup {r : ℕ | ∃ T : Tensor n n n, (F T).rank = r}

/-- Potency Pot(F) = (max_T rank F(T)) / ρ(F), equation (1.2), p.2. For a nonzero linear
flattening ρ ≥ 1 (pure tensors span), so the real division is genuine. -/
noncomputable def potency {n : ℕ} {ι κ : Type*} [Fintype κ]
    (F : Tensor n n n → Matrix ι κ ℂ) : ℝ :=
  (flatMaxRank F : ℝ) / (flatRho F : ℝ)

/-- Optimal potency Π(n), p.2: the supremum of Pot(L) over ALL nonzero ℂ-linear maps
L : (ℂⁿ)^{⊗3} → Mat_{u,v}(ℂ) and ALL output dimensions u, v (no restriction). Computed
in `EReal`, so an unbounded family would give `⊤` rather than a junk real value. -/
noncomputable def optimalPotency (n : ℕ) : EReal :=
  ⨆ (u : ℕ) (v : ℕ) (L : Tensor n n n →ₗ[ℂ] Matrix (Fin u) (Fin v) ℂ) (_ : L ≠ 0),
    ((potency (⇑L) : ℝ) : EReal)

/-- The matrix Σ_{ijk} x_i y_j z_k M_{ijk} (no complex conjugation), §4, pp.11–12. -/
def coeffMatrix {n r : ℕ} (M : Fin n → Fin n → Fin n → Matrix (Fin r) (Fin r) ℂ)
    (x y z : Fin n → ℂ) : Matrix (Fin r) (Fin r) ℂ :=
  ∑ i, ∑ j, ∑ k, (x i * y j * z k) • M i j k

/-- Squared Schatten 2-norm (Hilbert–Schmidt): ‖X‖₂² = tr(X X†) = Σ |X_ab|², p.5. -/
noncomputable def schatten2Sq {ι κ : Type*} [Fintype ι] [Fintype κ]
    (X : Matrix ι κ ℂ) : ℝ :=
  ∑ a, ∑ b, ‖X a b‖ ^ 2

/-- Fourth power of the Schatten 4-norm: ‖X‖₄⁴ = Σ σ_j(X)⁴ = tr((X† X)²), p.5. The trace
is of a positive semidefinite matrix, hence real; its real part is taken. -/
noncomputable def schatten4Pow4 {ι κ : Type*} [Fintype ι] [Fintype κ]
    (X : Matrix ι κ ℂ) : ℝ :=
  (Matrix.trace ((Xᴴ * X) * (Xᴴ * X))).re

end ExplicitTensorBarrier694.Explicit.Supplement
Source
Benjamin Lovitz, STOC 2027 submission #694 (October 2026), equation (1.2) and the definition of Π(n), p.2; Schatten norms p.5; §4 pp.11–12 (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