AFTD Auto-Formalizing Theoretical Domains

square_grid_graph_max_tripartite_info

def

For any natural number n, square_grid_graph_max_tripartite_info n is the maximum tripartite information M_n over all four-colorings c on the n-by-n square grid graph state.

Statement

noncomputable def square_grid_graph_max_tripartite_info (n : ℕ) : ℤ
Defined in
arXiv:2511.19585 ("Monogamy of Mutual Information in Graph States")
Verified
03 Nov 2026
Axioms
none listed
Built on 1
Used by 1

Read back from the Lean

For a given natural number $n$, square_grid_graph_max_tripartite_info n is defined as the maximum value (as an integer), over all colorings/assignments $c : (\text{Fin } n \times \text{Fin } n) \to \text{Fin } 4$, of square_grid_graph_tripartite_info n c. Here, square_grid_graph_tripartite_info n c partitions the vertices of the $n \times n$ grid graph $G = P_n \mathbin{\square} P_n$ (the Cartesian/box product of two path graphs on $n$ vertices) into four subsets: - $A = \{ v \in \text{Fin } n \times \text{Fin } n \mid c(v) = 0 \}$ - $B = \{ v \in \text{Fin } n \times \text{Fin } n \mid c(v) = 1 \}$ - $C = \{ v \in \text{Fin } n \times \text{Fin } n \mid c(v) = 2 \}$ - $D = \{ v \in \text{Fin } n \times \text{Fin } n \mid c(v) = 3 \}$ and computes the integer value: $$R(A) + R(B) + R(C) + R(D) - R(A \cup B) - R(A \cup C) - R(B \cup C)$$ where for any vertex subset $X$, $R(X)$ is the cut-rank of $X$ in $G$ (the rank over $\mathbb{Z}/2\mathbb{Z}$ of the submatrix of the adjacency matrix of $G$ with rows indexed by $X$ and columns indexed by $X^c$).

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

/-- Maximum tripartite information M_n of the n-by-n square grid graph state over all four-partitions. -/
noncomputable def square_grid_graph_max_tripartite_info (n : ℕ) : ℤ := ((Finset.univ : Finset (Fin n × Fin n → Fin 4)).image (square_grid_graph_tripartite_info n)).max' (by
    rw [Finset.image_nonempty]
    exact Finset.univ_nonempty)
See it in the graphDiscuss this resultChallenge it