square_grid_max_tripartite_info_nonneg
For every natural number n, the maximum tripartite information square_grid_graph_max_tripartite_info n of the n-by-n square grid graph state is at least 0.
Statement
theorem square_grid_max_tripartite_info_nonneg (n : ℕ) :
0 ≤ square_grid_graph_max_tripartite_info n- Formalizes
- arXiv:2511.19585 ("Monogamy of Mutual Information in Graph States")
- Verified
- 04 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- square_grid_graph_max_tripartite_infoFor any natural number n, square_grid_graph_max_tripartite_info n is the maximum tripartite information M_n over all four-colorings c on…
- square_grid_graph_tripartite_infoFor 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,…
- 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,…
- tree_graph_state_tripartite_info_trivial_zeroFor any finite graph G on type V with decidable equality and decidable adjacency, tree_graph_state_tripartite_info G Finset.univ ∅ ∅ ∅…
Read back from the Lean
For every natural number n, the maximum tripartite information of the n × n square grid graph (square_grid_graph_max_tripartite_info n) is greater than or equal to 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 maximum tripartite information of the n-by-n square grid graph state is defined as the maximum of the tripartite information over all 4-colorings of its vertices. The proof exhibits an explicit witness: the constant coloring that assigns 0 to every vertex. This coloring induces the trivial partition where one part is the entire vertex set and the other three parts are empty, which has tripartite information 0. Since the maximum over all colorings is at least the value achieved by this specific coloring, the maximum is at least 0.
The goal becomes showing that 0 is bounded above by the maximum of the tripartite information over all 4-colorings of the grid vertices.
Unfolding the definition of `square_grid_graph_max_tripartite_info` expresses it as the maximum value of `square_grid_graph_tripartite_info n` over the finite set of all colorings c : Fin n × Fin n → Fin 4.
unfold square_grid_graph_max_tripartite_infoThe constant-zero coloring on the grid graph has tripartite information equal to 0.
We evaluate the tripartite information on the constant coloring c(v) = 0 for all vertices. Under this coloring, the color class of 0 is the full vertex set Finset.univ, while the color classes of 1, 2, and 3 are empty. Rewriting the tripartite information in terms of these four sets, the lemma `tree_graph_state_tripartite_info_trivial_zero` establishes that the tripartite information of (Finset.univ, ∅, ∅, ∅) is 0.
uses
tree_graph_state_tripartite_info_trivial_zerohave hval : square_grid_graph_tripartite_info n (fun _ => (0:Fin 4)) = 0 := by unfold square_grid_graph_tripartite_info have h1 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (0:Fin 4)) = Finset.univ := by ext v; simp have h2 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (1:Fin 4)) = ∅ := by ext v; simp have h3 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (2:Fin 4)) = ∅ := by ext v; simp have h4 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (3:Fin 4)) = ∅ := by ext v; simp rw [h1, h2, h3, h4] exact @tree_graph_state_tripartite_info_trivial_zero (Fin n × Fin n) _ _ (SimpleGraph.pathGraph n □ SimpleGraph.pathGraph n) (Classical.decRel _)
The maximum tripartite information of the square grid graph state is at least 0.
Replacing 0 with the tripartite information of the constant-zero coloring, it suffices to show that the value at this coloring is at most the maximum over all colorings. Because the constant-zero coloring belongs to the universe of all colorings (Finset.mem_univ), its tripartite information belongs to the image set by `Finset.mem_image.mpr`, and therefore is bounded above by the maximum by `Finset.le_max'`.
uses
Finset.le_max',Finset.mem_image.mpr,Finset.mem_univrw [← hval] exact Finset.le_max' _ _ (Finset.mem_image.mpr ⟨fun _ => (0:Fin 4), Finset.mem_univ _, rfl⟩)
tree_graph_state_tripartite_info_trivial_zero- For any simple graph, the tripartite information on the partition where one part is the entire vertex set and the other three parts are empty is 0.
Finset.le_max'- In any linearly ordered finite set, every element of the set is less than or equal to the maximum element.
Finset.mem_image.mpr- If an element x is in s and f(x) = y, then y is in the image of s under f.
Finset.mem_univ- Every element of a finite type belongs to its universal finite set Finset.univ.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
/-- The maximum tripartite information of the n-by-n square grid graph state is nonnegative for every n. -/theorem square_grid_max_tripartite_info_nonneg (n : ℕ) : 0 ≤ square_grid_graph_max_tripartite_info n := by unfold square_grid_graph_max_tripartite_info have hval : square_grid_graph_tripartite_info n (fun _ => (0:Fin 4)) = 0 := by unfold square_grid_graph_tripartite_info have h1 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (0:Fin 4)) = Finset.univ := by ext v; simp have h2 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (1:Fin 4)) = ∅ := by ext v; simp have h3 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (2:Fin 4)) = ∅ := by ext v; simp have h4 : (Finset.univ : Finset (Fin n × Fin n)).filter (fun v => (fun _ => (0:Fin 4)) v = (3:Fin 4)) = ∅ := by ext v; simp rw [h1, h2, h3, h4] exact @tree_graph_state_tripartite_info_trivial_zero (Fin n × Fin n) _ _ (SimpleGraph.pathGraph n □ SimpleGraph.pathGraph n) (Classical.decRel _) rw [← hval] exact Finset.le_max' _ _ (Finset.mem_image.mpr ⟨fun _ => (0:Fin 4), Finset.mem_univ _, rfl⟩)