AFTD Auto-Formalizing Theoretical Domains

complete_uniform_hypergraph_schmidt_rank_k_eq_add

theoremverifiedformalization

For any positive integers a and b, when k = a + b, the rank over the rationals of the (a + 1) by (b + 1) matrix with entries (-1)^(Nat.choose (i + j) (a + b)) for 0 ≤ i ≤ a and 0 ≤ j ≤ b is equal to 2.

Statement

theorem complete_uniform_hypergraph_schmidt_rank_k_eq_add (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) (a + b))) = 2
Formalizes
OP-1672
Verified
16 Nov 2026
Axioms
Classical.choiceQuot.soundpropext

Read back from the Lean

For any natural numbers $a$ and $b$ satisfying $1 \le a$ and $1 \le b$, the rank over the rational numbers $\mathbb{Q}$ of the $(a+1) \times (b+1)$ matrix whose $(i, j)$-th entry (for $i \in \{0, \dots, a\}$ and $j \in \{0, \dots, b\}$) is $(-1)^{\binom{i + j}{a + b}}$ is 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

To prove that the $(a+1) \times (b+1)$ matrix $M$ with entries $(-1)^{\binom{i+j}{a+b}}$ has rational rank 2 when $a, b \ge 1$, the proof establishes both $\mathrm{rank}(M) \le 2$ and $\mathrm{rank}(M) \ge 2$. Because row indices $i \le a$ and column indices $j \le b$ sum to at most $a+b$ with equality strictly when $(i,j)=(a,b)$, the binomial coefficient vanishes everywhere except at $(a,b)$ where it equals 1. Thus $M$ is an all-ones matrix minus 2 at $(a,b)$, which decomposes as the sum of two rank-1 outer products, giving $\mathrm{rank}(M) \le 2$ by subadditivity of rank. Finally, the $2 \times 2$ submatrix spanned by rows $\{0, a\}$ and columns $\{0, b\}$ has non-zero determinant $-2$, proving $\mathrm{rank}(M) \ge 2$.

  1. For any rational matrices $A$ and $B$, $\mathrm{rank}(A + B) \le \mathrm{rank}(A) + \mathrm{rank}(B)$.

    We enable classical logic and unfold the definition of matrix rank (`Matrix.rank`) to the dimension of the range of the corresponding linear map (`mulVecLin`). The linear map of $A + B$ equals the sum of the linear maps of $A$ and $B$ (`Matrix.mulVecLin_add`), so its range is contained in the subspace sum of their ranges (`LinearMap.range_add_le`). Applying monotonicity of subspace dimension (`Submodule.finrank_mono`) and the dimension bound for a sum of subspaces (`Submodule.finrank_add_le_finrank_add_finrank`), we conclude that rank is subadditive.

    lines 4–10

    uses Matrix.rank, Matrix.mulVecLin_add, Submodule.finrank_mono, LinearMap.range_add_le, Submodule.finrank_add_le_finrank_add_finrank

      classical
      have hrank_add_le : ∀ {X Y : Type} [Fintype Y] (A B : Matrix X Y ℚ),
          (A + B).rank ≤ A.rank + B.rank := by
        intro X Y _ A B
        rw [Matrix.rank, Matrix.rank, Matrix.rank, Matrix.mulVecLin_add]
        exact (Submodule.finrank_mono (LinearMap.range_add_le A.mulVecLin B.mulVecLin)).trans
          (Submodule.finrank_add_le_finrank_add_finrank _ _)
  2. We define the matrix $M$ and two rank-one indicator vectors $u$ and $v$ that isolate its bottom-right corner.

    We abbreviate the given matrix as $M$, having entries $M_{i, j} = (-1)^{\binom{i+j}{a+b}}$, and restate the theorem as $\mathrm{rank}(M) = 2$. We define vectors $u$ (which takes the value $-2$ at row index $a$ and $0$ elsewhere) and $v$ (which takes the value $1$ at column index $b$ and $0$ elsewhere). Their outer product $u v^T$ is zero everywhere except at position $(a, b)$, where it equals $-2$.

    lines 11–14

      set M : Matrix (Fin (a+1)) (Fin (b+1)) ℚ := fun i j => (-1:ℚ) ^ (Nat.choose (i.val+j.val) (a+b)) with hM
      change Matrix.rank M = 2
      let u : Fin (a+1) → ℚ := fun i => if i.val = a then -2 else 0
      let v : Fin (b+1) → ℚ := fun j => if j.val = b then 1 else 0
  3. Every entry $M_{i, j}$ satisfies $M_{i, j} = 1 + u_i v_j$.

    For row index $i \le a$ and column index $j \le b$ (`Nat.lt_succ_iff.mp`), the sum satisfies $i + j \le a + b$ (`Nat.add_le_add`), with equality if and only if $i = a$ and $j = b$. In the equality case $i = a \land j = b$, the binomial coefficient is $\binom{a+b}{a+b} = 1$ (`Nat.choose_self`), so $M_{a, b} = (-1)^1 = -1$, which matches $1 + u_a v_b = 1 + (-2) \cdot 1 = -1$ (`if_pos`). In the strict inequality case $i + j < a + b$ (`lt_of_le_of_ne`), the binomial coefficient is $0$ (`Nat.choose_eq_zero_of_lt`), giving $M_{i, j} = (-1)^0 = 1$; since at least one of $i = a$ or $j = b$ fails, the product $u_i v_j$ vanishes (`if_neg`), matching $1 + 0 = 1$.

    lines 15–38

    uses Nat.lt_succ_iff.mp, Nat.add_le_add, Nat.choose_self, if_pos, lt_of_le_of_ne, Nat.choose_eq_zero_of_lt, if_neg

      have hchoose : ∀ (i : Fin (a+1)) (j : Fin (b+1)), M i j = 1 + u i * v j := by
        intro i j
        rw [hM]
        dsimp only [u, v]
        have hi : i.val ≤ a := Nat.lt_succ_iff.mp i.isLt
        have hj : j.val ≤ b := Nat.lt_succ_iff.mp j.isLt
        have hle : i.val + j.val ≤ a + b := Nat.add_le_add hi hj
        have hiff : i.val + j.val = a + b ↔ i.val = a ∧ j.val = b := by omega
        by_cases h : i.val = a ∧ j.val = b
        · have hsum : i.val + j.val = a + b := hiff.mpr h
          have hch : Nat.choose (i.val + j.val) (a + b) = 1 := by rw [hsum, Nat.choose_self]
          rw [hch]
          rw [if_pos h.1, if_pos h.2]
          norm_num
        · have hsum_ne : i.val + j.val ≠ a + b := fun hs => h (hiff.mp hs)
          have hlt : i.val + j.val < a + b := lt_of_le_of_ne hle hsum_ne
          have hch : Nat.choose (i.val + j.val) (a + b) = 0 := Nat.choose_eq_zero_of_lt hlt
          have hprod : (if i.val = a then (-2 : ℚ) else 0) * (if j.val = b then (1 : ℚ) else 0) = 0 := by
            by_cases h1 : i.val = a
            · have h2 : j.val ≠ b := fun h2 => h ⟨h1, h2⟩
              rw [if_pos h1, if_neg h2]; norm_num
            · rw [if_neg h1]; norm_num
          rw [hch, hprod]
          norm_num
  4. The rank of $M$ is at most 2.

    Using the entrywise identity $M_{i, j} = 1 + u_i v_j$, we express $M$ as the sum of the all-ones outer product $\mathbf{1} \mathbf{1}^T$ and the outer product $u v^T$ (`Matrix.add_apply`, `Matrix.vecMulVec_apply`). Each outer product has rank at most 1 (`Matrix.rank_vecMulVec_le`). By our subadditivity lemma, $\mathrm{rank}(M) \le 1 + 1 = 2$.

    lines 39–52

    uses Matrix.add_apply, Matrix.vecMulVec_apply, Matrix.rank_vecMulVec_le

      have hupper : Matrix.rank M ≤ 2 := by
        have hM_eq : M = Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) +
            (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ) := by
          ext i j
          rw [Matrix.add_apply, Matrix.vecMulVec_apply, Matrix.vecMulVec_apply, hchoose]
          norm_num
        rw [hM_eq]
        have h2 := hrank_add_le (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)))
          (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ)
        have h3 : (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 :=
          Matrix.rank_vecMulVec_le _ _
        have h4 : (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 :=
          Matrix.rank_vecMulVec_le _ _
        omega
  5. The rank of $M$ is at least 2.

    We consider the $2 \times 2$ submatrix on rows $\{0, a\}$ and columns $\{0, b\}$ (valid indices via `Nat.lt_succ_self`). Using the formula for $2 \times 2$ determinants (`Matrix.det_fin_two`) and our entry identity (`Matrix.submatrix_apply`, `Matrix.cons_val_zero`, `Matrix.cons_val_one`), its entries are $M_{0,0}=1$, $M_{0,b}=1$, $M_{a,0}=1$, and $M_{a,b}=-1$ because $a \ge 1$ and $b \ge 1$ ensure $0 \ne a$ and $0 \ne b$. The determinant is $1 \cdot (-1) - 1 \cdot 1 = -2 \ne 0$, so the submatrix has full rank 2 (`Matrix.rank_of_det_ne_zero`). Since submatrices cannot have higher rank than the ambient matrix (`Matrix.rank_submatrix_le`), we obtain $2 \le \mathrm{rank}(M)$.

    lines 53–64

    uses Nat.lt_succ_self, Matrix.rank_of_det_ne_zero, Matrix.det_fin_two, Matrix.submatrix_apply, Matrix.cons_val_zero, Matrix.cons_val_one, Matrix.rank_submatrix_le

      have hlower : 2 ≤ Matrix.rank M := by
        let r : Fin 2 → Fin (a+1) := ![0, ⟨a, Nat.lt_succ_self a⟩]
        let c : Fin 2 → Fin (b+1) := ![0, ⟨b, Nat.lt_succ_self b⟩]
        have hsub : (M.submatrix r c).rank = 2 := by
          apply Matrix.rank_of_det_ne_zero
          rw [Matrix.det_fin_two]
          simp only [Matrix.submatrix_apply]
          rw [hchoose, hchoose, hchoose, hchoose]
          simp only [r, c, Matrix.cons_val_zero, Matrix.cons_val_one, u, v]
          simp [show ¬ (0:ℕ) = a by omega, show ¬ (0:ℕ) = b by omega]
        have hle := Matrix.rank_submatrix_le M r c
        omega
  6. The rank of $M$ is exactly 2.

    Combining the upper bound $\mathrm{rank}(M) \le 2$ and the lower bound $2 \le \mathrm{rank}(M)$, linear integer arithmetic concludes that $\mathrm{rank}(M) = 2$.

    line 65

      omega
Matrix.rank
The rank of a matrix over a commutative ring, defined as the dimension of the range of the corresponding linear map.
Matrix.mulVecLin_add
The linear map associated with the sum of two matrices is the sum of their individual linear maps: $(M + N).\mathrm{mulVecLin} = M.\mathrm{mulVecLin} + N.\mathrm{mulVecLin}$.
Submodule.finrank_mono
If a submodule is contained in another, its dimension is less than or equal to the larger submodule's dimension: $s \le t \implies \dim(s) \le \dim(t)$.
LinearMap.range_add_le
The range of the sum of two linear maps is contained in the sum of their ranges: $\mathrm{range}(f + g) \le \mathrm{range}(f) \sqcup \mathrm{range}(g)$.
Submodule.finrank_add_le_finrank_add_finrank
The dimension of the sum of two submodules is bounded by the sum of their dimensions: $\dim(s \sqcup t) \le \dim(s) + \dim(t)$.
Nat.lt_succ_iff.mp
For natural numbers $n$ and $m$, if $n < m + 1$, then $n \le m$.
Nat.add_le_add
If $a \le b$ and $c \le d$ for natural numbers, then $a + c \le b + d$.
Nat.choose_self
For any natural number $n$, $\binom{n}{n} = 1$.
if_pos
If a condition $c$ is true, then `if c then t else e` equals $t$.
lt_of_le_of_ne
In a partial order, if $a \le b$ and $a \ne b$, then $a < b$.
Nat.choose_eq_zero_of_lt
If $n < k$ for natural numbers, then $\binom{n}{k} = 0$.
if_neg
If a condition $c$ is false, then `if c then t else e` equals $e$.
Matrix.add_apply
The $(i, j)$-th entry of the sum of two matrices $A + B$ is $A_{i,j} + B_{i,j}$.
Matrix.vecMulVec_apply
The $(i, j)$-th entry of the outer product matrix $w v^T$ is $w_i \cdot v_j$.
Matrix.rank_vecMulVec_le
The rank of an outer product matrix $w v^T$ is at most 1.
Nat.lt_succ_self
For any natural number $n$, $n < n + 1$.
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.det_fin_two
The determinant of a $2 \times 2$ matrix $A$ is $A_{0,0} A_{1,1} - A_{0,1} A_{1,0}$.
Matrix.submatrix_apply
The $(i, j)$-th entry of a submatrix $(A)_{r, c}$ is $A_{r(i), c(j)}$.
Matrix.cons_val_zero
The 0-th entry of a vector formed by prepending an element $x$ is $x$.
Matrix.cons_val_one
The 1-st entry of a vector formed by prepending an element $x$ to $u$ is $u(0)$.
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 = a + b and any positive integers a and b, the rational rank of the (a+1) x (b+1) complete (a+b)-uniform hypergraph matrix is exactly 2. -/theorem complete_uniform_hypergraph_schmidt_rank_k_eq_add (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) (a + b))) = 2 := by  classical  have hrank_add_le : ∀ {X Y : Type} [Fintype Y] (A B : Matrix X Y ℚ),      (A + B).rank ≤ A.rank + B.rank := by    intro X Y _ A B    rw [Matrix.rank, Matrix.rank, Matrix.rank, Matrix.mulVecLin_add]    exact (Submodule.finrank_mono (LinearMap.range_add_le A.mulVecLin B.mulVecLin)).trans      (Submodule.finrank_add_le_finrank_add_finrank _ _)  set M : Matrix (Fin (a+1)) (Fin (b+1)) ℚ := fun i j => (-1:ℚ) ^ (Nat.choose (i.val+j.val) (a+b)) with hM  change Matrix.rank M = 2  let u : Fin (a+1) → ℚ := fun i => if i.val = a then -2 else 0  let v : Fin (b+1) → ℚ := fun j => if j.val = b then 1 else 0  have hchoose : ∀ (i : Fin (a+1)) (j : Fin (b+1)), M i j = 1 + u i * v j := by    intro i j    rw [hM]    dsimp only [u, v]    have hi : i.val ≤ a := Nat.lt_succ_iff.mp i.isLt    have hj : j.val ≤ b := Nat.lt_succ_iff.mp j.isLt    have hle : i.val + j.val ≤ a + b := Nat.add_le_add hi hj    have hiff : i.val + j.val = a + b ↔ i.val = a ∧ j.val = b := by omega    by_cases h : i.val = a ∧ j.val = b    · have hsum : i.val + j.val = a + b := hiff.mpr h      have hch : Nat.choose (i.val + j.val) (a + b) = 1 := by rw [hsum, Nat.choose_self]      rw [hch]      rw [if_pos h.1, if_pos h.2]      norm_num    · have hsum_ne : i.val + j.val ≠ a + b := fun hs => h (hiff.mp hs)      have hlt : i.val + j.val < a + b := lt_of_le_of_ne hle hsum_ne      have hch : Nat.choose (i.val + j.val) (a + b) = 0 := Nat.choose_eq_zero_of_lt hlt      have hprod : (if i.val = a then (-2 : ℚ) else 0) * (if j.val = b then (1 : ℚ) else 0) = 0 := by        by_cases h1 : i.val = a        · have h2 : j.val ≠ b := fun h2 => h ⟨h1, h2⟩          rw [if_pos h1, if_neg h2]; norm_num        · rw [if_neg h1]; norm_num      rw [hch, hprod]      norm_num  have hupper : Matrix.rank M ≤ 2 := by    have hM_eq : M = Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) +        (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ) := by      ext i j      rw [Matrix.add_apply, Matrix.vecMulVec_apply, Matrix.vecMulVec_apply, hchoose]      norm_num    rw [hM_eq]    have h2 := hrank_add_le (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)))      (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ)    have h3 : (Matrix.vecMulVec (fun _ : Fin (a+1) => (1:ℚ)) (fun _ : Fin (b+1) => (1:ℚ)) : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 :=      Matrix.rank_vecMulVec_le _ _    have h4 : (Matrix.vecMulVec u v : Matrix (Fin (a+1)) (Fin (b+1)) ℚ).rank ≤ 1 :=      Matrix.rank_vecMulVec_le _ _    omega  have hlower : 2 ≤ Matrix.rank M := by    let r : Fin 2 → Fin (a+1) := ![0, ⟨a, Nat.lt_succ_self a⟩]    let c : Fin 2 → Fin (b+1) := ![0, ⟨b, Nat.lt_succ_self b⟩]    have hsub : (M.submatrix r c).rank = 2 := by      apply Matrix.rank_of_det_ne_zero      rw [Matrix.det_fin_two]      simp only [Matrix.submatrix_apply]      rw [hchoose, hchoose, hchoose, hchoose]      simp only [r, c, Matrix.cons_val_zero, Matrix.cons_val_one, u, v]      simp [show ¬ (0:ℕ) = a by omega, show ¬ (0:ℕ) = b by omega]    have hle := Matrix.rank_submatrix_le M r c    omega  omega
See it in the graphDiscuss this resultChallenge it