Three Disjoint Boolean Balls for Every Tripartition Tensor: Explicit Rank Decompositions, the Exact Rank of T(1,1,c), Depth-One Decompositions and Barriers at Rate 8

Abstract

We give an explicit rank decomposition of every tripartition tensor. For a, b, c ≥ 1 and N = a + b + c, the tensor T_{a,b,c} of ordered partitions of an N-set into an a-, a b- and a c-set satisfies, over every field of characteristic ≠ 2, R(T_{a,b,c}) ≤ 2^(N−1) − Σ_{r ∈ {a,b,c}} Σ_{k=0}^{r−2} C(N−1, k), with integer first and second factors and denominator 4 in the third. The identity has one term for every vertex of the Boolean cube {0,1}^(N−1) outside three disjoint Hamming balls of radii a−2, b−2, c−2, each factor removing its own ball; we prove that this is the most that lifting lower degrees and zeroing factors can remove. The two-ball form is a Boolean window: one term per vertex J with b−1 ≤ |J| ≤ a+b, that is, a+2 Johnson orbits with coefficients [|A∩J| = a−1] + (a−2)[|A∩J| = a] and the like, which beats the partial-Fourier bound of Flavi, Jelisiejew and Michałek by exactly Σ_{k=b−a−1}^{b−2} C(N−1, k). For a = 1 it is a three-orbit family with R(T_{1,b,c}) ≤ C(n,b−1) + C(n,b) + C(n,b+1), n = b+c, exactly C(n,b−2) below the partial-Fourier value, with relative saving → 1/4; for a = b = 1 it is sharp: R(T_{1,1,c}) = C(c+2,2) + 1 for every c, the lower bound because the span of the slices consists of symmetric matrices with zero diagonal and contains no rank-one matrix. For Pratt's balanced tensors the construction gives R(P₃) ≤ 229, R(P₄) ≤ 1847, R(P₅) ≤ 14 974 and R(P₆) ≤ 121 430, below the partial-Fourier values 247, 1981, 15 914 and 127 858, and R(T_{2,2,4}) ≤ 97, R(T_{2,3,3}) ≤ 111, R(T_{2,3,4}) ≤ 209, R(T_{3,3,4}) ≤ 446; the window certificates of all 41 tensors with N ≤ 11 and the reduced certificates were verified entry by entry (58 117 726 entries) by two independent exact checkers, one of them a Rust core in 128-bit integer arithmetic. The constructions were found by Wirkung, the author's discovery engine, in this order: a Young-ansatz search in class frames found T_{1,3,3} ≤ 50 and T_{1,4,4} ≤ 182 numerically; an isolation criterion (nullity of the Gauss–Newton matrix minus the gauge) and a sign gauge made them exact; the window {b−1, b, b+1} was read off and verified on ten more members before the closed form was proven; the Khatri–Rao rank test then found the linear redundancy of the a ≥ 2 window certificates (1 term for a = 2, N terms for a = 3) that the third ball explains. We also prove, as before, R̲(P₄) ≤ 1824 and R̲(P₅) ≤ 14 872 by depth-one decompositions, complementary pairs and torus ladders with rational slicing, and that rate 8 is forced for three large classes of decompositions: by the partition degree lemma every border decomposition of P_n contains a term depending on at least ⌊3n/2⌋ points, so depth-one decompositions in class frames with a bounded number of classes and decompositions with a symmetry group of subexponential index have rate 8, and a catalecticant bound gives the same for evaluation decompositions. Pratt's threshold for refuting the Set Cover Conjecture is 8^d C(3d,d) C(2d,d)/27^d ≥ (2/9)·8^d/d; it exceeds the flattening bound only from d = 11 on, where the three-ball value is 19.7 times the threshold, and every construction with one term per vertex of a band of layers of the Boolean cube that contains the middle layer, whatever its coefficients, stays a factor of order √N above it, which locates the remaining gap in the joint treatment of several distinguished points. All identities are verified coefficient by coefficient in exact arithmetic by scripts that do not use the search software, on up to 4 012 012 004 coefficients.