square_grid_coloring_is_four_partition
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$.
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.
refine ⟨?_, ?_, ?_, ?_, ?_, ?_, ?_⟩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.
uses
Finset.disjoint_filteriterate 6 rw [Finset.disjoint_filter] intro x _ hx hy omegaThe 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}$.
uses
Finset.mem_union,Finset.mem_filter,Finset.mem_univ,true_andext x simp only [Finset.mem_union, Finset.mem_filter, Finset.mem_univ, true_and]
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.
have : c x = 0 ∨ c x = 1 ∨ c x = 2 ∨ c x = 3 := by omega
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.
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$.
- The tactic `omega` automatically treats elements of `Fin 4` as natural numbers strictly less than 4, which closes both the impossibility of $c(x) = i$ and $c(x) = j$ for distinct $i, j$ and the exhaustive disjunction $c(x) \in \{0, 1, 2, 3\}$.
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 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