complete_uniform_hypergraph_schmidt_rank_k_two
For any positive integers a and b, the rank over the rationals of the (a + 1) by (b + 1) matrix with entries (-1)^(Nat.choose (i + j) 2) for 0 ≤ i ≤ a and 0 ≤ j ≤ b is equal to 2.
Statement
theorem complete_uniform_hypergraph_schmidt_rank_k_two (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) : Matrix.rank (fun (i : Fin (a + 1)) (j : Fin (b + 1)) => (-1 : ℚ) ^ (Nat.choose (i.val + j.val) 2)) = 2
- Formalizes
- OP-1672
- Verified
- 16 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- complete_uniform_hypergraph_schmidt_rank_one_one_twoThe rank over the rationals of the 2 by 2 matrix with entries (-1)^(Nat.choose (i + j) 2) for i, j ∈ {0, 1} is equal to 2.
Read back from the Lean
For any natural numbers $a$ and $b$ satisfying $1 \le a$ and $1 \le b$, the $(a + 1) \times (b + 1)$ matrix over the rational numbers $\mathbb{Q}$ whose entry at index $(i, j)$ (for $i \in \mathrm{Fin}(a + 1)$ and $j \in \mathrm{Fin}(b + 1)$) is given by $(-1)^{\binom{i + j}{2}}$ has matrix rank equal to 2.
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
The theorem is proved by establishing matching upper and lower bounds on the rank of the matrix M with entries M i j = c(i + j), where c(n) = (-1)^(n.choose 2). First, Pascal's identity yields the two-step anti-periodicity c(n + 2) = -c(n), from which two-step induction gives an addition formula expressing c(i + j) as a bilinear combination of (c(i), c(i+1)) and (c(j), c(j+1)). This identity factors M into the product of an (a + 1) × 2 matrix and a 2 × (b + 1) matrix, bounding the rank from above by 2. Finally, because a, b ≥ 1, the leading 2 × 2 submatrix is well-defined and has non-zero determinant -2, showing the rank is at least 2.
The sequence c(n) = (-1)^(n.choose 2) satisfies the two-step anti-periodicity relation c(n + 2) = -c(n) for all n ∈ ℕ
Applying Pascal's identity twice shows that (n+2).choose 2 = n.choose 2 + (2*n + 1). Since 2*n + 1 is odd, (-1)^(2*n + 1) = -1, and splitting the power (-1)^(n.choose 2 + 2*n + 1) = (-1)^(n.choose 2) * (-1)^(2*n + 1) produces -c(n).
uses
Nat.choose_succ_succ',Nat.choose_one_right,pow_add,odd_two_mul_add_onelet c : ℕ → ℚ := fun n => (-1 : ℚ) ^ (Nat.choose n 2) have hrec2 : ∀ n, c (n+2) = - c n := by intro n dsimp [c] have hchoose : Nat.choose (n+2) 2 = Nat.choose n 2 + (2*n+1) := by calc Nat.choose (n+2) 2 = (n+1).choose 1 + (n+1).choose 2 := by rw [show n+2 = (n+1)+1 by omega, Nat.choose_succ_succ'] _ = (n+1) + ((n).choose 1 + (n).choose 2) := by rw [Nat.choose_one_right, Nat.choose_succ_succ'] _ = Nat.choose n 2 + (2*n+1) := by rw [Nat.choose_one_right] ring rw [hchoose, pow_add] have hodd : Odd (2*n+1) := odd_two_mul_add_one n rw [hodd.neg_one_pow] ring
For all i, j ∈ ℕ, the sequence satisfies the addition formula c(i + j) = ((c(i) + c(i + 1)) / 2) * c(j) + ((c(i) - c(i + 1)) / 2) * c(j + 1)
The identity is proved by two-step induction on i. For i = 0, c(0) = c(1) = 1, giving coefficients 1 and 0, which reduces to c(j). For i = 1, c(1) = 1 and c(2) = -1, giving coefficients 0 and 1, which reduces to c(j + 1) = c(1 + j). For the inductive step from n and n+1 to n+2, shifting the argument by 2 negates both sides via the recurrence c(n+2) = -c(n), matching the induction hypothesis for n.
uses
Nat.twoStepInductionhave hid : ∀ i j, c (i+j) = ((c i + c (i+1))/2) * c j + ((c i - c (i+1))/2) * c (j+1) := by intro i refine Nat.twoStepInduction (motive := fun n => ∀ j, c (n+j) = ((c n + c (n+1))/2) * c j + ((c n - c (n+1))/2) * c (j+1)) ?_ ?_ ?_ i · intro j simp [c] · intro j dsimp [c] rw [show 1 + j = j + 1 by omega] norm_num · intro n ihn ihs j rw [show n + 2 + j = (n + j) + 2 by omega, hrec2 (n+j), ihn j] rw [show n + 2 + 1 = (n + 1) + 2 by omega, hrec2 (n+1), hrec2 n] ring
The matrix M with entries M i j = c(i + j) factors as M = A * B, where A is of size (a + 1) × 2 and B is of size 2 × (b + 1)
Define A with columns (c(i) + c(i+1))/2 and (c(i) - c(i+1))/2, and B with rows c(j) and c(j+1). Expanding the matrix product (A * B) i j as a sum over Fin 2 matches the addition identity c(i + j) proved in the previous step.
uses
Matrix.mul_apply,Fin.sum_univ_twolet M : Matrix (Fin (a+1)) (Fin (b+1)) ℚ := fun i j => c (i.val + j.val) change M.rank = 2 let A : Matrix (Fin (a+1)) (Fin 2) ℚ := fun i k => if k = 0 then (c i.val + c (i.val+1))/2 else (c i.val - c (i.val+1))/2 let B : Matrix (Fin 2) (Fin (b+1)) ℚ := fun k j => if k = 0 then c j.val else c (j.val+1) have hAB : M = A * B := by ext i j rw [Matrix.mul_apply, Fin.sum_univ_two] simp [M, A, B] exact hid i.val j.val
The rational rank of M is at most 2
From the factorization M = A * B, the rank of a matrix product is bounded by the rank of the first factor A, which is at most its number of columns, the cardinality of Fin 2, which is 2.
uses
Matrix.rank_mul_le_left,Matrix.rank_le_card_widthhave hrank_le : M.rank ≤ 2 := by rw [hAB] calc (A * B).rank ≤ A.rank := Matrix.rank_mul_le_left A B _ ≤ Fintype.card (Fin 2) := Matrix.rank_le_card_width A _ = 2 := by simp
The rational rank of M is at least 2
Since a ≥ 1 and b ≥ 1, the indices 0 and 1 embed into Fin (a + 1) and Fin (b + 1) via Fin.castLE. The resulting 2 × 2 leading submatrix has entries c(0) = 1, c(1) = 1 in the first row and c(1) = 1, c(2) = -1 in the second row. Its determinant is 1 * (-1) - 1 * 1 = -2 ≠ 0, so the submatrix has full rank 2. Since any submatrix has rank bounded by the full matrix rank, rank(M) ≥ 2.
uses
Fin.castLE,Matrix.det_fin_two,Fin.val_castLE,Matrix.rank_of_det_ne_zero,Matrix.rank_submatrix_lelet r : Fin 2 → Fin (a+1) := Fin.castLE (by omega) let s : Fin 2 → Fin (b+1) := Fin.castLE (by omega) have hNdet : (M.submatrix r s).det ≠ 0 := by rw [Matrix.det_fin_two] dsimp only [Matrix.submatrix, M, c] simp only [r, s, Fin.val_castLE] norm_num have hNrank : (M.submatrix r s).rank = 2 := by rw [Matrix.rank_of_det_ne_zero hNdet] simp have hrank_ge : 2 ≤ M.rank := by calc 2 = (M.submatrix r s).rank := hNrank.symm _ ≤ M.rank := Matrix.rank_submatrix_le M r s
The rational rank of M is exactly 2
Combining the upper bound rank(M) ≤ 2 and the lower bound 2 ≤ rank(M), linear integer arithmetic closes the goal.
omega
Nat.choose_succ_succ'- Pascal's identity for binomial coefficients: (n+1).choose (k+1) = n.choose k + n.choose (k+1)
Nat.choose_one_right- The binomial coefficient n.choose 1 equals n
pow_add- In a monoid, a^(m + n) = a^m * a^n
odd_two_mul_add_one- For any integer or natural number a, 2*a + 1 is odd
Nat.twoStepInduction- Induction principle for ℕ with two base cases (0 and 1) and an induction step from n and n+1 to n+2
Matrix.mul_apply- The (i, k)-th entry of a matrix product M * N is the sum over j of M i j * N j k
Fin.sum_univ_two- A sum over Fin 2 evaluates to the term at 0 plus the term at 1
Matrix.rank_mul_le_left- The rank of a matrix product A * B is at most the rank of A
Matrix.rank_le_card_width- The rank of a matrix is at most the number of its columns (the cardinality of its column index type)
Fin.castLE- Embeds Fin n into Fin m given a proof that n ≤ m
Matrix.det_fin_two- The determinant of a 2 × 2 matrix is A 0 0 * A 1 1 - A 0 1 * A 1 0
Fin.val_castLE- The natural number value of an index in Fin n is preserved under Fin.castLE
Matrix.rank_of_det_ne_zero- A square matrix over an integral domain with non-zero determinant has full rank equal to its dimension
Matrix.rank_submatrix_le- The rank of any submatrix of A is at most the rank of A
- The base cases of the two-step induction and the evaluation of the 2 × 2 submatrix determinant are verified by Lean's computational tactics `norm_num` and `simp` via arithmetic on powers of -1.
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.
/-- For k = 2 and any positive integers a and b, the rational rank of the (a+1) x (b+1) complete 2-uniform hypergraph matrix is exactly 2. -/theorem complete_uniform_hypergraph_schmidt_rank_k_two (a b : ℕ) (ha : 1 ≤ a) (hb : 1 ≤ b) : Matrix.rank (fun (i : Fin (a + 1)) (j : Fin (b + 1)) => (-1 : ℚ) ^ (Nat.choose (i.val + j.val) 2)) = 2 := by let c : ℕ → ℚ := fun n => (-1 : ℚ) ^ (Nat.choose n 2) have hrec2 : ∀ n, c (n+2) = - c n := by intro n dsimp [c] have hchoose : Nat.choose (n+2) 2 = Nat.choose n 2 + (2*n+1) := by calc Nat.choose (n+2) 2 = (n+1).choose 1 + (n+1).choose 2 := by rw [show n+2 = (n+1)+1 by omega, Nat.choose_succ_succ'] _ = (n+1) + ((n).choose 1 + (n).choose 2) := by rw [Nat.choose_one_right, Nat.choose_succ_succ'] _ = Nat.choose n 2 + (2*n+1) := by rw [Nat.choose_one_right] ring rw [hchoose, pow_add] have hodd : Odd (2*n+1) := odd_two_mul_add_one n rw [hodd.neg_one_pow] ring have hid : ∀ i j, c (i+j) = ((c i + c (i+1))/2) * c j + ((c i - c (i+1))/2) * c (j+1) := by intro i refine Nat.twoStepInduction (motive := fun n => ∀ j, c (n+j) = ((c n + c (n+1))/2) * c j + ((c n - c (n+1))/2) * c (j+1)) ?_ ?_ ?_ i · intro j simp [c] · intro j dsimp [c] rw [show 1 + j = j + 1 by omega] norm_num · intro n ihn ihs j rw [show n + 2 + j = (n + j) + 2 by omega, hrec2 (n+j), ihn j] rw [show n + 2 + 1 = (n + 1) + 2 by omega, hrec2 (n+1), hrec2 n] ring let M : Matrix (Fin (a+1)) (Fin (b+1)) ℚ := fun i j => c (i.val + j.val) change M.rank = 2 let A : Matrix (Fin (a+1)) (Fin 2) ℚ := fun i k => if k = 0 then (c i.val + c (i.val+1))/2 else (c i.val - c (i.val+1))/2 let B : Matrix (Fin 2) (Fin (b+1)) ℚ := fun k j => if k = 0 then c j.val else c (j.val+1) have hAB : M = A * B := by ext i j rw [Matrix.mul_apply, Fin.sum_univ_two] simp [M, A, B] exact hid i.val j.val have hrank_le : M.rank ≤ 2 := by rw [hAB] calc (A * B).rank ≤ A.rank := Matrix.rank_mul_le_left A B _ ≤ Fintype.card (Fin 2) := Matrix.rank_le_card_width A _ = 2 := by simp let r : Fin 2 → Fin (a+1) := Fin.castLE (by omega) let s : Fin 2 → Fin (b+1) := Fin.castLE (by omega) have hNdet : (M.submatrix r s).det ≠ 0 := by rw [Matrix.det_fin_two] dsimp only [Matrix.submatrix, M, c] simp only [r, s, Fin.val_castLE] norm_num have hNrank : (M.submatrix r s).rank = 2 := by rw [Matrix.rank_of_det_ne_zero hNdet] simp have hrank_ge : 2 ≤ M.rank := by calc 2 = (M.submatrix r s).rank := hNrank.symm _ ≤ M.rank := Matrix.rank_submatrix_le M r s omega