AFTD Auto-Formalizing Theoretical Domains

square_grid_max_tripartite_info_nonneg

theoremverifiedformalization

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

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.

  1. 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.

    line 4

      unfold square_grid_graph_max_tripartite_info
  2. The 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.

    lines 5–16

    uses tree_graph_state_tripartite_info_trivial_zero

      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 _)
  3. 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'`.

    lines 17–18

    uses Finset.le_max', Finset.mem_image.mpr, Finset.mem_univ

      rw [← 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

/-- 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⟩)
See it in the graphDiscuss this resultChallenge it