Weighted shift tensors and the weighted Landsberg–Michałek tensors

• Tensor3.weightedShifts o g is the tensor in ℂ^α ⊗ ℂ^m ⊗ ℂ^m whose t-th slice is the weighted shift matrix with offset o t and weights g t: its (t, j, ℓ) coordinate is g t j if ℓ = j + o t (as integers) and 0 otherwise.
• Tensor3.lmTensor k γ is the tensor T_k(γ) = ∑_{i, j} γ_{i, j} a_i ⊗ b_j ⊗ c_{i + j} in ℂ^{2k+1} ⊗ ℂ^{2k+1} ⊗ ℂ^{2k+1} of Landsberg and Michałek, Towards finding hay in a haystack, Theory of Computing 2025, (1.1), with the coefficients γ (their p_{ij}) as a parameter. The slice index a : Fin (2k+1) stands for the offset i = a - k ∈ [-k, k], so T_k(γ) = weightedShifts (a ↦ a - k) γ.
• Tensor3.lmWeight k a j = 2^{2^{a (2k+1) + j}} are explicit coefficients: the exponent a (2k+1) + j is an injective code of the position (a, j).
• Tensor3.weightedLMTensor k is the Landsberg–Michałek tensor T_k(lmWeight k) with these doubly exponential weights.
• Tensor3.periodicWeight k A M a j = 2^{2^{(a mod A) M + (j mod M)}} are periodic coefficients: the exponent codes the position (a, j) only modulo (A, M), so for A, M > 0 it lies below A M whatever k is. Tensor3.periodicLMTensor k A M is T_k(periodicWeight k A M); for A, M > 0 its entries lie in the set {0} ∪ {2^{2^e} : e < A M}, which does not depend on k.
• Tensor3.selectSlices c is the matrix of the linear map ℂ^α → ℂ^{α'} keeping the coordinates c t; applied to the first factor, map (selectSlices c) 1 1 T keeps the slices c t of T. For a strictly increasing c : Fin (2p+1) → Fin (2k+1) (a cluster of slices) it projects T_k(γ) to the cluster tensor, with 2p + 1 slices.
• Tensor3.clusterOffsets k c t = c t - k are the offsets of the slices of a cluster.
• Tensor3.sumSpread p o is the spread of the sums ∑_{t ∈ K} o t over the subsets K of size p or p + 1: the largest minus the smallest of these sums.
• Tensor3.subsetSumSpread p o is the spread of the sums ∑_{t ∈ I} o t over the subsets I of size p only. It is at most sumSpread p o, and at most p L for monotone offsets of diameter L, whatever their median. The labels of the weights need only be distinct on positions whose columns differ by at most subsetSumSpread p o.

The Koszul-flattening bound for cluster tensors is in Complexitylib.Algebraic.LinearAlgebra.Tensor.Diagonal.

def Algebraic.Tensor3.weightedShifts {α : Type u_1} {m : ℕ} (o : α → ℤ) (g : α → Fin m → ℂ) : Tensor3 α (Fin m) (Fin m)

The tensor whose t-th slice is the weighted shift matrix with offset o t and weights g t: its (t, j, ℓ) coordinate is g t j if ℓ = j + o t and 0 otherwise.

Equations

• Algebraic.Tensor3.weightedShifts o g t j ℓ = if ↑↑ℓ = ↑↑j + o t then g t j else 0

def Algebraic.Tensor3.lmTensor (k : ℕ) (γ : Fin (2 * k + 1) → Fin (2 * k + 1) → ℂ) : Tensor3 (Fin (2 * k + 1)) (Fin (2 * k + 1)) (Fin (2 * k + 1))

The Landsberg–Michałek tensor T_k(γ) = ∑_{i, j} γ_{i, j} a_i ⊗ b_j ⊗ c_{i + j} with coefficients γ. The slice index a : Fin (2k+1) stands for the offset i = a - k: the (a, j, ℓ) coordinate is γ a j if ℓ = j + (a - k) and 0 otherwise.

Equations

• Algebraic.Tensor3.lmTensor k γ = Algebraic.Tensor3.weightedShifts (fun (a : Fin (2 * k + 1)) => ↑↑a - ↑k) γ

def Algebraic.Tensor3.lmWeight (k : ℕ) (a j : Fin (2 * k + 1)) : ℂ

Doubly exponential coefficients 2^{2^{a (2k+1) + j}}, indexed by an injective code of the position (a, j).

Equations

• Algebraic.Tensor3.lmWeight k a j = ↑(2 ^ 2 ^ (↑a * (2 * k + 1) + ↑j))

def Algebraic.Tensor3.weightedLMTensor (k : ℕ) : Tensor3 (Fin (2 * k + 1)) (Fin (2 * k + 1)) (Fin (2 * k + 1))

The weighted Landsberg–Michałek tensor T_k(lmWeight k): its (a, j, ℓ) coordinate is 2^{2^{a (2k+1) + j}} if ℓ = j + (a - k) and 0 otherwise.

Equations

• Algebraic.Tensor3.weightedLMTensor k = Algebraic.Tensor3.lmTensor k (Algebraic.Tensor3.lmWeight k)

def Algebraic.Tensor3.periodicWeight (k A M : ℕ) (a j : Fin (2 * k + 1)) : ℂ

Periodic doubly exponential coefficients 2^{2^{(a mod A) M + (j mod M)}}. The exponent codes the position (a, j) modulo (A, M): it separates two positions whose slices differ by less than A and whose columns differ by less than M, and it is less than A M when A, M > 0, whatever k is.

Equations

• Algebraic.Tensor3.periodicWeight k A M a j = ↑(2 ^ 2 ^ (↑a % A * M + ↑j % M))

def Algebraic.Tensor3.periodicLMTensor (k A M : ℕ) : Tensor3 (Fin (2 * k + 1)) (Fin (2 * k + 1)) (Fin (2 * k + 1))

The periodic Landsberg–Michałek tensor T_k(periodicWeight k A M): its (a, j, ℓ) coordinate is 2^{2^{(a mod A) M + (j mod M)}} if ℓ = j + (a - k) and 0 otherwise. For fixed A, M > 0 its entries come from a finite set independent of k.

Equations

• Algebraic.Tensor3.periodicLMTensor k A M = Algebraic.Tensor3.lmTensor k (Algebraic.Tensor3.periodicWeight k A M)

def Algebraic.Tensor3.selectSlices {α : Type u_1} {α' : Type u_2} [DecidableEq α] (c : α' → α) : Matrix α' α ℂ

The matrix of the linear map ℂ^α → ℂ^{α'} that keeps the coordinates c t: its (t, a) entry is 1 if a = c t and 0 otherwise.

Equations

• Algebraic.Tensor3.selectSlices c = Matrix.of fun (t : α') (a : α) => if c t = a then 1 else 0

def Algebraic.Tensor3.clusterOffsets (k : ℕ) {n : ℕ} (c : Fin n → Fin (2 * k + 1)) (t : Fin n) : ℤ

The offsets c t - k of the slices c t of the Landsberg–Michałek tensor T_k.

Equations

• Algebraic.Tensor3.clusterOffsets k c t = ↑↑(c t) - ↑k

def Algebraic.Tensor3.adjacentSubsets {α : Type u_1} [Fintype α] (p : ℕ) : Finset (Finset α)

The subsets of α of size p or p + 1, which index the bases of Λ^p ℂ^α and Λ^{p+1} ℂ^α.

Equations

• Algebraic.Tensor3.adjacentSubsets p = {K : Finset α | K.card = p ∨ K.card = p + 1}

def Algebraic.Tensor3.sumSpread {α : Type u_1} [Fintype α] (p : ℕ) (o : α → ℤ) : ℕ

The spread of the subset sums of o: the largest value of ∑_{t ∈ K} o t - ∑_{t ∈ K'} o t over subsets K, K' of size p or p + 1, that is, the largest minus the smallest of the sums ∑_{t ∈ K} o t.

Equations

• Algebraic.Tensor3.sumSpread p o = (Algebraic.Tensor3.adjacentSubsets p ×ˢ Algebraic.Tensor3.adjacentSubsets p).sup fun (KK : Finset α × Finset α) => (∑ t ∈ KK.1, o t - ∑ t ∈ KK.2, o t).toNat

def Algebraic.Tensor3.subsetSumSpread {α : Type u_1} [Fintype α] (p : ℕ) (o : α → ℤ) : ℕ

The spread of the p-subset sums of o: the largest value of ∑_{t ∈ I} o t - ∑_{t ∈ I'} o t over subsets I, I' of size p. In one block of the single-cluster minor the columns w + ∑_{t ∈ I} o t lie in a window of this length.

Equations

• Algebraic.Tensor3.subsetSumSpread p o = ({I : Finset α | I.card = p} ×ˢ {I : Finset α | I.card = p}).sup fun (II : Finset α × Finset α) => (∑ t ∈ II.1, o t - ∑ t ∈ II.2, o t).toNat