AFTD Auto-Formalizing Theoretical Domains

tree_submatrix_dim

def

For 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 the kernel tree_submatrix_ker T S.

Statement

noncomputable def tree_submatrix_dim {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] (S : Finset V) : ℕ
Defined in
Fuentes et al., arXiv:2511.19585; OP-827
Verified
02 Nov 2026
Axioms
none listed
Built on 1
  • 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…
Used by 2
  • 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 χ :…

Read back from the Lean

Given a finite type V with decidable equality, a simple graph T on V with decidable adjacency, and a subset S : Finset V, tree_submatrix_dim T S is defined as the dimension (vector space rank over ZMod 2) of the kernel of the linear map defined by the submatrix of T's adjacency matrix over ZMod 2 with rows indexed by Sᶜ (the complement of S) and columns 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

/-- Dimension over ZMod 2 of the kernel of the adjacency submatrix for S. -/
noncomputable def tree_submatrix_dim {V : Type*} [Fintype V] [DecidableEq V]
    (T : SimpleGraph V) [DecidableRel T.Adj] (S : Finset V) : ℕ := Module.finrank (ZMod 2) (tree_submatrix_ker T S)
See it in the graphDiscuss this resultChallenge it