AFTD Auto-Formalizing Theoretical Domains

exists_nonzero_two_fractional_standardized_laplacian_four

theoremverified

There exists a nonzero 4 × 4 real matrix that is a standardized Laplacian with at most two fractional off-diagonal entries per row (e.g. the standardized Laplacian of a directed 4-cycle, whose off-diagonal entries are all 0 or -1/4).

Statement

theorem exists_nonzero_two_fractional_standardized_laplacian_four :
    ∃ L : Matrix (Fin 4) (Fin 4) ℝ, is_standardized_laplacian_two_fractional 4 L ∧ L ≠ 0
Source
step towards op_465_standardized_laplacian_order_four_polygon_conjecture
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • is_standardized_laplacian_two_fractionalA real matrix L of order n is a standardized Laplacian with at most two fractional entries per row if L is a standardized Laplacian and…
  • is_standardized_laplacianA standardized Laplacian matrix of order n is a real n x n matrix with zero row sums and off-diagonal entries in [-1/n, 0].

The proof, explained

We exhibit an explicit 4 × 4 matrix L with diagonal blocks [1/4, -1/4; -1/4, 1/4] and zeros elsewhere. Its row sums are all zero, all off-diagonal entries are either -1/4 or 0 (and hence lie in [-1/4, 0] with none strictly between -1/4 and 0), and L 0 0 = 1/4 ≠ 0, confirming that L is a nonzero standardized Laplacian with at most two fractional off-diagonal entries per row.

  1. No off-diagonal entry of the witness matrix lies strictly between -1/4 and 0.

    By unfolding the definition of the matrix and checking all 16 index pairs (i, j), whenever j = i the inequality contradicts the hypothesis j ≠ i, and whenever j ≠ i the entry is either -1/4 or 0, neither of which is strictly between -1/4 and 0.

    lines 14–22

      dsimp [exists_nonzero_two_fractional_standardized_laplacian_four_matrix]
      fin_cases i <;> fin_cases j
      all_goals
        first
        | exact (hij rfl).elim
        | intro h
          rcases h with ⟨h1, h2⟩
          revert h1 h2
          norm_num
  2. It suffices to show that the concrete matrix L satisfies the standardized Laplacian conditions and is nonzero.

    We supply the concrete matrix L as the existential witness and split the goal into verifying its row sums, off-diagonal bounds, fractional entry count, and nonzeroness.

    lines 27–30

    uses exists_nonzero_two_fractional_standardized_laplacian_four_matrix

      use exists_nonzero_two_fractional_standardized_laplacian_four_matrix
      constructor
      · constructor
        · constructor
  3. Each row of L sums to 0.

    Evaluating the sum over the four indices in each of the four rows gives 1/4 - 1/4 + 0 + 0 = 0 for the first two rows and 0 + 0 + 0 + 0 = 0 for the last two.

    lines 31–32

    uses Fin.sum_univ_four, exists_nonzero_two_fractional_standardized_laplacian_four_matrix

          · intro i
            fin_cases i <;> { simp [Fin.sum_univ_four, exists_nonzero_two_fractional_standardized_laplacian_four_matrix]; try norm_num }
  4. All off-diagonal entries of L lie in the interval [-1/4, 0].

    Exhaustive check on all 16 index pairs (i, j): if i = j there is a contradiction with i ≠ j, and if i ≠ j each entry (-1/4 or 0) satisfies -1/4 ≤ L i j ≤ 0.

    lines 33–34

    uses exists_nonzero_two_fractional_standardized_laplacian_four_matrix

          · intro i j hij
            fin_cases i <;> fin_cases j <;> first | contradiction | norm_num [exists_nonzero_two_fractional_standardized_laplacian_four_matrix]
  5. Each row of L has at most two fractional off-diagonal entries.

    By the helper lemma, no off-diagonal entry lies in (-1/4, 0), so the set of such entries in any row is empty. Its cardinality is 0, which is at most 2.

    lines 35–42

    uses Finset.filter_false_of_mem, Finset.card_eq_zero.mpr, exists_nonzero_two_fractional_standardized_laplacian_four_matrix_no_frac

        · intro i
          have h_empty : (Finset.filter (fun j => j ≠ i ∧ -1 / ↑(4 : ℕ) < exists_nonzero_two_fractional_standardized_laplacian_four_matrix i j ∧
              exists_nonzero_two_fractional_standardized_laplacian_four_matrix i j < 0) Finset.univ) = ∅ := by
            apply Finset.filter_false_of_mem
            intro j _ hj
            exact exists_nonzero_two_fractional_standardized_laplacian_four_matrix_no_frac i j hj.1 hj.2
          rw [Finset.card_eq_zero.mpr h_empty]
          norm_num
  6. L is not the zero matrix.

    If L were zero, its top-left entry L 0 0 would be 0, but by definition L 0 0 = 1/4, a contradiction.

    lines 43–49

    uses exists_nonzero_two_fractional_standardized_laplacian_four_matrix

      · intro h
        have h0 : exists_nonzero_two_fractional_standardized_laplacian_four_matrix 0 0 = 0 := by
          rw [h]
          rfl
        revert h0
        dsimp [exists_nonzero_two_fractional_standardized_laplacian_four_matrix]
        norm_num
