AFTD Auto-Formalizing Theoretical Domains

wild_closed_cut_of_additive_translation

theoremverified

Let a proper complete-graph edge coloring have an injective labeling of its vertices and colors in an exponent-two commutative group, with each edge color label equal to the sum of its endpoint labels. If the labels of a vertex set are stable under translation by one color label, that vertex set is closed under edges of that color.

Statement

theorem wild_closed_cut_of_additive_translation
    {G : Type*} [AddCommGroup G] [DecidableEq G] {n : ℕ}
    (h2 : ∀ a : G, a + a = 0)
    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n))
    (lab : Fin n → G) (hinj : Function.Injective lab)
    (hcol : ∀ u v (h : u ≠ v),
      lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v)
    (i : Fin n) (U : Finset (Fin n))
    (htrans : ∀ u ∈ U, lab u + lab i ∈ U.image lab) :
    w279_closed c i U
Source
OP-306 / IN-338 general-route helpers for the strict prescribed-coloring conjecture in arXiv:2610.22142, Sections3.3.2 and6. Structural analysis of binary factorizations and exact finite averaging in experiments8399,8400,8402,8414. These are conditional certificate or method-diagnostic lemmas, not a new wild-number bound or research advance.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 1

The proof, explained

To prove that U is closed under edges of color i, consider any vertex u ∈ U connected to a vertex v by an edge of color i. In an exponent-two group, the endpoint-sum coloring condition lab(u) + lab(v) = lab(i) can be rearranged to lab(v) = lab(u) + lab(i). Since U is stable under translation by lab(i), this sum is the label of some vertex w ∈ U, and injectivity of the labeling forces v = w ∈ U.

  1. To show that U is closed under edges of color i, let u ∈ U and let v be an adjacent vertex such that the edge between u and v has color i; it suffices to show that v ∈ U.

    Unfolding the definition of a closed vertex set (w279_closed c i U), we assume u ∈ U, a vertex v with u ≠ v, and that the edge {u, v} has color i. The goal is to prove that v ∈ U.

    line 14

      intro u hu v huv hc
  2. The label of vertex v equals lab(u) + lab(i).

    Since every element in G has order two (h2: a + a = 0), we can express lab(v) as 0 + lab(v) = (lab(u) + lab(u)) + lab(v) = lab(u) + (lab(u) + lab(v)). By the coloring assumption hcol, the sum lab(u) + lab(v) is the label of the color of edge {u, v}, which equals lab(i). Hence lab(v) = lab(u) + lab(i).

    lines 15–19

    uses zero_add

      have hv : lab v = lab u + lab i := by
        calc
          _ = (lab u + lab u) + lab v := by rw [h2, zero_add]
          _ = lab u + (lab u + lab v) := by abel
          _ = lab u + lab i := by rw [← hcol u v huv, hc]
  3. The vertex v belongs to U.

    By the translation stability hypothesis htrans, lab(u) + lab(i) belongs to the image of U under lab. Unpacking this finset image membership gives a vertex w ∈ U with lab(w) = lab(u) + lab(i). Since lab(w) = lab(v) and the labeling is injective (hinj), we have w = v, which implies v ∈ U.

    lines 20–22

    uses mem_image.mp

      obtain ⟨w, hw, hweq⟩ := mem_image.mp (htrans u hu)
      have : w = v := hinj (hweq.trans hv.symm)
      simpa only [this] using hw
zero_add
in any additive structure with zero, adding zero on the left leaves the element unchanged: 0 + a = a
mem_image.mp
an element b is in the image of a finite set s under f if and only if b = f(a) for some a ∈ s

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

open Finsetset_option maxHeartbeats 2500000theorem wild_closed_cut_of_additive_translation    {G : Type*} [AddCommGroup G] [DecidableEq G] {n : ℕ}    (h2 : ∀ a : G, a + a = 0)    (c : (⊤ : SimpleGraph (Fin n)).lineGraph.Coloring (Fin n))    (lab : Fin n → G) (hinj : Function.Injective lab)    (hcol : ∀ u v (h : u ≠ v),      lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v)    (i : Fin n) (U : Finset (Fin n))    (htrans : ∀ u ∈ U, lab u + lab i ∈ U.image lab) :    w279_closed c i U := by  intro u hu v huv hc  have hv : lab v = lab u + lab i := by    calc      _ = (lab u + lab u) + lab v := by rw [h2, zero_add]      _ = lab u + (lab u + lab v) := by abel      _ = lab u + lab i := by rw [← hcol u v huv, hc]  obtain ⟨w, hw, hweq⟩ := mem_image.mp (htrans u hu)  have : w = v := hinj (hweq.trans hv.symm)  simpa only [this] using hw
See it in the graphDiscuss this resultChallenge it