AFTD Auto-Formalizing Theoretical Domains

tree_graph_state_tripartite_info_trivial_zero

theoremverified

For any finite graph G on type V with decidable equality and decidable adjacency, tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ equals 0.

Statement

theorem tree_graph_state_tripartite_info_trivial_zero
    {V : Type*} [Fintype V] [DecidableEq V]
    (G : SimpleGraph V) [DecidableRel G.Adj] :
    tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ = 0
Source
arXiv:2511.19585
Verified
02 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • simple_graph_cut_rankFor a finite type V with decidable equality, a simple graph G on V with decidable adjacency, and a finite subset X : Finset V,…
  • tree_graph_state_tripartite_infoFor a simple graph G on a finite type V with decidable equality and decidable adjacency, and four finite subsets A, B, C, D : Finset V,…
Used by 2

Read back from the Lean

For every finite type V with decidable equality and every simple graph G on V with decidable adjacency, the quantity tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ equals 0.

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 tripartite information of the partition (V, ∅, ∅, ∅) is defined as a signed sum of cut ranks of the subsets and their pairwise unions. Since any union with the empty set is trivial, the expression reduces entirely to cut ranks of the full vertex set V and the empty set ∅. The cut rank of ∅ vanishes because its submatrix has no rows, and the cut rank of V vanishes because its submatrix has no columns. Substituting these zero ranks into the formula immediately yields zero.

  1. The cut rank of the empty set in G is 0.

    The cut rank of a vertex subset X is defined as the rank over ℤ/2ℤ of the adjacency submatrix with rows indexed by X and columns indexed by Xᶜ. For X = ∅, the row index set is empty. By Matrix.rank_le_card_height, the rank of this submatrix is bounded by its number of rows, which by Fintype.card_coe and Finset.card_empty is 0. Since the rank is a natural number bounded by 0, omega concludes that it equals 0.

    lines 5–8

    uses Matrix.rank_le_card_height, Fintype.card_coe, Finset.card_empty

      dsimp [simple_graph_cut_rank]
      have h := Matrix.rank_le_card_height ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(∅ : Finset V) → V) (Subtype.val : ↥((∅ : Finset V)ᶜ) → V))
      simp only [Fintype.card_coe, Finset.card_empty] at h
      omega
  2. The cut rank of the universal set V in G is 0.

    For X = V (the universal set), the column index set is Vᶜ, which by Finset.compl_univ is ∅. By Matrix.rank_le_card_width, the rank of the submatrix is at most its number of columns, which is 0 (by Fintype.card_coe and Finset.card_empty). Since the rank is a natural number bounded by 0, omega concludes that it equals 0.

    lines 14–17

    uses Matrix.rank_le_card_width, Finset.compl_univ, Fintype.card_coe, Finset.card_empty

      dsimp [simple_graph_cut_rank]
      have h := Matrix.rank_le_card_width ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(Finset.univ : Finset V) → V) (Subtype.val : ↥((Finset.univ : Finset V)ᶜ) → V))
      simp only [Finset.compl_univ, Fintype.card_coe, Finset.card_empty] at h
      omega
  3. Expanding tree_graph_state_tripartite_info on (V, ∅, ∅, ∅) reduces to a combination of cut ranks of V and ∅.

    Unfolding the definition of tree_graph_state_tripartite_info G V ∅ ∅ ∅ yields an alternating sum of the cut ranks of the four sets V, ∅, ∅, ∅ and the pairwise unions V ∪ ∅, V ∪ ∅, and ∅ ∪ ∅. Applying Finset.union_empty simplifies these unions to V and ∅, leaving an integer linear combination involving only cut ranks of V and ∅.

    lines 24–25

    uses Finset.union_empty

      dsimp [tree_graph_state_tripartite_info]
      simp only [Finset.union_empty]
  4. The tripartite information of (V, ∅, ∅, ∅) is 0.

    Rewriting with the helper lemmas tree_graph_state_tripartite_info_trivial_zero_univ and tree_graph_state_tripartite_info_trivial_zero_empty replaces every cut rank term with 0. The resulting integer arithmetic expression 0 + 0 + 0 + 0 - 0 - 0 - 0 = 0 is evaluated and closed by ring.

    lines 26–28

    uses tree_graph_state_tripartite_info_trivial_zero_univ, tree_graph_state_tripartite_info_trivial_zero_empty

      rw [tree_graph_state_tripartite_info_trivial_zero_univ,
          tree_graph_state_tripartite_info_trivial_zero_empty]
      ring
Matrix.rank_le_card_height
The rank of a matrix over a commutative ring is at most its number of rows (the cardinality of its row index set).
Matrix.rank_le_card_width
The rank of a matrix over a commutative ring is at most its number of columns (the cardinality of its column index set).
Fintype.card_coe
The cardinality of a finite set coerced to a subtype equals the cardinality of the finset itself.
Finset.card_empty
The empty set has cardinality zero.
Finset.compl_univ
The complement of the universal set of a finite type is the empty set.
Finset.union_empty
The union of any finite set with the empty set is the set itself.
tree_graph_state_tripartite_info_trivial_zero_univ
For any finite graph, the cut rank of the full vertex set is zero.
tree_graph_state_tripartite_info_trivial_zero_empty
For any finite graph, the cut rank of the empty set is zero.

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

lemma tree_graph_state_tripartite_info_trivial_zero_empty    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    simple_graph_cut_rank G ∅ = 0 := by  dsimp [simple_graph_cut_rank]  have h := Matrix.rank_le_card_height ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(∅ : Finset V) → V) (Subtype.val : ↥((∅ : Finset V)ᶜ) → V))  simp only [Fintype.card_coe, Finset.card_empty] at h  omegalemma tree_graph_state_tripartite_info_trivial_zero_univ    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    simple_graph_cut_rank G Finset.univ = 0 := by  dsimp [simple_graph_cut_rank]  have h := Matrix.rank_le_card_width ((G.adjMatrix (ZMod 2)).submatrix (Subtype.val : ↥(Finset.univ : Finset V) → V) (Subtype.val : ↥((Finset.univ : Finset V)ᶜ) → V))  simp only [Finset.compl_univ, Fintype.card_coe, Finset.card_empty] at h  omega/-- The trivial four-partition (V, ∅, ∅, ∅) of any finite graph has tripartite information zero. -/theorem tree_graph_state_tripartite_info_trivial_zero    {V : Type*} [Fintype V] [DecidableEq V]    (G : SimpleGraph V) [DecidableRel G.Adj] :    tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅ = 0 := by  dsimp [tree_graph_state_tripartite_info]  simp only [Finset.union_empty]  rw [tree_graph_state_tripartite_info_trivial_zero_univ,      tree_graph_state_tripartite_info_trivial_zero_empty]  ring
See it in the graphDiscuss this resultChallenge it