AFTD Auto-Formalizing Theoretical Domains

wild_binary_leaf_signature_collision_closed

theoremverified

For a properly colored complete graph whose vertex/color labels bijectively enumerate the nonzero elements of an exponent-two commutative group and whose edge labels add, take two disjoint triples each containing a pair separated by the same e. A collision of their leaf signatures modulo {0,e} forces their six-vertex union to be closed for some color whose missing vertex lies outside that union.

Statement

theorem wild_binary_leaf_signature_collision_closed
    {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)
    (hnz : ∀ u, lab u ≠ 0) (hsurj : ∀ g : G, g ≠ 0 → ∃ u, lab u = g)
    (hcol : ∀ u v (h : u ≠ v),
      lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v)
    (e : G) (a b z d f w : Fin n)
    (hb : lab b = lab a + e) (hf : lab f = lab d + e)
    (hA : ({a,b,z} : Finset (Fin n)).card = 3)
    (hB : ({d,f,w} : Finset (Fin n)).card = 3)
    (hdis : Disjoint ({a,b,z} : Finset (Fin n)) {d,f,w})
    (hsig : lab a + lab z = lab d + lab w ∨
      lab a + lab z = lab d + lab w + e) :
    let U := ({a,b,z} : Finset (Fin n)) ∪ {d,f,w}
    U.card = 6 ∧ ∃ i : Fin n, i ∉ U ∧ 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 4

The proof, explained

