AFTD Auto-Formalizing Theoretical Domains

square_grid_coloring_is_four_partition

theoremverified

For any natural number n and any four-coloring c : Fin n × Fin n → Fin 4, the four color classes of c are pairwise disjoint and their union is the universal finset, so they satisfy is_four_partition.

Statement

theorem square_grid_coloring_is_four_partition (n : ℕ) (c : Fin n × Fin n → Fin 4) :
    is_four_partition
      (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))
Source
arXiv:2511.19585 ("Monogamy of Mutual Information in Graph States")
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • is_four_partitionGiven a finite type V with decidable equality and four finite subsets A, B, C, D : Finset V, is_four_partition A B C D is the proposition…

Read back from the Lean

For every natural number $n$ and every function $c : \text{Fin } n \times \text{Fin } n \to \text{Fin } 4$, the fiber subsets $\{v \mid c(v) = 0\}$, $\{v \mid c(v) = 1\}$, $\{v \mid c(v) = 2\}$, and $\{v \mid c(v) = 3\}$ form a four-partition (is_four_partition) of $\text{Fin } n \times \text{Fin } n$.

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 theorem shows that the four color classes of any four-coloring of the grid form a valid four-partition. By definition of `is_four_partition`, this requires showing that the six pairs of color classes are pairwise disjoint and that their union is the entire set of vertices. Disjointness holds because a vertex cannot simultaneously have two different colors, and the union covers all vertices because every value in $\mathrm{Fin}\; 4$ is $0, 1, 2,$ or $3$.

  1. To prove that the four color classes form a four-partition, it suffices to prove seven subgoals: six pairwise disjointness conditions and one covering condition.

    The definition of `is_four_partition` requires that each of the $\binom{4}{2} = 6$ pairs of color classes are disjoint, and that their union equals the universal finset `Finset.univ`. The `refine` tactic decomposes the conjunction into these seven separate goals.

    line 8

      refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩
  2. The four color classes are pairwise disjoint. automation

    For each of the six pairs of distinct colors, `Finset.disjoint_filter` rewrites the disjointness condition into showing that no vertex $x$ can satisfy both $c(x) = i$ and $c(x) = j$. Assuming both equalities hold for a vertex $x$, the `omega` tactic derives a contradiction from $i \neq j$ and closes the goal.

    lines 9–12

    uses Finset.disjoint_filter

      iterate 6
        rw [Finset.disjoint_filter]
        intro x _ hx hy
        omega
  3. The covering condition reduces to showing that for every vertex $x$, $c(x)$ is $0, 1, 2,$ or $3$.

    By extensionality (`ext x`), the union equals the universal set if every vertex $x$ belongs to the union. Simplifying set membership across unions, filters, and the universal set using `Finset.mem_union`, `Finset.mem_filter`, `Finset.mem_univ`, and `true_and`, this is equivalent to $((c(x) = 0 \lor c(x) = 1) \lor c(x) = 2) \lor c(x) = 3 \leftrightarrow \mathrm{True}$.

    lines 13–14

    uses Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and

      ext x
      simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and]
  4. For every vertex $x$, its color $c(x)$ is $0, 1, 2,$ or $3$. automation

    Since $c(x) \in \mathrm{Fin}\; 4$, its numerical value is a natural number strictly less than 4, so it must be $0, 1, 2,$ or $3$. The `omega` tactic proves this disjunction automatically.

    line 15

      have : c x = 0 ∨ c x = 1 ∨ c x = 2 ∨ c x = 3 := by omega
  5. The union of the four color classes is the universal set.

    Having proved that $c(x)$ is one of the four colors, propositional logic (`tauto`) finishes the equivalence with $\mathrm{True}$, completing the proof.

    line 16

      tauto
Finset.disjoint_filter
Two subsets obtained by filtering the same finset by predicates $p$ and $q$ are disjoint if and only if no element satisfies both $p$ and $q$.
Finset.mem_union
An element belongs to the union of two finsets if and only if it belongs to at least one of them.
Finset.mem_filter
An element belongs to a filtered finset if and only if it belongs to the original finset and satisfies the predicate.
Finset.mem_univ
Every element of a finite type belongs to the universal finset `Finset.univ`.
true_and
The conjunction $\mathrm{True} \land p$ simplifies to $p$.

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 four color classes of any four-coloring on Fin n × Fin n form a valid four-partition. -/theorem square_grid_coloring_is_four_partition (n : ℕ) (c : Fin n × Fin n → Fin 4) :    is_four_partition      (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)) := by  refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩  iterate 6    rw [Finset.disjoint_filter]    intro x _ hx hy    omega  ext x  simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and]  have : c x = 0 ∨ c x = 1 ∨ c x = 2 ∨ c x = 3 := by omega  tauto
See it in the graphDiscuss this resultChallenge it