The Koszul-flattening certificate for paired clusters #
This file proves the paired-cluster lemma of the program for border rank (7/3 - o(1)) m of
explicit tensors in the setting of Landsberg and Michałek, Towards finding hay in a haystack,
Theory of Computing 2025: a positive and a negative cluster of 2p + 1 slices of the weighted
Landsberg–Michałek tensor, identified slice by slice, have a Koszul flattening of rank about
(2p+1).choose p * Φ, where Φ exceeds what either cluster certifies alone. The single-cluster
certificate is in Complexitylib.Algebraic.LinearAlgebra.Tensor.Diagonal.
The statement #
Let T = weightedLMTensor k with n = m = 2k + 1. Its slice a is supported on the diagonal of
offset a - k. A positive cluster c⁺ : Fin (2p+1) → Fin (2k+1) is strictly monotone with
offsets o⁺ = c⁺ - k in [1, k], diameter at most L, pairwise distinct p-subset sums, and
median offset r = o⁺ p; a negative cluster c⁻ is the same with offsets in [-k, -1] and
median -s. The paired projection selectSlices c⁺ + selectSlices c⁻ sums the slices c⁺ t
and c⁻ t into the slice t, so V = map (selectSlices c⁺ + selectSlices c⁻) 1 1 T is the sum
of the two cluster tensors (Tensor3.map_add_selectSlices_weightedLMTensor), it is unchanged by
first zeroing slices outside the clusters (Tensor3.map_add_selectSlices_map_diagonal), and its
Koszul flattening is the sum of theirs (Tensor3.koszulFlattening_map_add_left). With
z = r + s,
rank V_A^{∧p} ≥ (2p+1).choose p * (W - 8 (p + 1) L), where
W = r + s + min s (n - r - z) + min r (n - s - z)
(Tensor3.choose_mul_le_rank_koszulFlattening_pairedClusters, truncated subtraction), and
W ≥ max z (2 min z (n - z)) (Tensor3.max_le_pairedWidth). No lower bound on r or s is
needed. By the Koszul-flattening
bound after the paired projection, the same quantity is at most borderRank T' * (2p).choose p
for T' the tensor T with some slices outside both clusters zeroed
(Tensor3.choose_mul_le_borderRank_mul_map_diagonal_pairedClusters,
Tensor3.choose_mul_le_borderRank_mul_restrictSlices_pairedClusters). Combined with the
single-cluster bounds n - r - pL and n - s - pL, this gives
(2p+1)/(p+1) * (Φ_n(r, s) - 8 (p + 1) L) ≤ borderRank (T restricted to S),
Φ_n(r, s) = max {n - r, n - s, r + s, 2 min (r + s, n - r - s)} (DeletionGame.phi),
for every set S of slices containing both clusters
(Tensor3.div_mul_phi_sub_le_borderRank_restrictSlices; over ℤ with the denominator cleared,
Tensor3.choose_mul_phi_sub_le_borderRank_mul_restrictSlices).
Labels in a window #
Only the labels inside one single-cluster block matter: the diagonal blocks of the minor are
single-cluster blocks, whose columns differ by at most the p-subset spread, at most p L
(Tensor3.subsetSumSpread_le). So all of the above holds for T_k(γ) with
γ a j = 2^{2^{e a j}} whenever the labels e separate positions (a, j), (a', j') with
|a - a'| ≤ L and |j - j'| ≤ p L
(Tensor3.choose_mul_le_rank_koszulFlattening_pairedClusters_lmTensor,
Tensor3.div_mul_phi_sub_le_borderRank_restrictSlices_lmTensor). The global labels
a (2k + 1) + j of weightedLMTensor k separate all positions; periodic labels
(Tensor3.periodicLMTensor) separate the positions of a window and keep the entries in a
finite set independent of k.
The proof: two tiles #
Index the columns of the Koszul flattening by positions j and the rows by ℓ, both in
[0, n). A single-cluster block of shift w uses the columns (I, w + ∑_I o) and the rows
(σ I, w + ∑_{σ I} o); for monotone offsets with median ρ and diameter L its columns lie
within pL of a center x and its rows within pL of x + ρ. A positive column at x
therefore meets rows near x + r (through the positive slices) and near x - s (through the
negative ones); a negative column at x meets rows near x - s and x + r.
Choose blocks with centers in four tiles, each shrunk by the margin μ = (p + 1) L at both
ends: positive blocks with centers in P1 = [0, s) and P2 = [z, z + s) (rows in
[r, z) and [z + r, 2z)), negative blocks with centers in N1 = [s, z) and
N2 = [z + s, 2z) (rows in [0, r) and [z, z + r)), all cut to [0, n). The positive
system (columns P1 ∪ P2) and the negative system (columns N1 ∪ N2) never meet: a positive
column hits the rows of P1 or P2, a negative column those of N1 or N2. The only cross
entries go from P2 columns to P1 rows (shift -s) and from N1 columns to N2 rows
(shift +r). In the order P1 < P2 < N2 < N1 the minor is block triangular
(Matrix.card_mul_card_le_rank_of_det_blocks_ne_zero_of_lt), with the blocks of single shifts as
diagonal blocks. Inside such a block the other cluster's entries vanish exactly, since they
would need o⁺ t = o⁻ t, so it is the nonsingular single-cluster block. The tiles have widths
s, min s (n - r - z), min r (n - s - z) and r, each less 2μ; their sum is W - 8μ.
When 2z ≤ n both tiles fit and W = 2z; when 2z > n the second tile is cut by n and
W ≥ 2 (n - z). The general certificate for several clusters identified slicewise is
Tensor3.choose_mul_card_le_rank_koszulFlattening_sum_weightedShifts, and the two-tile bound
for weighted shifts is Tensor3.choose_mul_le_rank_koszulFlattening_add_weightedShifts.
The sketch of this argument first claimed that the interactions between two copies of a one-tile square run in one direction; for that partition they do not. The decomposition above, which separates the positive and negative systems, replaces it.
Block-triangular minors. Choose, for each block b : β, rows f i b and columns
g i b of A indexed by i : ι. If every entry from a block b to a block b' with
v b' < v b vanishes, for an injective v into a linear order, and every block
A.submatrix (f · b) (g · b) is nonsingular, then card ι * card β ≤ rank A.
Koszul linearity. The Koszul flattening of (X + X') ⊗ Y ⊗ Z applied to T is the sum
of those of X ⊗ Y ⊗ Z and X' ⊗ Y ⊗ Z.
The paired projection ignores the other slices. Scaling slices by d and then summing
the slices cP t and cN t gives the same tensor as summing them directly, when d = 1 on
both clusters.
The single-cluster certificate on a window of shifts. Let the offsets o of 2p + 1
slices have pairwise distinct p-subset sums and the weights be g t j = 2^{2^{e t j}} with
labels e injective on positions whose columns differ by at most subsetSumSpread p o. For
pairwise
distinct shifts w q whose positions w q + ∑_{t ∈ K} o t lie in [0, m) for all subsets K
of size p or p + 1, the Koszul flattening of weightedShifts o g has rank at least
(2p+1).choose p * card Q: the columns (I, w q + ∑_I o) and rows (σ I, w q + ∑_{σ I} o)
form a block-diagonal minor.
Several clusters on one slice space. Let o b (b : κ) be offsets of 2p + 1 slices
with pairwise distinct p-subset sums and weights g b t j = 2^{2^{e b t j}} as in
choose_mul_card_le_rank_koszulFlattening_weightedShifts_of_shifts, with o b t ≠ o b' t for
b ≠ b'. Let each block q : Q have a cluster c q and a shift w q whose positions lie in
[0, m), and let v order the blocks. If no entry of the Koszul flattening goes from the rows
(insert t I, w q + ∑_{insert t I} o (c q)) of a block q to the columns
(I, w q' + ∑_I o (c q')) of an earlier block q' (v q' < v q) through the slice t of any
cluster b, then the Koszul flattening of ∑ b, weightedShifts (o b) (g b) has rank at least
(2p+1).choose p * card Q.
The two-tile certificate for weighted shifts. Let oP and oN be monotone offsets of
2p + 1 slices with medians oP p = r and oN p = -s, diameters at most L, pairwise
distinct p-subset sums, and oP t ≠ oN t for every t, and let the weights be 2^{2^{e}}
with labels injective on positions whose columns differ by at most p L (which bounds the
p-subset spread). If r + s ≤ m, the Koszul flattening of
weightedShifts oP gP + weightedShifts oN gN has rank at least (2p+1).choose p times
r + s + min s (m - r - (r + s)) + min r (m - s - (r + s)) - 8 (p + 1) L.
The paired projection. Summing the slices cP t and cN t of the weighted
Landsberg–Michałek tensor gives the sum of the two cluster tensors.
The paired projection of T_k(γ). Summing the slices cP t and cN t of T_k(γ)
gives the sum of the two cluster tensors.
The paired-cluster Koszul certificate for T_k(γ) with window labels. Let
γ a j = 2^{2^{e a j}} with labels e that separate positions (a, j), (a', j') with
|a - a'| ≤ L and |j - j'| ≤ p L. Under the hypotheses of
choose_mul_le_rank_koszulFlattening_pairedClusters, the Koszul flattening of the paired
projection of T_k(γ) has rank at least (2p+1).choose p * (W - 8 (p + 1) L), where
W = r + s + min s (2k + 1 - r - (r + s)) + min r (2k + 1 - s - (r + s)).
The paired-cluster Koszul certificate. Let cP be a strictly monotone positive cluster
(cP 0 > k) with median offset cP p - k = r, and cN a strictly monotone negative cluster
(cN (2p) < k) with median offset cN p - k = -s, both of diameter at most L and with
pairwise distinct p-subset sums of offsets. Then the Koszul flattening of the paired
projection of weightedLMTensor k has rank at least (2p+1).choose p * (W - 8 (p + 1) L),
where W = r + s + min s (2k + 1 - r - (r + s)) + min r (2k + 1 - s - (r + s)).
Border rank from paired clusters, with some slices zeroed. Under the hypotheses of
choose_mul_le_rank_koszulFlattening_pairedClusters, if d = 1 on both clusters (for instance
the indicator of a set of slices containing them), then
(2p+1).choose p * (W - 8 (p + 1) L) ≤ borderRank ((diagonal d ⊗ 1 ⊗ 1) T) * (2p).choose p
for T = weightedLMTensor k.
Border rank from paired clusters, for a restriction to a set of slices. Under the
hypotheses of choose_mul_le_rank_koszulFlattening_pairedClusters, for every set S of slices
containing both clusters,
(2p+1).choose p * (W - 8 (p + 1) L) ≤ borderRank (T restricted to S) * (2p).choose p.
The paired width dominates the two-tile terms. With z = r + s,
max z (2 min z (n - z)) ≤ W = z + min s (n - r - z) + min r (n - s - z): when 2z ≤ n both
tiles fit and W = 2z; otherwise W ≥ 2 (n - z).
The combined paired-cluster bound, denominator cleared. For every set S of slices and
strictly monotone clusters cP, cN contained in S, with pairwise distinct p-subset sums
of offsets, diameters at most L, offsets of cP in [1, k] and of cN in [-k, -1], and
medians r = clusterOffsets k cP p and -s = clusterOffsets k cN p,
(2p+1).choose p * (Φ_{2k+1}(r, s) - 8 (p + 1) L) ≤ borderRank (T restricted to S) * (2p).choose p.
The combined paired-cluster bound. For every set S of slices of
T = weightedLMTensor k and strictly monotone clusters cP, cN : Fin (2p+1) → Fin (2k+1)
contained in S, with pairwise distinct p-subset sums of offsets, diameters at most L,
offsets of cP in [1, k] and of cN in [-k, -1], and medians
r = clusterOffsets k cP p and -s = clusterOffsets k cN p,
(2p+1)/(p+1) * (Φ_{2k+1}(r, s) - 8 (p + 1) L) ≤ borderRank (T restricted to S), where
Φ_n(r, s) = max {n - r, n - s, r + s, 2 min (r + s, n - r - s)} (DeletionGame.phi). There is
no condition on k, p, or L.
The combined paired-cluster bound for T_k(γ) with window labels, denominator
cleared. Let γ a j = 2^{2^{e a j}} with labels e that separate positions (a, j),
(a', j') with |a - a'| ≤ L and |j - j'| ≤ p L. Under the hypotheses of
choose_mul_phi_sub_le_borderRank_mul_restrictSlices,
(2p+1).choose p * (Φ_{2k+1}(r, s) - 8 (p + 1) L) ≤ borderRank (T_k(γ) restricted to S) * (2p).choose p.
The combined paired-cluster bound for T_k(γ) with window labels. Let
γ a j = 2^{2^{e a j}} with labels e that separate positions (a, j), (a', j') with
|a - a'| ≤ L and |j - j'| ≤ p L. Under the hypotheses of
div_mul_phi_sub_le_borderRank_restrictSlices,
(2p+1)/(p+1) * (Φ_{2k+1}(r, s) - 8 (p + 1) L) ≤ borderRank (T_k(γ) restricted to S). The
labels need not be distinct outside the window, so they can be periodic
(Tensor3.periodicLMTensor).