exists_nonzero_two_fractional_standardized_laplacian_four_matrix
a concrete 4x4 matrix with entries in ℝ
exists_nonzero_two_fractional_standardized_laplacian_four_matrix_no_frac
no off-diagonal entry of the witness matrix lies strictly between -1/4 and 0
Fin.sum_univ_four
the sum over the four elements of Fin 4 equals the sum of values at 0, 1, 2, and 3
Finset.filter_false_of_mem
filtering a finset by a predicate that holds nowhere yields the empty set
Finset.card_eq_zero.mpr
a finite set has cardinality zero if and only if it is empty

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

/-- A concrete nonzero 4x4 matrix with row sums 0 and off-diagonal entries in [-1/4, 0]. -/noncomputable def exists_nonzero_two_fractional_standardized_laplacian_four_matrix :    Matrix (Fin 4) (Fin 4) ℝ :=  !![ 1/4, -1/4,  0,    0;     -1/4,  1/4,  0,    0;        0,    0,  0,    0;        0,    0,  0,    0]/-- The off-diagonal entries of the concrete matrix are never strictly between -1/4 and 0. -/lemma exists_nonzero_two_fractional_standardized_laplacian_four_matrix_no_frac    (i j : Fin 4) (hij : j ≠ i) :    ¬ (-1 / ↑(4 : ℕ) < exists_nonzero_two_fractional_standardized_laplacian_four_matrix i j ∧       exists_nonzero_two_fractional_standardized_laplacian_four_matrix i j < 0) := by  dsimp [exists_nonzero_two_fractional_standardized_laplacian_four_matrix]  fin_cases i <;> fin_cases j  all_goals    first    | exact (hij rfl).elim    | intro h      rcases h with ⟨h1, h2⟩      revert h1 h2      norm_num/-- Sanity witness: the two-fractional standardized Laplacians of order 4 are a nonempty class containing a nonzero matrix. -/theorem exists_nonzero_two_fractional_standardized_laplacian_four :    ∃ L : Matrix (Fin 4) (Fin 4) ℝ, is_standardized_laplacian_two_fractional 4 L ∧ L ≠ 0 := by  use exists_nonzero_two_fractional_standardized_laplacian_four_matrix  constructor  · constructor    · constructor      · intro i        fin_cases i <;> { simp [Fin.sum_univ_four, exists_nonzero_two_fractional_standardized_laplacian_four_matrix]; try norm_num }      · intro i j hij        fin_cases i <;> fin_cases j <;> first | contradiction | norm_num [exists_nonzero_two_fractional_standardized_laplacian_four_matrix]    · intro i      have h_empty : (Finset.filter (fun j => j ≠ i ∧ -1 / ↑(4 : ℕ) < exists_nonzero_two_fractional_standardized_laplacian_four_matrix i j ∧          exists_nonzero_two_fractional_standardized_laplacian_four_matrix i j < 0) Finset.univ) = ∅ := by        apply Finset.filter_false_of_mem        intro j _ hj        exact exists_nonzero_two_fractional_standardized_laplacian_four_matrix_no_frac i j hj.1 hj.2      rw [Finset.card_eq_zero.mpr h_empty]      norm_num  · intro h    have h0 : exists_nonzero_two_fractional_standardized_laplacian_four_matrix 0 0 = 0 := by      rw [h]      rfl    revert h0    dsimp [exists_nonzero_two_fractional_standardized_laplacian_four_matrix]    norm_num
See it in the graphDiscuss this resultChallenge it