AFTD Auto-Formalizing Theoretical Domains

distinct_subset_sums_root_matrix_pos_def

theoremverified

For any natural number k ≥ 1, the root lattice matrix distinct_subset_sums_root_matrix k is positive definite.

Statement

theorem distinct_subset_sums_root_matrix_pos_def (k : ℕ) (hk : 1 ≤ k) :
  Matrix.PosDef (distinct_subset_sums_root_matrix k)
Source
arXiv:2610.26970 Proposition 3.2
Verified
26 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • distinct_subset_sums_root_matrixFor a natural number k, distinct_subset_sums_root_matrix k is the real k × k matrix H whose (i, j)-th entry is (if i = j then (1 : ℝ) else…

Read back from the Lean

For every natural number $k$ such that $1 \le k$, the $k \times k$ real matrix distinct_subset_sums_root_matrix k is positive definite (in the sense of Matrix.PosDef).

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 root lattice matrix distinct_subset_sums_root_matrix k is given by I_k - (1 / (k + 1)) J_k, where J_k is the all-ones matrix. To prove it is positive definite, the argument first checks that the matrix is Hermitian by entrywise symmetry. It then evaluates the quadratic form xᵀ M x as ∑ x_i² - (1 / (k + 1)) (∑ x_i)², bounds (∑ x_i)² ≤ k ∑ x_i² using the Cauchy–Schwarz inequality, and concludes that the quadratic form is strictly positive since k / (k + 1) < 1 and ∑ x_i² > 0 for x ≠ 0.

  1. To prove that the matrix is positive definite, it suffices to show that it is Hermitian and that its quadratic form is strictly positive for every non-zero vector.

    By `PosDef.of_dotProduct_mulVec_pos`, positive definiteness of a matrix M reduces to verifying two conditions: M is Hermitian (equal to its conjugate transpose), and for any vector x ≠ 0, the real quadratic form x* ⬝ᵥ (M *ᵥ x) is strictly positive.

    lines 4–5

    uses PosDef.of_dotProduct_mulVec_pos

      open Matrix Finset in
      refine PosDef.of_dotProduct_mulVec_pos ?_ ?_
  2. The matrix distinct_subset_sums_root_matrix k is Hermitian.

    Because the entries are real, conjugation is trivial via `star_trivial`. By definition, the (i, j) entry is δ_{ij} - 1/(k + 1). Comparing this with the (j, i) entry, we split into cases: if i = j, the diagonal entry trivially equals itself; if i ≠ j, then j ≠ i by `Ne.symm`, so both Kronecker delta terms vanish, leaving -1/(k + 1) on both sides.

    lines 6–11

    uses conjTranspose_apply, star_trivial, distinct_subset_sums_root_matrix, Ne.symm

      · ext i j
        simp only [conjTranspose_apply, star_trivial, distinct_subset_sums_root_matrix]
        by_cases h : i = j
        · subst h; rfl
        · have h' : j ≠ i := Ne.symm h
          simp [h, h']
  3. For any non-zero vector x, the quadratic form evaluates to ∑ i, (x i)^2 - (1 / (k + 1)) * (∑ i, x i)^2.

    Expanding the matrix-vector product coordinate-wise gives (M *ᵥ x)_i = x i - (1 / (k + 1)) * ∑ j, x j. Taking the inner product with x and distributing the multiplication and sum yields ∑ i, (x i)^2 - (1 / (k + 1)) * (∑ i, x i)^2. Rewriting the goal with this identity transforms the positive definiteness condition into proving this scalar expression is strictly positive.

    lines 12–22

    uses distinct_subset_sums_root_matrix, sub_mul, sum_sub_distrib, mul_sub, sq

      · intro x hx
        have h_dot : star x ⬝ᵥ (distinct_subset_sums_root_matrix k *ᵥ x) =
            ∑ i, (x i) ^ 2 - (1 / ((k : ℝ) + 1)) * (∑ i, x i) ^ 2 := by
          simp only [dotProduct, mulVec, star_trivial, distinct_subset_sums_root_matrix]
          have h (i : Fin k) : (∑ j, ((if i = j then (1 : ℝ) else 0) - 1 / ((k : ℝ) + 1)) * x j) =
              x i - (1 / ((k : ℝ) + 1)) * ∑ j, x j := by
            simp [sub_mul, sum_sub_distrib, ← mul_sum]
          simp_rw [h]
          simp only [mul_sub, sum_sub_distrib, ← sum_mul, sq]
          ring
        rw [h_dot]
  4. There exists an index i such that x i ≠ 0.

    By contraposition from the hypothesis that x ≠ 0, if x i = 0 for every index i, then x would be the zero vector, a contradiction. Thus there must be some coordinate i where x i ≠ 0.

    lines 23–27

        have hne : ∃ i, x i ≠ 0 := by
          contrapose! hx
          ext i
          exact hx i
        obtain ⟨i, hi⟩ := hne
  5. The sum of squares S = ∑ j, (x j)^2 is strictly positive.

    Since x i ≠ 0, its square (x i)^2 is strictly positive by `sq_pos_of_ne_zero`. Each term in the sum is non-negative by `sq_nonneg`, so the single term (x i)^2 is bounded by the total sum via `single_le_sum`. Since (x i)^2 > 0, the sum of squares is strictly positive.

    lines 28–31

    uses sq_pos_of_ne_zero, single_le_sum, sq_nonneg, mem_univ

        have hS : 0 < ∑ j, (x j) ^ 2 := by
          have hi_pos : 0 < (x i) ^ 2 := sq_pos_of_ne_zero hi
          have hle : (x i) ^ 2 ≤ ∑ j, (x j) ^ 2 := single_le_sum (fun j _ => sq_nonneg (x j)) (mem_univ i)
          linarith
  6. By Cauchy–Schwarz, (∑ i, x i)^2 ≤ k * ∑ i, (x i)^2.

    Applying the Cauchy–Schwarz inequality (`sum_mul_sq_le_sq_mul_sq`) to the vector x and the constant vector 1 on the index set Fin k gives (∑ i, x i * 1)^2 ≤ (∑ i, (x i)^2) * ∑ i, 1^2. The second sum simplifies to the cardinality of Fin k, which is k, establishing (∑ i, x i)^2 ≤ k * ∑ i, (x i)^2.

    lines 32–35

    uses sum_mul_sq_le_sq_mul_sq, univ, mul_one, one_pow, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul

        have hCS : (∑ i, x i) ^ 2 ≤ (k : ℝ) * ∑ i, (x i) ^ 2 := by
          have := sum_mul_sq_le_sq_mul_sq (univ : Finset (Fin k)) x (fun _ => (1 : ℝ))
          simp only [mul_one, one_pow, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul] at this
          linarith
  7. The quadratic form S - (1 / (k + 1)) * C is strictly positive, completing the proof.

    Let S = ∑ i, (x i)^2 and C = (∑ i, x i)^2. Since k ≥ 1, the denominator k + 1 is strictly positive. Dividing the Cauchy–Schwarz bound C ≤ k * S by k + 1 gives C / (k + 1) ≤ (k * S) / (k + 1). Because S > 0, we have k * S < S * (k + 1) = k * S + S, so (k * S) / (k + 1) < S. By transitivity, C / (k + 1) < S, which implies S - (1 / (k + 1)) * C > 0.

    lines 36–47

    uses div_le_div_of_nonneg_right, le_of_lt, div_lt_iff₀

        set S := ∑ i, (x i) ^ 2
        set C := (∑ i, x i) ^ 2
        have hk_real : (1 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk
        have hk1 : 0 < (k : ℝ) + 1 := by linarith
        have h1 : C / ((k : ℝ) + 1) ≤ ((k : ℝ) * S) / ((k : ℝ) + 1) :=
          div_le_div_of_nonneg_right hCS (le_of_lt hk1)
        have h2 : (1 / ((k : ℝ) + 1)) * C = C / ((k : ℝ) + 1) := by ring
        rw [h2]
        have h3 : ((k : ℝ) * S) / ((k : ℝ) + 1) < S := by
          rw [div_lt_iff₀ hk1]
          nlinarith
        linarith
card_univ
The cardinality of the universal finset of a finite type equals the cardinality of the type: |univ| = card(α).
conjTranspose_apply
The (j, i) entry of the conjugate transpose Mᴴ is the conjugate of the (i, j) entry of M.
div_lt_iff₀
For c > 0, b / c < a holds if and only if b < a * c.
div_le_div_of_nonneg_right
If a ≤ b and c ≥ 0, then a / c ≤ b / c.
distinct_subset_sums_root_matrix
The k × k matrix whose (i, j) entry is δ_{ij} - 1/(k + 1).
Fintype.card_fin
The cardinality of the standard finite type Fin n is n.
le_of_lt
Strict inequality implies non-strict inequality: a < b implies a ≤ b.
mem_univ
Every element of a finite type belongs to the universal finset univ.
mul_one
Multiplying by 1 on the right leaves an element unchanged: a * 1 = a.
mul_sub
Multiplication distributes over subtraction on the left: a * (b - c) = a * b - a * c.
Ne.symm
Disequality is symmetric: if a ≠ b, then b ≠ a.
nsmul_eq_mul
Natural number scalar multiplication equals multiplication by the coerced natural number: n • a = ↑n * a.
one_pow
Any power of 1 is 1: 1^n = 1.
PosDef.of_dotProduct_mulVec_pos
A matrix M is positive definite if M is Hermitian and x* ⬝ᵥ (M *ᵥ x) > 0 for all non-zero vectors x.
single_le_sum
A single non-negative term is bounded by the sum over the finset: if each f(x) ≥ 0 and a ∈ s, then f(a) ≤ ∑ x ∈ s, f(x).
sq
The square of an element is its product with itself: a^2 = a * a.
sq_nonneg
In an ordered ring, the square of any element is non-negative: 0 ≤ a^2.
sq_pos_of_ne_zero
If an element is non-zero, its square is strictly positive: a ≠ 0 implies 0 < a^2.
star_trivial
On the real numbers (or any trivial star ring), the star operation is the identity: star r = r.
sub_mul
Multiplication distributes over subtraction on the right: (a - b) * c = a * c - b * c.
sum_const
Summing a constant b over a finset s equals |s| • b.
sum_mul_sq_le_sq_mul_sq
The Cauchy–Schwarz inequality for sums: (∑ i ∈ s, f(i) * g(i))^2 ≤ (∑ i ∈ s, f(i)^2) * ∑ i ∈ s, g(i)^2.
sum_sub_distrib
The sum of a difference of functions equals the difference of their sums.
univ
The finset of all elements of a finite type.

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

/-- The root lattice matrix H is positive definite for every k ≥ 1. -/theorem distinct_subset_sums_root_matrix_pos_def (k : ℕ) (hk : 1 ≤ k) :  Matrix.PosDef (distinct_subset_sums_root_matrix k) := by  open Matrix Finset in  refine PosDef.of_dotProduct_mulVec_pos ?_ ?_  · ext i j    simp only [conjTranspose_apply, star_trivial, distinct_subset_sums_root_matrix]    by_cases h : i = j    · subst h; rfl    · have h' : j ≠ i := Ne.symm h      simp [h, h']  · intro x hx    have h_dot : star x ⬝ᵥ (distinct_subset_sums_root_matrix k *ᵥ x) =        ∑ i, (x i) ^ 2 - (1 / ((k : ℝ) + 1)) * (∑ i, x i) ^ 2 := by      simp only [dotProduct, mulVec, star_trivial, distinct_subset_sums_root_matrix]      have h (i : Fin k) : (∑ j, ((if i = j then (1 : ℝ) else 0) - 1 / ((k : ℝ) + 1)) * x j) =          x i - (1 / ((k : ℝ) + 1)) * ∑ j, x j := by        simp [sub_mul, sum_sub_distrib, ← mul_sum]      simp_rw [h]      simp only [mul_sub, sum_sub_distrib, ← sum_mul, sq]      ring    rw [h_dot]    have hne : ∃ i, x i ≠ 0 := by      contrapose! hx      ext i      exact hx i    obtain ⟨i, hi⟩ := hne    have hS : 0 < ∑ j, (x j) ^ 2 := by      have hi_pos : 0 < (x i) ^ 2 := sq_pos_of_ne_zero hi      have hle : (x i) ^ 2 ≤ ∑ j, (x j) ^ 2 := single_le_sum (fun j _ => sq_nonneg (x j)) (mem_univ i)      linarith    have hCS : (∑ i, x i) ^ 2 ≤ (k : ℝ) * ∑ i, (x i) ^ 2 := by      have := sum_mul_sq_le_sq_mul_sq (univ : Finset (Fin k)) x (fun _ => (1 : ℝ))      simp only [mul_one, one_pow, sum_const, card_univ, Fintype.card_fin, nsmul_eq_mul] at this      linarith    set S := ∑ i, (x i) ^ 2    set C := (∑ i, x i) ^ 2    have hk_real : (1 : ℝ) ≤ (k : ℝ) := by exact_mod_cast hk    have hk1 : 0 < (k : ℝ) + 1 := by linarith    have h1 : C / ((k : ℝ) + 1) ≤ ((k : ℝ) * S) / ((k : ℝ) + 1) :=      div_le_div_of_nonneg_right hCS (le_of_lt hk1)    have h2 : (1 / ((k : ℝ) + 1)) * C = C / ((k : ℝ) + 1) := by ring    rw [h2]    have h3 : ((k : ℝ) * S) / ((k : ℝ) + 1) < S := by      rw [div_lt_iff₀ hk1]      nlinarith    linarith
See it in the graphDiscuss this resultChallenge it