common_space_diagonal_tensor_rank_bound
Common-Space Diagonal Tensor Rank Bound (arXiv:2610.26686, Lemma 3). Let k = n + 1 ≥ 2 (with 1 ≤ n), and let V ⊆ U be a finite set. Let f : (Fin (n + 1) → U) → ℚ be (n + 1)-diagonal on V, meaning that for all x : Fin (n + 1) → U taking values in V, f(x) ≠ 0 if and only if all entries of x are equal. Suppose there exist functions p : Fin d → (U → ℚ) and G : Fin (n + 1) → Fin d → (Fin n → U) → ℚ such that for all x : Fin (n + 1) → U, f(x) = ∑_{i ≠ 0} ∑_{j} p_j(x_i) G_{i,j}(x ∘ i.succAbove), where the outer sum is over nonzero indices i ∈ Fin (n + 1) and x ∘ i.succAbove is the tuple obtained by omitting the i-th entry. Then the cardinality of V is at most d.
Statement
theorem common_space_diagonal_tensor_rank_bound {U : Type*} (n d : ℕ) (hn : 1 ≤ n) (V : Finset U) (f : (Fin (n + 1) → U) → ℚ) (hdiag : is_k_diagonal_on V f) (p : Fin d → (U → ℚ)) (G : Fin (n + 1) → Fin d → (Fin n → U) → ℚ) (hdecomp : ∀ x : Fin (n + 1) → U, f x = ∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), ∑ j : Fin d, p j (x i) * G i j (x ∘ i.succAbove)) : V.card ≤ d
- Formalizes
- arXiv:2610.26686 Lemma 3
- Verified
- 22 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 2
- is_k_diagonal_onLet V be a finite subset of U. A function f : U^k -> ℚ is k-diagonal on V if for all x : Fin k -> U with all coordinates in V, f(x) ≠ 0 if…
- exists_nontrivial_solution_of_card_gtIf a finite set V has cardinality strictly greater than d, then for any d functions p_j : U -> ℚ, there exists a non-zero function h : V…
Read back from the Lean
Let $U$ be a type, and let $n$ and $d$ be natural numbers with $1 \le n$. Let $V$ be a finite subset of $U$, and let $f : (\mathrm{Fin}(n + 1) \to U) \to \mathbb{Q}$ be a function. Assume $f$ is diagonal on $V$ in the sense that for every $x : \mathrm{Fin}(n + 1) \to U$ such that $x(i) \in V$ for all $i \in \mathrm{Fin}(n + 1)$, $f(x) \ne 0$ if and only if all components of $x$ are equal (that is, $x(i) = x(j)$ for all $i, j \in \mathrm{Fin}(n + 1)$). Let $p : \mathrm{Fin}(d) \to U \to \mathbb{Q}$ be a collection of $d$ functions from $U$ to $\mathbb{Q}$, and let $G : \mathrm{Fin}(n + 1) \to \mathrm{Fin}(d) \to (\mathrm{Fin}(n) \to U) \to \mathbb{Q}$. Assume that for all $x : \mathrm{Fin}(n + 1) \to U$, $f(x)$ decomposes as: $$f(x) = \sum_{i \in \mathrm{Fin}(n + 1),\, i \ne 0} \sum_{j \in \mathrm{Fin}(d)} p(j)(x(i)) \cdot G(i, j)(x \circ i.\mathrm{succAbove})$$ (where $i.\mathrm{succAbove} : \mathrm{Fin}(n) \hookrightarrow \mathrm{Fin}(n + 1)$ is the embedding that skips index $i$, so $x \circ i.\mathrm{succAbove}$ is the tuple $x$ with the $i$-th entry omitted). Then the cardinality of $V$ is at most $d$ ($|V| \le d$).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
To prove that |V| ≤ d, we assume for contradiction that |V| > d. By linear algebra over ℚ, there exists a nonzero vector h : V → ℚ orthogonal to all d functions p_j on V, so h(a) ≠ 0 for some a ∈ V. Defining a weight system w on Fin (n + 1) with w 0 = δ_a and w_t = h for all t > 0, we evaluate the multilinear sum S = ∑_{x ∈ V^(n+1)} (∏_t w_t(x_t)) f(x) in two ways: expanding f via its decomposition, every term isolates some coordinate i ≠ 0 where w_i = h is orthogonal to p_j, forcing S = 0; conversely, the diagonal property of f and the support of w 0 annihilate every tuple x except the constant tuple (a, ..., a), leaving a single nonzero diagonal term (h a)^n f(a, ..., a) ≠ 0. This contradiction shows |V| ≤ d.
For a fixed nonzero index i and function index j, the sum over all tuples x : Fin (n + 1) → V reduces to an outer sum over the remaining coordinates z : Fin n → V of an inner sum over the i-th coordinate u : V, and it suffices to show each inner sum vanishes.
We reindex the sum over tuples x : Fin (n + 1) → V via the equivalence Fin.insertNthEquiv, which splits x into the i-th entry u ∈ V and the remaining n entries z : Fin n → V. By Fintype.sum_prod_type and exchanging the order of summation with Finset.sum_comm, the total sum becomes a sum over z of an inner sum over u. Showing every inner sum equals zero thus suffices.
uses
Fin.insertNthEquiv,Fintype.sum_prod_type,Finset.sum_comm,Finset.sum_eq_zerointro w have hequiv := (Fin.insertNthEquiv (fun _ => V) i).sum_comp (fun x => (∏ t : Fin (n + 1), w t (x t)) * (p j (x i) * G i j ((fun m => (x m : U)) ∘ i.succAbove))) rw [← hequiv] rw [Fintype.sum_prod_type] rw [Finset.sum_comm] apply Finset.sum_eq_zero intro z _ change ∑ u : V, (∏ t : Fin (n + 1), w t (Fin.insertNth (α := fun _ => V) i u z t)) * (p j ((Fin.insertNth (α := fun _ => V) i u z i : U)) * G i j ((fun m => (Fin.insertNth (α := fun _ => V) i u z m : U)) ∘ i.succAbove)) = 0
For any fixed z and u, the weight product factors into h(u) times the product over the coordinates of z, the value at index i is u, and the tuple of remaining coordinates is z.
Since i ≠ 0, the weight w i is defined as h (using Fin.succ_pred and Fin.cons_succ). Splitting the product of weights at index i via Fin.prod_univ_succAbove isolates w i u = h u from the product over the remaining entries. Furthermore, inserting u at position i produces u at index i by Fin.insertNth_apply_same, while omitting position i via i.succAbove leaves the tuple z unchanged by Fin.insertNth_apply_succAbove.
uses
Fin.prod_univ_succAbove,Fin.insertNth_apply_same,Fin.succ_pred,Fin.cons_succ,Finset.prod_congr,Fin.insertNth_apply_succAbove,Function.comp_applyhave hprod : ∀ u : V, ∏ t : Fin (n + 1), w t (Fin.insertNth (α := fun _ => V) i u z t) = h u * ∏ m : Fin n, w (i.succAbove m) (z m) := by intro u rw [Fin.prod_univ_succAbove (fun t => w t (Fin.insertNth (α := fun _ => V) i u z t)) i] rw [Fin.insertNth_apply_same] have hw : w i = h := by have hi' : (i.pred hi).succ = i := Fin.succ_pred i hi rw [← hi'] exact Fin.cons_succ (α := fun _ => V → ℚ) _ _ (i.pred hi) rw [hw] congr 1 apply Finset.prod_congr rfl intro m _ rw [Fin.insertNth_apply_succAbove] have hcomp_u : ∀ u : V, ((fun m => (Fin.insertNth (α := fun _ => V) i u z m : U)) ∘ i.succAbove) = fun m => (z m : U) := by intro u ext m simp only [Function.comp_apply] congr 1 exact Fin.insertNth_apply_succAbove (α := fun _ => V) i u z m have hsame : ∀ u : V, (Fin.insertNth (α := fun _ => V) i u z i : U) = (u : U) := by intro u congr 1 exact Fin.insertNth_apply_same (α := fun _ => V) i u z
The inner sum over u ∈ V is zero.
Using the factorization of the weight product and the simplified arguments, the summand rewrites to (h u * p j u) * ((∏ m, w (i.succAbove m) (z m)) * G i j z). Factoring the z-dependent part out of the sum over u yields (∑ u : V, h u * p j u) multiplied by this factor. By the orthogonality hypothesis h_ortho, the sum ∑ u : V, h u * p j u equals zero, so the entire inner sum vanishes.
uses
Finset.sum_congr,Finset.sum_mul,zero_mulhave hstep : (∑ u : V, (∏ t : Fin (n + 1), w t (Fin.insertNth (α := fun _ => V) i u z t)) * (p j ((Fin.insertNth (α := fun _ => V) i u z i : U)) * G i j ((fun m => (Fin.insertNth (α := fun _ => V) i u z m : U)) ∘ i.succAbove))) = ∑ u : V, (h u * p j (u : U)) * ((∏ m : Fin n, w (i.succAbove m) (z m)) * G i j (fun m => (z m : U))) := by apply Finset.sum_congr rfl intro u _ rw [hprod u, hsame u, hcomp_u u] ring rw [hstep, ← Finset.sum_mul, h_ortho j, zero_mul]
The total weighted sum of f(x) over x : Fin (n + 1) → V can be expanded as a sum over nonzero indices i and indices j of the individual decomposition terms.
We substitute the decomposition of f(x) given by hdecomp into the weighted sum and distribute the weight product across the finite sums over i ≠ 0 and j using Finset.mul_sum.
uses
Finset.mul_sum,Finset.sum_congrintro w have hrew : (fun x : Fin (n + 1) → V => (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U))) = fun x => ∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), ∑ j : Fin d, (∏ t : Fin (n + 1), w t (x t)) * (p j (x i) * G i j ((fun m => (x m : U)) ∘ i.succAbove)) := by ext x rw [hdecomp (fun m => (x m : U))] rw [Finset.mul_sum] apply Finset.sum_congr rfl intro i _ rw [Finset.mul_sum]
The total weighted sum of f(x) over all x : Fin (n + 1) → V is zero.
Exchanging the order of summation brings the sums over nonzero i and over j to the outside. Each summand is then an instance of common_space_diagonal_tensor_rank_bound_term_sum_zero, which was shown to vanish. Since every term in the outer sum is zero, the total sum is zero.
uses
Finset.sum_comm,Finset.sum_eq_zero,Finset.mem_filter,common_space_diagonal_tensor_rank_bound_term_sum_zerorw [hrew] rw [Finset.sum_comm] apply Finset.sum_eq_zero intro i hi rw [Finset.mem_filter] at hi rw [Finset.sum_comm] apply Finset.sum_eq_zero intro j _ exact common_space_diagonal_tensor_rank_bound_term_sum_zero n d a h p h_ortho G i hi.2 j
Every tuple x : Fin (n + 1) → V other than the constant diagonal tuple x_diag = (a, ..., a) contributes zero to the weighted sum.
Let x ≠ x_diag. If x 0 ≠ a, then w 0 (x 0) = 0 by definition of w 0, so the product of weights vanishes. If x 0 = a, then since x ≠ x_diag, not all entries of x can be equal; because f is diagonal on V, this implies f(x) = 0. In both cases, the product of the weights and f(x) is zero.
uses
congr_arg,Subtype.val,mul_zero,Fin.cons_zero,if_neg,Fin.prod_univ_succ,zero_mulintro w let x_diag : Fin (n + 1) → V := fun _ => a have h_term_zero : ∀ x : Fin (n + 1) → V, x ≠ x_diag → (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = 0 := by intro x hx by_cases h0 : x 0 = a · have h_not_all : ¬ (∀ i j : Fin (n + 1), (x i : U) = (x j : U)) := by intro hall apply hx ext i have hi0 := hall i 0 have h0' : (x 0 : U) = (a : U) := congr_arg Subtype.val h0 exact hi0.trans h0' have hf : f (fun m => (x m : U)) = 0 := by by_contra hfne have h_all_eq := (hdiag (fun m => (x m : U)) (fun m => (x m).2)).mp hfne exact h_not_all h_all_eq rw [hf, mul_zero] · have hw0 : w 0 (x 0) = 0 := by have : w 0 = fun u => if u = a then (1:ℚ) else 0 := Fin.cons_zero (α := fun _ => V → ℚ) _ _ rw [this] dsimp exact if_neg h0 have hprod : ∏ t : Fin (n + 1), w t (x t) = 0 := by rw [Fin.prod_univ_succ] rw [hw0, zero_mul] rw [hprod, zero_mul]
The total weighted sum reduces to the single diagonal term at x_diag.
Splitting the sum over all tuples into the term at x_diag and the sum over all other tuples via Finset.add_sum_erase, the sum over the remaining tuples vanishes because each term was shown to be zero.
uses
Finset.add_sum_erase,Finset.mem_univ,Finset.sum_eq_zero,Finset.mem_erase,add_zerohave hsum_eq : ∑ x : Fin (n + 1) → V, (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = (∏ t : Fin (n + 1), w t (x_diag t)) * f (fun m => (x_diag m : U)) := by rw [← Finset.add_sum_erase _ _ (Finset.mem_univ x_diag)] have herase : ∑ x ∈ (Finset.univ.erase x_diag), (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = 0 := by apply Finset.sum_eq_zero intro x hx rw [Finset.mem_erase] at hx exact h_term_zero x hx.1 rw [herase, add_zero] rw [hsum_eq]
The single diagonal term is nonzero, so the total weighted sum of f is nonzero.
At x_diag, all entries are equal to a, so f(x_diag) ≠ 0 by the diagonal property of f. The weight product at x_diag splits into w 0 a = 1 times the product of w (i.succ) a = h a for i ∈ Fin n, giving 1 * (h a)^n. Since h a ≠ 0 and n ≥ 1, this power is nonzero. The product of two nonzero rationals is nonzero.
uses
Fin.prod_univ_succ,Fin.cons_zero,if_pos,one_mul,Fin.cons_succ,Finset.prod_const,Finset.card_univ,Fintype.card_fin,pow_ne_zero,mul_ne_zerohave hf_diag : f (fun m => (x_diag m : U)) ≠ 0 := by have h_all : ∀ i j : Fin (n + 1), ((x_diag i : U) = (x_diag j : U)) := fun _ _ => rfl exact (hdiag (fun m => (x_diag m : U)) (fun m => (x_diag m).2)).mpr h_all have hprod_diag : ∏ t : Fin (n + 1), w t (x_diag t) ≠ 0 := by rw [Fin.prod_univ_succ] have hw0 : w 0 (x_diag 0) = 1 := by have : w 0 = fun u => if u = a then (1:ℚ) else 0 := Fin.cons_zero (α := fun _ => V → ℚ) _ _ rw [this] dsimp [x_diag] rw [if_pos rfl] rw [hw0, one_mul] have hw_succ : ∀ i : Fin n, w i.succ (x_diag i.succ) = h a := by intro i have : w i.succ = h := Fin.cons_succ (α := fun _ => V → ℚ) _ _ i rw [this] have hprod_succ : ∏ i : Fin n, w i.succ (x_diag i.succ) = (h a) ^ n := by have : (fun i : Fin n => w i.succ (x_diag i.succ)) = fun _ => h a := by ext i; exact hw_succ i rw [this, Finset.prod_const, Finset.card_univ, Fintype.card_fin] rw [hprod_succ] exact pow_ne_zero n ha exact mul_ne_zero hprod_diag hf_diag
If |V| > d, there exists a nonzero function h : V → ℚ orthogonal to every p_j, and a point a ∈ V such that h a ≠ 0.
Assuming for contradiction that d < |V|, the homogeneous linear system ∑_{x ∈ V} h(x) p_j(x) = 0 for j ∈ Fin d has fewer equations than variables, so exists_nontrivial_solution_of_card_gt provides a nontrivial solution h ≠ 0. Since h is not the zero function, there exists some a ∈ V with h a ≠ 0.
uses
exists_nontrivial_solution_of_card_gtclassical by_contra! hcard rcases exists_nontrivial_solution_of_card_gt V d p hcard with ⟨h, hne, h_ortho⟩ have hex : ∃ a : V, h a ≠ 0 := by by_contra! hall apply hne ext a exact hall a rcases hex with ⟨a, ha⟩
The cardinality of V is at most d.
From the assumed decomposition of f and the orthogonality of h with p_j, the total weighted sum of f is zero by common_space_diagonal_tensor_rank_bound_total_sum_zero. But since f is diagonal on V and h a ≠ 0 with 1 ≤ n, the same sum is nonzero by common_space_diagonal_tensor_rank_bound_single_term_nonzero. This contradiction establishes that |V| ≤ d.
uses
common_space_diagonal_tensor_rank_bound_total_sum_zero,common_space_diagonal_tensor_rank_bound_single_term_nonzerohave hzero := common_space_diagonal_tensor_rank_bound_total_sum_zero n d a h f p h_ortho G hdecomp have hnonzero := common_space_diagonal_tensor_rank_bound_single_term_nonzero n hn a h ha f hdiag exact hnonzero hzero
mul_zero- The product of a nonzero element with zero is zero: a * 0 = 0
zero_mul- The product of zero with any element is zero: 0 * a = 0
add_zero- Adding zero on the right leaves an element unchanged: a + 0 = a
one_mul- Multiplying by one on the left leaves an element unchanged: 1 * a = a
mul_ne_zero- In a domain with no zero divisors, the product of two nonzero elements is nonzero
pow_ne_zero- A nonzero element raised to any natural power is nonzero
if_pos- If c is true, the conditional if c then t else e equals t
if_neg- If c is false, the conditional if c then t else e equals e
congr_arg- Applying a function to both sides of an equality preserves equality
Subtype.val- The canonical coercion / projection from a subtype to its carrier type
Function.comp_apply- Function composition evaluated at a point: (f ∘ g)(x) = f(g(x))
Fin.succ_pred- For any nonzero index i in Fin (n + 1), the successor of its predecessor is i
Fin.cons_zero- Fin.cons evaluated at index 0 returns its first argument
Fin.cons_succ- Fin.cons evaluated at a successor index i.succ returns the i-th element of its second argument
Fin.insertNth_apply_same- The value of Fin.insertNth i x p at the insertion index i is x
Fin.insertNth_apply_succAbove- The value of Fin.insertNth i x p at index i.succAbove j is p(j)
Fin.insertNthEquiv- The canonical equivalence between α i × (Π j, α (i.succAbove j)) and (Π j, α j) by inserting at index i
Fin.prod_univ_succ- A product over Fin (n + 1) splits into the factor at index 0 times the product over Fin n of factors at successor indices
Fin.prod_univ_succAbove- A product over Fin (n + 1) splits into the factor at index i times the product over Fin n of factors at i.succAbove indices
Fintype.sum_prod_type- A sum over a product type α₁ × α₂ equals the iterated sum over α₁ and α₂
Fintype.card_fin- The number of elements in Fin n is n
Finset.sum_comm- Fubini theorem for finite sums: exchanging the order of summation over two finite sets
Finset.sum_eq_zero- A finite sum is zero if every term in the sum is zero
Finset.sum_congr- Two finite sums are equal if their index sets are equal and their summands agree at every element
Finset.prod_congr- Two finite products are equal if their index sets are equal and their factors agree at every element
Finset.sum_mul- Right-distributivity of multiplication over a finite sum: (∑ x, f x) * a = ∑ x, (f x * a)
Finset.mul_sum- Left-distributivity of multiplication over a finite sum: a * ∑ x, f x = ∑ x, (a * f x)
Finset.mem_filter- An element belongs to a filtered finset if and only if it belongs to the set and satisfies the condition
Finset.mem_univ- Every element of a finite type belongs to its universal finset
Finset.mem_erase- An element belongs to s.erase b if and only if it is in s and not equal to b
Finset.add_sum_erase- Splitting a finite sum into a chosen term and the sum over the remaining elements
Finset.prod_const- The product of a constant value over a finite set equals the constant raised to the cardinality of the set
Finset.card_univ- The cardinality of the universal finset of a finite type equals the Fintype cardinality of the type
exists_nontrivial_solution_of_card_gt- A homogeneous linear system over ℚ with fewer equations than variables has a nontrivial solution
common_space_diagonal_tensor_rank_bound_term_sum_zero- The weighted sum of a single decomposition term vanishes when the isolated coordinate i is nonzero and h is orthogonal to p_j
common_space_diagonal_tensor_rank_bound_total_sum_zero- The total weighted sum of f(x) over V^(n+1) is zero under the decomposition and orthogonality hypotheses
common_space_diagonal_tensor_rank_bound_single_term_nonzero- The total weighted sum of f(x) over V^(n+1) is nonzero when f is diagonal on V, h(a) ≠ 0, and 1 ≤ n
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
open Classical intheorem common_space_diagonal_tensor_rank_bound_term_sum_zero {U : Type*} (n d : ℕ) {V : Finset U} (a : V) (h : V → ℚ) (p : Fin d → U → ℚ) (h_ortho : ∀ j : Fin d, ∑ x : V, h x * p j x = 0) (G : Fin (n + 1) → Fin d → (Fin n → U) → ℚ) (i : Fin (n + 1)) (hi : i ≠ 0) (j : Fin d) : let w : Fin (n + 1) → V → ℚ := Fin.cons (fun u => if u = a then (1:ℚ) else 0) (fun _ => h) ∑ x : Fin (n + 1) → V, (∏ t : Fin (n + 1), w t (x t)) * (p j (x i) * G i j ((fun m => (x m : U)) ∘ i.succAbove)) = 0 := by intro w have hequiv := (Fin.insertNthEquiv (fun _ => V) i).sum_comp (fun x => (∏ t : Fin (n + 1), w t (x t)) * (p j (x i) * G i j ((fun m => (x m : U)) ∘ i.succAbove))) rw [← hequiv] rw [Fintype.sum_prod_type] rw [Finset.sum_comm] apply Finset.sum_eq_zero intro z _ change ∑ u : V, (∏ t : Fin (n + 1), w t (Fin.insertNth (α := fun _ => V) i u z t)) * (p j ((Fin.insertNth (α := fun _ => V) i u z i : U)) * G i j ((fun m => (Fin.insertNth (α := fun _ => V) i u z m : U)) ∘ i.succAbove)) = 0 have hprod : ∀ u : V, ∏ t : Fin (n + 1), w t (Fin.insertNth (α := fun _ => V) i u z t) = h u * ∏ m : Fin n, w (i.succAbove m) (z m) := by intro u rw [Fin.prod_univ_succAbove (fun t => w t (Fin.insertNth (α := fun _ => V) i u z t)) i] rw [Fin.insertNth_apply_same] have hw : w i = h := by have hi' : (i.pred hi).succ = i := Fin.succ_pred i hi rw [← hi'] exact Fin.cons_succ (α := fun _ => V → ℚ) _ _ (i.pred hi) rw [hw] congr 1 apply Finset.prod_congr rfl intro m _ rw [Fin.insertNth_apply_succAbove] have hcomp_u : ∀ u : V, ((fun m => (Fin.insertNth (α := fun _ => V) i u z m : U)) ∘ i.succAbove) = fun m => (z m : U) := by intro u ext m simp only [Function.comp_apply] congr 1 exact Fin.insertNth_apply_succAbove (α := fun _ => V) i u z m have hsame : ∀ u : V, (Fin.insertNth (α := fun _ => V) i u z i : U) = (u : U) := by intro u congr 1 exact Fin.insertNth_apply_same (α := fun _ => V) i u z have hstep : (∑ u : V, (∏ t : Fin (n + 1), w t (Fin.insertNth (α := fun _ => V) i u z t)) * (p j ((Fin.insertNth (α := fun _ => V) i u z i : U)) * G i j ((fun m => (Fin.insertNth (α := fun _ => V) i u z m : U)) ∘ i.succAbove))) = ∑ u : V, (h u * p j (u : U)) * ((∏ m : Fin n, w (i.succAbove m) (z m)) * G i j (fun m => (z m : U))) := by apply Finset.sum_congr rfl intro u _ rw [hprod u, hsame u, hcomp_u u] ring rw [hstep, ← Finset.sum_mul, h_ortho j, zero_mul]open Classical intheorem common_space_diagonal_tensor_rank_bound_total_sum_zero {U : Type*} (n d : ℕ) {V : Finset U} (a : V) (h : V → ℚ) (f : (Fin (n + 1) → U) → ℚ) (p : Fin d → U → ℚ) (h_ortho : ∀ j : Fin d, ∑ x : V, h x * p j x = 0) (G : Fin (n + 1) → Fin d → (Fin n → U) → ℚ) (hdecomp : ∀ x : Fin (n + 1) → U, f x = ∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), ∑ j : Fin d, p j (x i) * G i j (x ∘ i.succAbove)) : let w : Fin (n + 1) → V → ℚ := Fin.cons (fun u => if u = a then (1:ℚ) else 0) (fun _ => h) ∑ x : Fin (n + 1) → V, (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = 0 := by intro w have hrew : (fun x : Fin (n + 1) → V => (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U))) = fun x => ∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), ∑ j : Fin d, (∏ t : Fin (n + 1), w t (x t)) * (p j (x i) * G i j ((fun m => (x m : U)) ∘ i.succAbove)) := by ext x rw [hdecomp (fun m => (x m : U))] rw [Finset.mul_sum] apply Finset.sum_congr rfl intro i _ rw [Finset.mul_sum] rw [hrew] rw [Finset.sum_comm] apply Finset.sum_eq_zero intro i hi rw [Finset.mem_filter] at hi rw [Finset.sum_comm] apply Finset.sum_eq_zero intro j _ exact common_space_diagonal_tensor_rank_bound_term_sum_zero n d a h p h_ortho G i hi.2 jopen Classical intheorem common_space_diagonal_tensor_rank_bound_single_term_nonzero {U : Type*} (n : ℕ) (_hn : 1 ≤ n) {V : Finset U} (a : V) (h : V → ℚ) (ha : h a ≠ 0) (f : (Fin (n + 1) → U) → ℚ) (hdiag : is_k_diagonal_on V f) : let w : Fin (n + 1) → V → ℚ := Fin.cons (fun u => if u = a then (1:ℚ) else 0) (fun _ => h) ∑ x : Fin (n + 1) → V, (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) ≠ 0 := by intro w let x_diag : Fin (n + 1) → V := fun _ => a have h_term_zero : ∀ x : Fin (n + 1) → V, x ≠ x_diag → (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = 0 := by intro x hx by_cases h0 : x 0 = a · have h_not_all : ¬ (∀ i j : Fin (n + 1), (x i : U) = (x j : U)) := by intro hall apply hx ext i have hi0 := hall i 0 have h0' : (x 0 : U) = (a : U) := congr_arg Subtype.val h0 exact hi0.trans h0' have hf : f (fun m => (x m : U)) = 0 := by by_contra hfne have h_all_eq := (hdiag (fun m => (x m : U)) (fun m => (x m).2)).mp hfne exact h_not_all h_all_eq rw [hf, mul_zero] · have hw0 : w 0 (x 0) = 0 := by have : w 0 = fun u => if u = a then (1:ℚ) else 0 := Fin.cons_zero (α := fun _ => V → ℚ) _ _ rw [this] dsimp exact if_neg h0 have hprod : ∏ t : Fin (n + 1), w t (x t) = 0 := by rw [Fin.prod_univ_succ] rw [hw0, zero_mul] rw [hprod, zero_mul] have hsum_eq : ∑ x : Fin (n + 1) → V, (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = (∏ t : Fin (n + 1), w t (x_diag t)) * f (fun m => (x_diag m : U)) := by rw [← Finset.add_sum_erase _ _ (Finset.mem_univ x_diag)] have herase : ∑ x ∈ (Finset.univ.erase x_diag), (∏ t : Fin (n + 1), w t (x t)) * f (fun m => (x m : U)) = 0 := by apply Finset.sum_eq_zero intro x hx rw [Finset.mem_erase] at hx exact h_term_zero x hx.1 rw [herase, add_zero] rw [hsum_eq] have hf_diag : f (fun m => (x_diag m : U)) ≠ 0 := by have h_all : ∀ i j : Fin (n + 1), ((x_diag i : U) = (x_diag j : U)) := fun _ _ => rfl exact (hdiag (fun m => (x_diag m : U)) (fun m => (x_diag m).2)).mpr h_all have hprod_diag : ∏ t : Fin (n + 1), w t (x_diag t) ≠ 0 := by rw [Fin.prod_univ_succ] have hw0 : w 0 (x_diag 0) = 1 := by have : w 0 = fun u => if u = a then (1:ℚ) else 0 := Fin.cons_zero (α := fun _ => V → ℚ) _ _ rw [this] dsimp [x_diag] rw [if_pos rfl] rw [hw0, one_mul] have hw_succ : ∀ i : Fin n, w i.succ (x_diag i.succ) = h a := by intro i have : w i.succ = h := Fin.cons_succ (α := fun _ => V → ℚ) _ _ i rw [this] have hprod_succ : ∏ i : Fin n, w i.succ (x_diag i.succ) = (h a) ^ n := by have : (fun i : Fin n => w i.succ (x_diag i.succ)) = fun _ => h a := by ext i; exact hw_succ i rw [this, Finset.prod_const, Finset.card_univ, Fintype.card_fin] rw [hprod_succ] exact pow_ne_zero n ha exact mul_ne_zero hprod_diag hf_diag/-- Common-space diagonal tensor rank bound: a k-diagonal tensor on V decomposed via d functions in one variable has |V| ≤ d. -/theorem common_space_diagonal_tensor_rank_bound {U : Type*} (n d : ℕ) (hn : 1 ≤ n) (V : Finset U) (f : (Fin (n + 1) → U) → ℚ) (hdiag : is_k_diagonal_on V f) (p : Fin d → (U → ℚ)) (G : Fin (n + 1) → Fin d → (Fin n → U) → ℚ) (hdecomp : ∀ x : Fin (n + 1) → U, f x = ∑ i ∈ Finset.univ.filter (· ≠ (0 : Fin (n + 1))), ∑ j : Fin d, p j (x i) * G i j (x ∘ i.succAbove)) : V.card ≤ d := by classical by_contra! hcard rcases exists_nontrivial_solution_of_card_gt V d p hcard with ⟨h, hne, h_ortho⟩ have hex : ∃ a : V, h a ≠ 0 := by by_contra! hall apply hne ext a exact hall a rcases hex with ⟨a, ha⟩ have hzero := common_space_diagonal_tensor_rank_bound_total_sum_zero n d a h f p h_ortho G hdecomp have hnonzero := common_space_diagonal_tensor_rank_bound_single_term_nonzero n hn a h ha f hdiag exact hnonzero hzero