AFTD Auto-Formalizing Theoretical Domains

square_grid_graph_tripartite_info

def

For any natural number n and four-coloring c : Fin n × Fin n → Fin 4 of the vertices of the n-by-n square grid graph, square_grid_graph_tripartite_info n c is the tripartite information tree_graph_state_tripartite_info of the four parts defined by the color classes of c.

Statement

noncomputable def square_grid_graph_tripartite_info (n : ℕ) (c : Fin n × Fin n → Fin 4) : ℤ
Defined in
arXiv:2511.19585 ("Monogamy of Mutual Information in Graph States")
Verified
03 Nov 2026
Axioms
none listed
Built on 1
  • 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

square_grid_graph_tripartite_info n c is a definition that takes a natural number n : ℕ and a coloring/partition function c : Fin n × Fin n → Fin 4, and returns an integer (ℤ). It partitions the vertices of the $n \times n$ grid graph (the Cartesian/box product of two path graphs on $n$ vertices, SimpleGraph.pathGraph n □ SimpleGraph.pathGraph n) into four sets: - $A = \{ v \mid c(v) = 0 \}$ - $B = \{ v \mid c(v) = 1 \}$ - $C = \{ v \mid c(v) = 2 \}$ - $D = \{ v \mid c(v) = 3 \}$ It then computes the integer quantity: $$\text{cut\_rank}(A) + \text{cut\_rank}(B) + \text{cut\_rank}(C) + \text{cut\_rank}(D) - \text{cut\_rank}(A \cup B) - \text{cut\_rank}(A \cup C) - \text{cut\_rank}(B \cup C)$$ where for any vertex subset $X$, $\text{cut\_rank}(X)$ is the cut rank of $X$ in the grid graph.

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

/-- Tripartite information I3(A:B:C) of a four-coloring c on the n-by-n square grid graph state. -/
noncomputable def square_grid_graph_tripartite_info (n : ℕ) (c : Fin n × Fin n → Fin 4) : ℤ := letI : DecidableRel (SimpleGraph.pathGraph n □ SimpleGraph.pathGraph n).Adj := Classical.decRel _
  tree_graph_state_tripartite_info (SimpleGraph.pathGraph n □ SimpleGraph.pathGraph n)
    (Finset.univ.filter (fun v => c v = 0))
    (Finset.univ.filter (fun v => c v = 1))
    (Finset.univ.filter (fun v => c v = 2))
    (Finset.univ.filter (fun v => c v = 3))
See it in the graphDiscuss this resultChallenge it