AFTD Auto-Formalizing Theoretical Domains

anti_ramsey_k5_lower_bound_nineteen

theoremverifiedformalization

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.

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

    line 24

      rfl
  2. The 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.

    lines 28–29

      revert x y
      decide
  3. Converting 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.

    lines 33–36

    uses List.mem_toFinset, Finset.mem_univ, iff_true

      ext x
      simp only [List.mem_toFinset, Finset.mem_univ, iff_true]
      revert x
      decide
  4. 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`.

    lines 40–52

    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_nodup

      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]
  5. 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`.

    lines 57–66

    uses anti_ramsey_k5_lower_bound_nineteen_check_list, List.all_eq_true, List.any_eq_true, Bool.and_eq_true, decide_eq_true_iff

      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⟩
  6. 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.

    lines 74–75

    uses anti_ramsey_k5_lower_bound_nineteen_c_symm

      use anti_ramsey_k5_lower_bound_nineteen_c
      refine ⟨anti_ramsey_k5_lower_bound_nineteen_c_symm, ?_⟩
  7. 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`.

    lines 76–84

    uses List.filter_sublist, anti_ramsey_k5_lower_bound_nineteen_filter_length_eq_card, List.mem_sublistsLen

      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⟩
  8. 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`.

    lines 85–89

    uses anti_ramsey_k5_lower_bound_nineteen_check_all_sublists_eq, anti_ramsey_k5_lower_bound_nineteen_check_all_sublists, List.all_eq_true

      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
  9. 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`.

    lines 90–93

    uses anti_ramsey_k5_lower_bound_nineteen_check_list_prop, List.mem_filter, decide_eq_true_eq

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

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

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