The Koszul-flattening certificate for one cluster of slices #
This file proves the single-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 lower bound for the Koszul flattening of the tensor formed by
2p + 1 slices of a weighted Landsberg–Michałek tensor, and the border-rank bound it gives.
The definitions are in Complexitylib.Algebraic.LinearAlgebra.Tensor.Diagonal.Defs.
The statement #
Let m = 2k + 1 and let c : Fin (2p+1) → Fin (2k+1) select 2p + 1 slices (a cluster)
of T_k(γ) (Tensor3.lmTensor), with offsets o t = c t - k (Tensor3.clusterOffsets). The
cluster tensor map (selectSlices c) 1 1 T_k(γ) is weightedShifts o (γ ∘ c): its slice t is
supported on the diagonal ℓ = j + o t. Suppose that
- the sums
∑_{t ∈ I} o tover thep-subsetsIofFin (2p+1)are pairwise distinct, and - the coefficients are
γ a j = 2^{2^{e a j}}with labelse (c t) jthat are injective on positions(t, j)whose columnsjdiffer by at most the spreadsubsetSumSpread p oof thep-subset sums∑_{t ∈ I} o t.
Then the Koszul flattening T_A^{∧p} of the cluster tensor has rank at least
(2p+1).choose p * (m - sumSpread p o)
(Tensor3.choose_mul_le_rank_koszulFlattening_lmTensor). The explicit coefficients
lmWeight k a j = 2^{2^{a (2k+1) + j}} satisfy the label condition for every injective c
(Tensor3.choose_mul_le_rank_koszulFlattening_weightedLMTensor). By the Koszul-flattening bound
after the projection onto the 2p + 1 cluster slices (denominator (2p).choose p),
(2p+1).choose p * (m - sumSpread p o) ≤ borderRank T * (2p).choose p for the weighted tensor
T = weightedLMTensor k, and also for T = map (diagonal d) 1 1 (weightedLMTensor k) whenever
d (c t) = 1 for all t, for instance when d is the indicator of a set of slices containing
the cluster and T is the tensor with the other slices zeroed
(Tensor3.choose_mul_le_borderRank_mul_map_diagonal_weightedLMTensor,
Tensor3.not_borderRankLE_map_diagonal_weightedLMTensor). Projecting such a restricted tensor
onto the cluster gives the same cluster tensor (Tensor3.map_selectSlices_map_diagonal).
For monotone offsets with median r = o p and diameter o (2p) - o 0 ≤ L, the spread is at
most |r| + p L (Tensor3.sumSpread_le, Tensor3.sumSpread_clusterOffsets_le), whatever the
signs of the offsets. The window of the labels is smaller: the p-subset spread is at most
p L, independent of the median (Tensor3.subsetSumSpread_le,
Tensor3.subsetSumSpread_clusterOffsets_le), and at most sumSpread p o
(Tensor3.subsetSumSpread_le_sumSpread). So labels need only be distinct on positions whose
columns differ by at most p L, which allows labels periodic in the column, with entries of
size independent of m (Tensor3.periodicLMTensor).
The proof #
- Grading. A nonzero entry of
T_A^{∧p}in column(I, j)and row(J, ℓ)hasJ = I ∪ {t}witht ∉ Iandℓ = j + o t, sow = j - ∑_I o = ℓ - ∑_J ois preserved. - Square minor. For each of the
m - sumSpread p ovalues ofwfor whichw + ∑_K o ∈ [0, m)for all subsetsKof sizeporp + 1, take the columns(I, w + ∑_I o)and the rows(σ I, w + ∑_{σ I} o), whereσis a bijection from thep-subsets to the(p + 1)-subsets withI ⊆ σ I. Such a perfect matching of the inclusion graph exists by Hall's theorem, since the graph is(p + 1)-regular on both sides. By the grading the minor is block diagonal (Matrix.card_mul_card_le_rank_of_det_blocks_ne_zero). - Blocks. A block entry is
0or±2^{2^{e (c t) (w + ∑_I o)}}forJ = I ∪ {t}. Its columnsw + ∑_I odiffer by at mostsubsetSumSpread p o, so the label condition and distinctp-subset sums make these labels distinct within a block, and the diagonal ofσis nonzero, so the block determinant is a nonempty sum∑ ±2^{E}with distinct exponentsE, which is nonzero (Matrix.det_ne_zero_of_two_pow_two_pow).
selectSlices c applied to the first factor keeps the slices c t.
diagonal d applied to the first factor scales the slice a by d a.
Scaling slices by d and then keeping the slices c t gives the same tensor as keeping them
directly, when d (c t) = 1 for every t.
The spread of a cluster. For monotone offsets o with median r = o p and diameter
o (2p) - o 0 ≤ L, the sums over subsets of size p or p + 1 spread over at most
|r| + p L. No sign condition on the offsets is needed.
The spread of a cluster of slices. For a monotone cluster c with median slice
c p (offset c p - k) and diameter c (2p) - c 0 ≤ L, the spread of its offsets is at most
|c p - k| + p L.
The p-subset spread is at most the spread over subsets of size p or p + 1.
The p-subset spread of a cluster of slices. For a monotone cluster c with diameter
c (2p) - c 0 ≤ L, the p-subset spread of its offsets is at most p L.
The single-cluster Koszul certificate for weighted shifts. Let o be offsets of
2p + 1 slices whose p-subset sums are pairwise distinct, and let the weights be
g t j = 2^{2^{e t j}} with labels e that are injective on positions whose columns differ
by at most the p-subset spread subsetSumSpread p o (at most sumSpread p o). Then the
Koszul flattening T_A^{∧p} of weightedShifts o g has rank at least
(2p+1).choose p * (m - sumSpread p o).
The cluster tensor of T_k(γ): keeping the slices c t of T_k(γ) gives the weighted
shifts with offsets c t - k and weights γ (c t).
The single-cluster Koszul certificate for T_k(γ). Let c select 2p + 1 slices of
T_k(γ) whose offsets c t - k have pairwise distinct p-subset sums, and let
γ a j = 2^{2^{e a j}} with labels e (c t) j injective on positions whose columns differ by
at most the p-subset spread. Then the Koszul flattening of the cluster tensor
map (selectSlices c) 1 1 T_k(γ) has rank at least
(2p+1).choose p * (2k + 1 - sumSpread p (clusterOffsets k c)).
The single-cluster Koszul certificate for the weighted Landsberg–Michałek tensor. If
c selects 2p + 1 distinct slices whose offsets c t - k have pairwise distinct p-subset
sums, the Koszul flattening of the cluster tensor of weightedLMTensor k has rank at least
(2p+1).choose p * (2k + 1 - sumSpread p (clusterOffsets k c)).
Border rank from one cluster, for T_k(γ) with some slices zeroed. Under the hypotheses
of choose_mul_le_rank_koszulFlattening_lmTensor, if d (c t) = 1 for every t (for instance
if d is the indicator of a set of slices containing the cluster), then
(2p+1).choose p * (2k + 1 - spread) ≤ borderRank ((diagonal d ⊗ 1 ⊗ 1) T_k(γ)) * (2p).choose p.
Border rank from one cluster, for the weighted Landsberg–Michałek tensor with some slices
zeroed. If c selects 2p + 1 distinct slices whose offsets have pairwise distinct
p-subset sums and d (c t) = 1 for every t, then
(2p+1).choose p * (2k + 1 - spread) ≤ borderRank ((diagonal d ⊗ 1 ⊗ 1) T) * (2p).choose p
for T = weightedLMTensor k.
Border rank from one cluster, contrapositive form. Under the hypotheses of
choose_mul_le_borderRank_mul_map_diagonal_weightedLMTensor, if
r * (2p).choose p < (2p+1).choose p * (2k + 1 - spread), then
(diagonal d ⊗ 1 ⊗ 1) (weightedLMTensor k) does not have border rank at most r.
Border rank from one cluster, for the weighted Landsberg–Michałek tensor. If c selects
2p + 1 distinct slices whose offsets have pairwise distinct p-subset sums, then
(2p+1).choose p * (2k + 1 - spread) ≤ borderRank (weightedLMTensor k) * (2p).choose p.