The proof transports the two disjoint vertex triples into the exponent-two group G via the injective labeling function. Under the collision of their leaf signatures modulo {0, e}, the lemma wild_two_leaf_signature_translation_seal shows that the element lab z + lab w is nonzero, lies outside the 6-element label union, and acts as a translation symmetry of that label union. Surjectivity yields an external vertex i with that label, and wild_closed_cut_of_additive_translation establishes that U is closed for color i.

  1. Define the vertex sets A = {a, b, z}, B = {d, f, w}, and U = A ∪ B.

    We enable classical logic and introduce names for the two triples of vertices and their six-vertex union.

    lines 21–24

      classical
      let A : Finset (Fin n) := {a,b,z}
      let B : Finset (Fin n) := {d,f,w}
      let U := A ∪ B
  2. The label sets of A and B are {lab a, lab a + e, lab z} and {lab d, lab d + e, lab w}.

    Since lab b = lab a + e and lab f = lab d + e, simplifying the image of each triple under the labeling function replaces b and f with their shifted labels.

    lines 25–26

      have hAI : A.image lab = {lab a, lab a + e, lab z} := by simp [A, hb]
      have hBI : B.image lab = {lab d, lab d + e, lab w} := by simp [B, hf]
  3. The label sets of A and B each have cardinality 3.

    Because lab is injective, taking the image of a finite set preserves its size (card_image_of_injective). Since A and B each have size 3, their images also have size 3.

    lines 27–32

    uses card_image_of_injective

      have hcardAI : ({lab a, lab a + e, lab z} : Finset G).card = 3 := by
        rw [← hAI, card_image_of_injective _ hinj]
        exact hA
      have hcardBI : ({lab d, lab d + e, lab w} : Finset G).card = 3 := by
        rw [← hBI, card_image_of_injective _ hinj]
        exact hB
  4. The label sets of A and B are disjoint.

    To show disjointness (disjoint_left.mpr), suppose an element g belongs to both label sets. Then g = lab u for some u ∈ A and g = lab v for some v ∈ B (mem_image.mp). By injectivity of lab, u = v, which contradicts the assumed disjointness of A and B (disjoint_left.mp).

    lines 33–41

    uses disjoint_left.mpr, mem_image.mp, disjoint_left.mp

      have hdisI : Disjoint ({lab a, lab a + e, lab z} : Finset G)
          {lab d, lab d + e, lab w} := by
        rw [← hAI, ← hBI]
        apply disjoint_left.mpr
        intro g hgA hgB
        obtain ⟨u, hu, he⟩ := mem_image.mp hgA
        obtain ⟨v, hv, he'⟩ := mem_image.mp hgB
        have huv := hinj (he.trans he'.symm)
        exact disjoint_left.mp hdis hu (huv ▸ hv)
  5. The label set of U is the union of the label sets of A and B.

    The image of a union is the union of the images (image_union), so the image of U = A ∪ B is the union of the explicit label sets computed for A and B.

    lines 42–45

    uses image_union

      have hUI : U.image lab = ({lab a, lab a + e, lab z} : Finset G) ∪
          {lab d, lab d + e, lab w} := by
        change (A ∪ B).image lab = _
        rw [image_union, hAI, hBI]
  6. The zero element of G does not belong to the label set of U.

    If 0 were in the image of U (mem_image.mp), it would be the label of some vertex in U, contradicting the hypothesis that every vertex has a nonzero label.

    lines 46–51

    uses mem_image.mp

      have hzero : (0 : G) ∉ ({lab a, lab a + e, lab z} : Finset G) ∪
          {lab d, lab d + e, lab w} := by
        rw [← hUI]
        rintro hz
        obtain ⟨v, hv, he⟩ := mem_image.mp hz
        exact hnz v he
  7. The shift lab z + lab w is nonzero, lies outside the label set of U, is invariant on U under addition, and is realized as the label of a vertex i.

    The algebraic lemma wild_two_leaf_signature_translation_seal shows that under the leaf signature collision hypothesis in an exponent-two group, the shift lab z + lab w is nonzero, does not belong to lab(U), and satisfies v + (lab z + lab w) ∈ lab(U) for all v ∈ lab(U). By surjectivity of lab on nonzero elements, there exists a vertex i with lab i = lab z + lab w.

    lines 52–54

    uses wild_two_leaf_signature_translation_seal

      obtain ⟨_, hc, hcU, ht⟩ := wild_two_leaf_signature_translation_seal h2 e
        (lab a) (lab d) (lab z) (lab w) hcardAI hcardBI hdisI hzero hsig
      obtain ⟨i, hi⟩ := hsurj (lab z + lab w) hc
  8. The union U has cardinality 6.

    We supply i as the existential witness and split into subgoals. Because A and B are disjoint, the cardinality of U = A ∪ B is 3 + 3 = 6 (card_union_of_disjoint).

    lines 55–56

    uses card_union_of_disjoint

      refine ⟨?_, i, ?_, ?_⟩
      · rw [card_union_of_disjoint hdis, hA, hB]
  9. The vertex i does not belong to U.

    If i were in U, its label lab i = lab z + lab w would belong to lab(U) (mem_image.mpr), which contradicts the fact established by the seal lemma that lab z + lab w ∉ lab(U).

    lines 57–60

    uses mem_image.mpr

      · intro hiU
        apply hcU
        rw [← hUI, ← hi]
        exact mem_image.mpr ⟨i, hiU, rfl⟩
  10. The set U is closed for color i.

    By wild_closed_cut_of_additive_translation, U is closed for color i if translating any vertex label in U by lab i stays within lab(U). Since lab i = lab z + lab w, this holds directly by the translation stability property from the seal lemma (mem_image.mpr).

    lines 61–66

    uses wild_closed_cut_of_additive_translation, mem_image.mpr

      · apply wild_closed_cut_of_additive_translation h2 c lab hinj hcol i U
        intro u hu
        rw [hi, hUI]
        apply ht
        rw [← hUI]
        exact mem_image.mpr ⟨u, hu, rfl⟩
card_image_of_injective
An injective function preserves the cardinality of a finite set: |f(s)| = |s|.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities: |s ∪ t| = |s| + |t|.
disjoint_left.mp
If two sets are disjoint, any element of the first does not belong to the second.
disjoint_left.mpr
Two sets are disjoint if no element of the first belongs to the second.
image_union
The image of a union of two sets under a function is the union of their images: f(s ∪ t) = f(s) ∪ f(t).
mem_image.mp
If an element belongs to the image of a set under a function, it is the image of some element of that set.
mem_image.mpr
If an element is the image of some element of a set under a function, it belongs to the image of that set.
wild_closed_cut_of_additive_translation
For an additive edge coloring over an exponent-two group, a subset of vertices U is closed for color i if adding the label of i to any vertex label in U remains within the label set of U.
wild_two_leaf_signature_translation_seal
In an exponent-two commutative group, two disjoint 3-element sets of the forms {x, x + e, z} and {y, y + e, w} avoiding 0 whose leaf signatures collide modulo {0, e} have a 6-element union U such that z + w ≠ 0, z + w ∉ U, and U is invariant under translation by z + w.

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_binary_leaf_signature_collision_closed    {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)    (hnz : ∀ u, lab u ≠ 0) (hsurj : ∀ g : G, g ≠ 0 → ∃ u, lab u = g)    (hcol : ∀ u v (h : u ≠ v),      lab (c ⟨s(u,v), wild_kn_mem h⟩) = lab u + lab v)    (e : G) (a b z d f w : Fin n)    (hb : lab b = lab a + e) (hf : lab f = lab d + e)    (hA : ({a,b,z} : Finset (Fin n)).card = 3)    (hB : ({d,f,w} : Finset (Fin n)).card = 3)    (hdis : Disjoint ({a,b,z} : Finset (Fin n)) {d,f,w})    (hsig : lab a + lab z = lab d + lab w ∨      lab a + lab z = lab d + lab w + e) :    let U := ({a,b,z} : Finset (Fin n)) ∪ {d,f,w}    U.card = 6 ∧ ∃ i : Fin n, i ∉ U ∧ w279_closed c i U := by  classical  let A : Finset (Fin n) := {a,b,z}  let B : Finset (Fin n) := {d,f,w}  let U := A ∪ B  have hAI : A.image lab = {lab a, lab a + e, lab z} := by simp [A, hb]  have hBI : B.image lab = {lab d, lab d + e, lab w} := by simp [B, hf]  have hcardAI : ({lab a, lab a + e, lab z} : Finset G).card = 3 := by    rw [← hAI, card_image_of_injective _ hinj]    exact hA  have hcardBI : ({lab d, lab d + e, lab w} : Finset G).card = 3 := by    rw [← hBI, card_image_of_injective _ hinj]    exact hB  have hdisI : Disjoint ({lab a, lab a + e, lab z} : Finset G)      {lab d, lab d + e, lab w} := by    rw [← hAI, ← hBI]    apply disjoint_left.mpr    intro g hgA hgB    obtain ⟨u, hu, he⟩ := mem_image.mp hgA    obtain ⟨v, hv, he'⟩ := mem_image.mp hgB    have huv := hinj (he.trans he'.symm)    exact disjoint_left.mp hdis hu (huv ▸ hv)  have hUI : U.image lab = ({lab a, lab a + e, lab z} : Finset G) ∪      {lab d, lab d + e, lab w} := by    change (A ∪ B).image lab = _    rw [image_union, hAI, hBI]  have hzero : (0 : G) ∉ ({lab a, lab a + e, lab z} : Finset G) ∪      {lab d, lab d + e, lab w} := by    rw [← hUI]    rintro hz    obtain ⟨v, hv, he⟩ := mem_image.mp hz    exact hnz v he  obtain ⟨_, hc, hcU, ht⟩ := wild_two_leaf_signature_translation_seal h2 e    (lab a) (lab d) (lab z) (lab w) hcardAI hcardBI hdisI hzero hsig  obtain ⟨i, hi⟩ := hsurj (lab z + lab w) hc  refine ⟨?_, i, ?_, ?_⟩  · rw [card_union_of_disjoint hdis, hA, hB]  · intro hiU    apply hcU    rw [← hUI, ← hi]    exact mem_image.mpr ⟨i, hiU, rfl⟩  · apply wild_closed_cut_of_additive_translation h2 c lab hinj hcol i U    intro u hu    rw [hi, hUI]    apply ht    rw [← hUI]    exact mem_image.mpr ⟨u, hu, rfl⟩
See it in the graphDiscuss this resultChallenge it