AFTD Auto-Formalizing Theoretical Domains

tree_submatrix_ker

def

For 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 of the adjacency matrix of T with row indices in the complement Sᶜ and column indices in S, viewed as a submodule of (↥S → ZMod 2).

Statement

noncomputable def tree_submatrix_ker {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] (S : Finset V) :
    Submodule (ZMod 2) (↥S → ZMod 2)
Defined in
Fuentes et al., arXiv:2511.19585; OP-827
Verified
02 Nov 2026
Axioms
none listed
Used by 7
  • dephased_supported_kernelThe part of the cut kernel whose vectors vanish at every zero-parameter vertex of the subsystem.
  • tree_submatrix_dimFor a finite simple graph T on vertex type V and a subset S : Finset V, tree_submatrix_dim T S is the dimension (finrank) over ZMod 2 of…
  • dephased_path_interval_indicator_mem_supported_kernelAn alternating interval contained in a path subsystem has its indicator in the supported cut kernel exactly when all its selected weights…
  • dephased_tree_entropyFor a finite simple graph T on vertex type V, noise profile q : V → ℝ, and subset S : Finset V, dephased_tree_entropy T q S is |S| - d_S -…
  • dephased_tree_probFor a finite simple graph T on vertex type V, a noise parameter function q : V → ℝ, a subset S : Finset V, and an additive character χ :…
  • dephased_supported_character_restrictRestrict a character of the cut kernel to its supported subspace.
  • dephased_supported_kernel_zero_edge_eqDeleting an edge between two zero-parameter vertices does not change the cut-kernel subspace supported at nonzero-parameter vertices.

Read back from the Lean

Given a finite type V with decidable equality, a simple graph T on V with decidable adjacency, and a finset S of V, tree_submatrix_ker T S is defined as the kernel (as a ZMod 2-submodule of ↥S → ZMod 2) of the linear map associated to the submatrix of the adjacency matrix of T over ZMod 2 whose rows are indexed by the complement Sᶜ and whose columns are indexed by S.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

Lean source view module on GitHub

/-- Kernel over ZMod 2 of the adjacency submatrix with rows V \ S and columns S. -/
noncomputable def tree_submatrix_ker {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] (S : Finset V) :
    Submodule (ZMod 2) (↥S → ZMod 2) := LinearMap.ker (Matrix.toLin' ((T.adjMatrix (ZMod 2)).submatrix
    (fun (r : ↥(Sᶜ : Finset V)) => (r : V)) (fun (c : ↥(S : Finset V)) => (c : V))))
See it in the graphDiscuss this resultChallenge it