AFTD Auto-Formalizing Theoretical Domains

complete_uniform_hypergraph_schmidt_rank_k_two

theoremverifiedformalization

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

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.

  1. 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).

    lines 4–20

    uses Nat.choose_succ_succ', Nat.choose_one_right, pow_add, odd_two_mul_add_one

      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
  2. 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.

    lines 21–33

    uses Nat.twoStepInduction

      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
  3. 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.

    lines 34–44

    uses Matrix.mul_apply, Fin.sum_univ_two

      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
  4. 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.

    lines 45–50

    uses Matrix.rank_mul_le_left, Matrix.rank_le_card_width

      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
  5. 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.

    lines 51–64

    uses Fin.castLE, Matrix.det_fin_two, Fin.val_castLE, Matrix.rank_of_det_ne_zero, Matrix.rank_submatrix_le

      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
  6. 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.

    line 65

      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

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

/-- 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
See it in the graphDiscuss this resultChallenge it