anti_ramsey_k5_lower_bound_nineteen
There exists a symmetric 3-edge-coloring of the complete graph K_19 on vertices ZMod 19 such that every 5-element vertex subset contains at least one edge of each of the three colors, implying that the three-colored anti-Ramsey number satisfies xi(K_5) >= 19.
Statement
theorem anti_ramsey_k5_lower_bound_nineteen :
∃ c : ZMod 19 → ZMod 19 → Fin 3,
(∀ x y, c x y = c y x) ∧
∀ s : Finset (ZMod 19), s.card = 5 →
∀ col : Fin 3, ∃ u ∈ s, ∃ v ∈ s, u ≠ v ∧ c u v = col- Formalizes
- arXiv:2611.03878 Theorem 3.2
- Verified
- 05 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
Read back from the Lean
There exists a function $c : \mathbb{Z}/19\mathbb{Z} \to \mathbb{Z}/19\mathbb{Z} \to \mathrm{Fin}\;3$ such that: 1. $c$ is symmetric: for all $x, y \in \mathbb{Z}/19\mathbb{Z}$, $c(x, y) = c(y, x)$, and 2. For every subset $s \subseteq \mathbb{Z}/19\mathbb{Z}$ with cardinality $|s| = 5$, and for every color $\mathrm{col} \in \mathrm{Fin}\;3$, there exist distinct vertices $u, v \in s$ such that $c(u, v) = \mathrm{col}$.
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 is proved by exhibiting an explicit, symmetric 3-edge-coloring of the complete graph K_19 on vertex set ZMod 19 whose color classes are determined by difference pairs. To verify that every 5-element vertex subset contains at least one edge of each color, the property is formulated as a decidable Boolean check over all 11,628 sublists of length 5 of the vertices. Lean verifies this check by direct kernel evaluation (`rfl`). For any given 5-element finset of vertices, filtering the vertex list produces a 5-element sublist, from which edges of all three colors are extracted using the verified check.
The exhaustive check `anti_ramsey_k5_lower_bound_nineteen_check_all_sublists` evaluates to `true`.
By definition and direct computation (`rfl`), Lean evaluates the decision procedure over all 11,628 sublists of length 5 of the 19 vertices, confirming that each sublist contains an edge of each of the three colors.
rflThe edge coloring function is symmetric: `c x y = c y x` for all `x, y ∈ ZMod 19`.
Reverting `x` and `y` generalizes the equality to a universal statement over all pairs in `ZMod 19`. The `decide` tactic checks all 19 × 19 = 361 cases exhaustively.
revert x y decideConverting the list of all 19 vertices to a finset yields `Finset.univ`.
By extensionality (`ext x`), it suffices to show that each `x ∈ ZMod 19` is in the finset if and only if `x ∈ Finset.univ`. Rewriting with `List.mem_toFinset`, `Finset.mem_univ`, and `iff_true` reduces this to checking that every element is in the list `[0, ..., 18]`, which `decide` verifies exhaustively.
uses
List.mem_toFinset,Finset.mem_univ,iff_trueext x simp only [List.mem_toFinset, Finset.mem_univ, iff_true] revert x decide
For any finset `s ⊆ ZMod 19`, filtering the universal list of vertices by membership in `s` gives a list of length equal to `s.card`.
First, the universal list has no duplicate elements (`Nodup`, proved by `decide`). Second, converting the filtered list to a finset yields `s` (`h_toFinset`), using `List.mem_toFinset`, `List.mem_filter`, `decide_eq_true_eq`, `anti_ramsey_k5_lower_bound_nineteen_univ_toFinset`, and `List.mem_toFinset.mp`. Finally, by `List.toFinset_card_of_nodup`, the length of the filtered list equals the cardinality of its underlying finset, which is `s.card`.
uses
List.mem_toFinset,List.mem_filter,decide_eq_true_eq,anti_ramsey_k5_lower_bound_nineteen_univ_toFinset,List.mem_toFinset.mp,List.toFinset_card_of_noduphave h_nodup : anti_ramsey_k5_lower_bound_nineteen_univ.Nodup := by decide have h_toFinset : (anti_ramsey_k5_lower_bound_nineteen_univ.filter (· ∈ s)).toFinset = s := by ext x simp only [List.mem_toFinset, List.mem_filter, decide_eq_true_eq] constructor · rintro ⟨-, hx⟩; exact hx · intro hx refine ⟨?_, hx⟩ have : x ∈ anti_ramsey_k5_lower_bound_nineteen_univ.toFinset := by simp [anti_ramsey_k5_lower_bound_nineteen_univ_toFinset] exact List.mem_toFinset.mp this rw [← List.toFinset_card_of_nodup (h_nodup.filter _)] rw [h_toFinset]
If a list `l` passes the color check, then for every color in `Fin 3`, there are distinct vertices `u, v ∈ l` colored with that color.
Every color `col : Fin 3` belongs to `[0, 1, 2]` by exhaustive case analysis (`fin_cases col`). Unfolding `anti_ramsey_k5_lower_bound_nineteen_check_list` and using `List.all_eq_true` specializes the check to `col`. Rewriting with `List.any_eq_true` twice extracts vertices `u, v ∈ l`, and simplifying with `Bool.and_eq_true` and `decide_eq_true_iff` yields `u ≠ v` and `c u v = col`.
uses
anti_ramsey_k5_lower_bound_nineteen_check_list,List.all_eq_true,List.any_eq_true,Bool.and_eq_true,decide_eq_true_iffhave hcol : col ∈ ([0, 1, 2] : List (Fin 3)) := by fin_cases col <;> simp rw [anti_ramsey_k5_lower_bound_nineteen_check_list, List.all_eq_true] at h have h_any := h col hcol rw [List.any_eq_true] at h_any rcases h_any with ⟨u, hu, hu_prop⟩ rw [List.any_eq_true] at hu_prop rcases hu_prop with ⟨v, hv, hv_prop⟩ simp only [Bool.and_eq_true, decide_eq_true_iff] at hv_prop exact ⟨u, hu, v, hv, hv_prop.1, hv_prop.2⟩
Witnessing the coloring function `c` and proving its symmetry reduces the problem to showing every 5-element subset contains all three colors.
We provide `anti_ramsey_k5_lower_bound_nineteen_c` as the witness for the existential quantifier with `use`, and discharge symmetry with the lemma `anti_ramsey_k5_lower_bound_nineteen_c_symm`, leaving the condition on 5-element subsets.
uses
anti_ramsey_k5_lower_bound_nineteen_c_symmuse anti_ramsey_k5_lower_bound_nineteen_c refine ⟨anti_ramsey_k5_lower_bound_nineteen_c_symm, ?_⟩
Any 5-element finset `s` corresponds to a sublist `l` of length 5 of the universal vertex list.
Given a subset `s` with `s.card = 5` and a target color `col`, we define `l` as the universal vertex list filtered by membership in `s`. By `List.filter_sublist`, `l` is a sublist of the universal list. By `anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card` and `s.card = 5`, `l` has length 5. Therefore, `l` belongs to `List.sublistsLen 5 anti_ramsey_k5_lower_bound_nineteen_univ` by `List.mem_sublistsLen`.
uses
List.filter_sublist,anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card,List.mem_sublistsLenintro s hs col let l := anti_ramsey_k5_lower_bound_nineteen_univ.filter (· ∈ s) have hl_sub : l.Sublist anti_ramsey_k5_lower_bound_nineteen_univ := List.filter_sublist have hl_len : l.length = 5 := by rw [← hs] exact anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card s have hl_mem : l ∈ List.sublistsLen 5 anti_ramsey_k5_lower_bound_nineteen_univ := by rw [List.mem_sublistsLen] exact ⟨hl_sub, hl_len⟩
The sublist `l` satisfies `anti_ramsey_k5_lower_bound_nineteen_check_list l = true`.
We invoke `anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq`. Unfolding `anti_ramsey_k5_lower_bound_nineteen_check_all_sublists` and using `List.all_eq_true` establishes that every length-5 sublist satisfies the check. Instantiating this for `l` (which belongs to `sublistsLen 5`) gives `anti_ramsey_k5_lower_bound_nineteen_check_list l = true`.
uses
anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq,anti_ramsey_k5_lower_bound_nineteen_check_all_sublists,List.all_eq_truehave h_all : anti_ramsey_k5_lower_bound_nineteen_check_all_sublists = true := anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq have hl_check : anti_ramsey_k5_lower_bound_nineteen_check_list l = true := by rw [anti_ramsey_k5_lower_bound_nineteen_check_all_sublists, List.all_eq_true] at h_all exact h_all l hl_mem
There exist distinct vertices `u, v ∈ s` with `c u v = col`, completing the proof.
Applying `anti_ramsey_k5_lower_bound_nineteen_check_list_prop` to the check on `l` extracts distinct vertices `u, v ∈ l` with `c u v = col`. Rewriting with `List.mem_filter` and `decide_eq_true_eq` shows that `u ∈ s` and `v ∈ s`, providing the required edge of color `col` in the subset `s`.
uses
anti_ramsey_k5_lower_bound_nineteen_check_list_prop,List.mem_filter,decide_eq_true_eqrcases anti_ramsey_k5_lower_bound_nineteen_check_list_prop hl_check col with ⟨u, hu, v, hv, huv, hcol⟩ rw [List.mem_filter] at hu hv simp only [decide_eq_true_eq] at hu hv exact ⟨u, hu.2, v, hv.2, huv, hcol⟩
List.mem_toFinset- An element belongs to `l.toFinset` if and only if it belongs to the list `l`.
Finset.mem_univ- Every element of a finite type belongs to the universal finset `Finset.univ`.
iff_true- An equivalence `p ↔ True` simplifies to `p`.
List.mem_filter- An element `x` belongs to `List.filter p as` if and only if `x ∈ as` and `p x = true`.
decide_eq_true_eq- The equality `decide p = true` is definitionally equal to `p`.
anti_ramsey_k5_lower_bound_nineteen_univ_toFinset- The finset formed from the vertex list `anti_ramsey_k5_lower_bound_nineteen_univ` is equal to `Finset.univ` on ZMod 19.
List.mem_toFinset.mp- If an element belongs to `l.toFinset`, then it belongs to the list `l`.
List.toFinset_card_of_nodup- For any list `l` with no duplicate elements, the cardinality of `l.toFinset` equals the length of `l`.
anti_ramsey_k5_lower_bound_nineteen_check_list- The boolean function that tests whether all three colors appear between distinct vertices in a given list.
List.all_eq_true- A list satisfies `l.all p = true` if and only if `p x = true` for every element `x ∈ l`.
List.any_eq_true- A list satisfies `l.any p = true` if and only if there exists some element `x ∈ l` with `p x = true`.
Bool.and_eq_true- The boolean conjunction `a && b = true` holds if and only if both `a = true` and `b = true`.
decide_eq_true_iff- The boolean decision `decide p = true` is equivalent to the proposition `p`.
anti_ramsey_k5_lower_bound_nineteen_c_symm- The edge coloring function `anti_ramsey_k5_lower_bound_nineteen_c` is symmetric: `c x y = c y x` for all `x, y ∈ ZMod 19`.
List.filter_sublist- Filtering a list produces a sublist of the original list.
anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card- Filtering the universal vertex list by membership in a finset `s` produces a list whose length equals `s.card`.
List.mem_sublistsLen- A list `l'` belongs to `List.sublistsLen n l` if and only if `l'` is a sublist of `l` and has length `n`.
anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq- The exhaustive boolean check over all 5-element sublists of vertices evaluates to `true`.
anti_ramsey_k5_lower_bound_nineteen_check_all_sublists- The boolean function asserting that every 5-element sublist of the universal vertex list passes the list color check.
anti_ramsey_k5_lower_bound_nineteen_check_list_prop- If a list `l` passes the list color check, then for every color in Fin 3 there exist distinct vertices `u, v ∈ l` connected by an edge of that color.
- The core combinatorial check that all 11,628 five-element vertex subsets contain all three colors is discharged purely by kernel computation (`rfl`), without producing an explicit proof trace for each subset.
- Symmetry of the difference-based edge coloring across all 361 pairs of vertices is verified exhaustively by the `decide` tactic.
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.
def anti_ramsey_k5_lower_bound_nineteen_c (x y : ZMod 19) : Fin 3 := let d := x - y if d = 1 ∨ d = 18 ∨ d = 7 ∨ d = 12 ∨ d = 8 ∨ d = 11 then 0 else if d = 2 ∨ d = 17 ∨ d = 3 ∨ d = 16 ∨ d = 5 ∨ d = 14 then 1 else 2def anti_ramsey_k5_lower_bound_nineteen_univ : List (ZMod 19) := [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18]def anti_ramsey_k5_lower_bound_nineteen_check_list (l : List (ZMod 19)) : Bool := ([0, 1, 2] : List (Fin 3)).all fun col => l.any fun u => l.any fun v => decide (u ≠ v) && decide (anti_ramsey_k5_lower_bound_nineteen_c u v = col)def anti_ramsey_k5_lower_bound_nineteen_check_all_sublists : Bool := (List.sublistsLen 5 anti_ramsey_k5_lower_bound_nineteen_univ).all anti_ramsey_k5_lower_bound_nineteen_check_listset_option maxRecDepth 500000 inset_option maxHeartbeats 4000000 intheorem anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq : anti_ramsey_k5_lower_bound_nineteen_check_all_sublists = true := by rfltheorem anti_ramsey_k5_lower_bound_nineteen_c_symm (x y : ZMod 19) : anti_ramsey_k5_lower_bound_nineteen_c x y = anti_ramsey_k5_lower_bound_nineteen_c y x := by revert x y decidetheorem anti_ramsey_k5_lower_bound_nineteen_univ_toFinset : anti_ramsey_k5_lower_bound_nineteen_univ.toFinset = Finset.univ := by ext x simp only [List.mem_toFinset, Finset.mem_univ, iff_true] revert x decidetheorem anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card (s : Finset (ZMod 19)) : (anti_ramsey_k5_lower_bound_nineteen_univ.filter (· ∈ s)).length = s.card := by have h_nodup : anti_ramsey_k5_lower_bound_nineteen_univ.Nodup := by decide have h_toFinset : (anti_ramsey_k5_lower_bound_nineteen_univ.filter (· ∈ s)).toFinset = s := by ext x simp only [List.mem_toFinset, List.mem_filter, decide_eq_true_eq] constructor · rintro ⟨-, hx⟩; exact hx · intro hx refine ⟨?_, hx⟩ have : x ∈ anti_ramsey_k5_lower_bound_nineteen_univ.toFinset := by simp [anti_ramsey_k5_lower_bound_nineteen_univ_toFinset] exact List.mem_toFinset.mp this rw [← List.toFinset_card_of_nodup (h_nodup.filter _)] rw [h_toFinset]theorem anti_ramsey_k5_lower_bound_nineteen_check_list_prop {l : List (ZMod 19)} (h : anti_ramsey_k5_lower_bound_nineteen_check_list l = true) (col : Fin 3) : ∃ u ∈ l, ∃ v ∈ l, u ≠ v ∧ anti_ramsey_k5_lower_bound_nineteen_c u v = col := by have hcol : col ∈ ([0, 1, 2] : List (Fin 3)) := by fin_cases col <;> simp rw [anti_ramsey_k5_lower_bound_nineteen_check_list, List.all_eq_true] at h have h_any := h col hcol rw [List.any_eq_true] at h_any rcases h_any with ⟨u, hu, hu_prop⟩ rw [List.any_eq_true] at hu_prop rcases hu_prop with ⟨v, hv, hv_prop⟩ simp only [Bool.and_eq_true, decide_eq_true_iff] at hv_prop exact ⟨u, hu, v, hv, hv_prop.1, hv_prop.2⟩/-- There exists a three-edge-coloring of K_19 such that every complete subgraph on 5 vertices represents all three colors, showing xi(K_5) >= 19. -/theorem anti_ramsey_k5_lower_bound_nineteen : ∃ c : ZMod 19 → ZMod 19 → Fin 3, (∀ x y, c x y = c y x) ∧ ∀ s : Finset (ZMod 19), s.card = 5 → ∀ col : Fin 3, ∃ u ∈ s, ∃ v ∈ s, u ≠ v ∧ c u v = col := by use anti_ramsey_k5_lower_bound_nineteen_c refine ⟨anti_ramsey_k5_lower_bound_nineteen_c_symm, ?_⟩ intro s hs col let l := anti_ramsey_k5_lower_bound_nineteen_univ.filter (· ∈ s) have hl_sub : l.Sublist anti_ramsey_k5_lower_bound_nineteen_univ := List.filter_sublist have hl_len : l.length = 5 := by rw [← hs] exact anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card s have hl_mem : l ∈ List.sublistsLen 5 anti_ramsey_k5_lower_bound_nineteen_univ := by rw [List.mem_sublistsLen] exact ⟨hl_sub, hl_len⟩ have h_all : anti_ramsey_k5_lower_bound_nineteen_check_all_sublists = true := anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq have hl_check : anti_ramsey_k5_lower_bound_nineteen_check_list l = true := by rw [anti_ramsey_k5_lower_bound_nineteen_check_all_sublists, List.all_eq_true] at h_all exact h_all l hl_mem rcases anti_ramsey_k5_lower_bound_nineteen_check_list_prop hl_check col with ⟨u, hu, v, hv, huv, hcol⟩ rw [List.mem_filter] at hu hv simp only [decide_eq_true_eq] at hu hv exact ⟨u, hu.2, v, hv.2, huv, hcol⟩