Breaking Pratt's Bound for Balanced Tripartition Tensors: R(P₃) ≤ 226, R(P₂) ≤ 28, and a Four-Cube Lemma

Pratt's balanced tripartition tensor P_n, the tensor of ordered partitions of a 3n-element set into three n-element blocks, is the bridge between Strassen's asymptotic rank conjecture and the Set Cover Conjecture: its asymptotic rank controls the running time of balanced tripartitioning and set cover algorithms. The previous upper bounds on its rank are Pratt's group construction R(P_n) ≤ 8ⁿ/2 and the partial-Fourier refinement of Flavi, Jelisiejew and Michałek, which gives 31 for P₂ and 247 for P₃. We prove R̲(P₃) ≤ 226 and R̲(P₂) ≤ 28. Both bounds come from explicit identities that write the cubic form of P_n as a sum of blocks ℓ(ℓw + pq), and every block has border rank four by a four-cube lemma: x(xw + pq) is the limit of four cubes. The identity for P₃ is invariant under the symmetric group S₇, uses 56 blocks indexed by the pairs and triples of a seven-element set plus one block of border rank two, and has rational coefficients 1/5, 2/5, 1/8, 1/200 and 1/2. Its proof reduces to 19 + 13 orbit checks that are listed in full. We further prove R̲(P₃) ≥ 150 and R(T₂,₂,₃) ≤ 55: the first from a Koszul–Young flattening whose 10584 × 10584 matrix has exact rank 10500, the second from a decomposition with entries 0, ±1 on two factors that beats the partial-Fourier bound 57; the B-part of the P₃ identity is itself a 56-term decomposition of T₂,₂,₃. On the side of group constructions we prove that no abelian group of order below 32 realises P₂ as a restriction of its group tensor, so Pratt's ℤ₂⁵ is optimal among abelian groups and the bound 28 lies beyond the reach of the method. A computational survey of the balanced type slices of W^⊗m for m = 4, …, 9 places every one of them at least 11.7 % below Pratt's bound and up to 15.6 %, including R(P₃) ≤ 240 and R̲(T₂,₂,₃) ≤ 54 numerically. Every exact statement comes with a verification script in rational or modular arithmetic; paper, scripts, certificates and numerical decompositions are included.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-10-13
DOI
https://doi.org/10.5281/zenodo.23333859
Primary Topic
Tensor decomposition and applications
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
preprint

Breaking Pratt's Bound for Balanced Tripartition Tensors: R(P₃) ≤ 226, R(P₂) ≤ 28, and a Four-Cube Lemma

David Tom Foss
Zenodo (CERN European Organization for Nuclear Research)
Tensor decomposition and applications
preprint

Breaking Pratt's Bound for Balanced Tripartition Tensors: R(P₃) ≤ 226, R(P₂) ≤ 28, and a Four-Cube Lemma

David Tom Foss
preprint en

Abstract

Pratt's balanced tripartition tensor P_n, the tensor of ordered partitions of a 3n-element set into three n-element blocks, is the bridge between Strassen's asymptotic rank conjecture and the Set Cover Conjecture: its asymptotic rank controls the running time of balanced tripartitioning and set cover algorithms. The previous upper bounds on its rank are Pratt's group construction R(P_n) ≤ 8ⁿ/2 and the partial-Fourier refinement of Flavi, Jelisiejew and Michałek, which gives 31 for P₂ and 247 for P₃. We prove R̲(P₃) ≤ 226 and R̲(P₂) ≤ 28. Both bounds come from explicit identities that write the cubic form of P_n as a sum of blocks ℓ(ℓw + pq), and every block has border rank four by a four-cube lemma: x(xw + pq) is the limit of four cubes. The identity for P₃ is invariant under the symmetric group S₇, uses 56 blocks indexed by the pairs and triples of a seven-element set plus one block of border rank two, and has rational coefficients 1/5, 2/5, 1/8, 1/200 and 1/2. Its proof reduces to 19 + 13 orbit checks that are listed in full. We further prove R̲(P₃) ≥ 150 and R(T₂,₂,₃) ≤ 55: the first from a Koszul–Young flattening whose 10584 × 10584 matrix has exact rank 10500, the second from a decomposition with entries 0, ±1 on two factors that beats the partial-Fourier bound 57; the B-part of the P₃ identity is itself a 56-term decomposition of T₂,₂,₃. On the side of group constructions we prove that no abelian group of order below 32 realises P₂ as a restriction of its group tensor, so Pratt's ℤ₂⁵ is optimal among abelian groups and the bound 28 lies beyond the reach of the method. A computational survey of the balanced type slices of W^⊗m for m = 4, …, 9 places every one of them at least 11.7 % below Pratt's bound and up to 15.6 %, including R(P₃) ≤ 240 and R̲(T₂,₂,₃) ≤ 54 numerically. Every exact statement comes with a verification script in rational or modular arithmetic; paper, scripts, certificates and numerical decompositions are included.

Zenodo (CERN European Organization for Nuclear Research)
Tensor decomposition and applications
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.