AFTD Auto-Formalizing Theoretical Domains

dephased_supported_kernel_zero_edge_eq

theoremverified

Deleting an edge between two zero-parameter vertices does not change the cut-kernel subspace supported at nonzero-parameter vertices.

Statement

theorem dephased_supported_kernel_zero_edge_eq {V : Type*} [Fintype V] [DecidableEq V] (G G' : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel G'.Adj] (u v : V) (hedge : ∀ x y : V, G'.Adj x y ↔ G.Adj x y ∧ ¬ ((x = u ∧ y = v) ∨ (x = v ∧ y = u))) (q : V → ℝ) (hu : q u = 0) (hv : q v = 0) (S : Finset V) : dephased_supported_kernel G q S = dephased_supported_kernel G' q S
Source
Linear-algebra half of the zero-edge entropy reduction for OP-827; checked numerically in experiments 22383 and 22398.
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • dephased_supported_kernelThe part of the cut kernel whose vectors vanish at every zero-parameter vertex of the subsystem.
  • tree_submatrix_kerFor a finite simple graph T on vertex type V and a subset S : Finset V, tree_submatrix_ker T S is the kernel over ZMod 2 of the submatrix…

Lean source view module on GitHub

theorem dephased_supported_kernel_zero_edge_eq {V : Type*} [Fintype V] [DecidableEq V] (G G' : SimpleGraph V) [DecidableRel G.Adj] [DecidableRel G'.Adj] (u v : V) (hedge : ∀ x y : V, G'.Adj x y ↔ G.Adj x y ∧ ¬ ((x = u ∧ y = v) ∨ (x = v ∧ y = u))) (q : V → ℝ) (hu : q u = 0) (hv : q v = 0) (S : Finset V) : dephased_supported_kernel G q S = dephased_supported_kernel G' q S := by
  classical
  ext x
  change (x ∈ tree_submatrix_ker G S ∧ (∀ i : ↥S, q i.1 = 0 → x i = 0)) ↔
    (x ∈ tree_submatrix_ker G' S ∧ (∀ i : ↥S, q i.1 = 0 → x i = 0))
  have hsame (hx : ∀ i : ↥S, q i.1 = 0 → x i = 0) :
      Matrix.toLin' ((G.adjMatrix (ZMod 2)).submatrix
        (fun (r : ↥(Sᶜ : Finset V)) => (r : V)) (fun (c : ↥S) => (c : V))) x =
      Matrix.toLin' ((G'.adjMatrix (ZMod 2)).submatrix
        (fun (r : ↥(Sᶜ : Finset V)) => (r : V)) (fun (c : ↥S) => (c : V))) x := by
    ext r
    simp only [Matrix.toLin'_apply, Matrix.mulVec, dotProduct, Matrix.submatrix_apply]
    apply Finset.sum_congr rfl
    intro c hc
    by_cases hz : q c.1 = 0
    · simp [hx c hz]
    · have hcu : c.1 ≠ u := by intro h; exact hz (h ▸ hu)
      have hcv : c.1 ≠ v := by intro h; exact hz (h ▸ hv)
      have hadj : G.Adj r.1 c.1 ↔ G'.Adj r.1 c.1 := by
        rw [hedge]
        simp [hcu, hcv]
      simp only [SimpleGraph.adjMatrix_apply]
      split_ifs <;> simp_all
  constructor
  · rintro ⟨h, hx⟩
    refine ⟨?_, hx⟩
    change Matrix.toLin' _ x = 0 at h ⊢
    rwa [← hsame hx]
  · rintro ⟨h, hx⟩
    refine ⟨?_, hx⟩
    change Matrix.toLin' _ x = 0 at h ⊢
    rwa [hsame hx]
See it in the graphDiscuss this resultChallenge it