AFTD Auto-Formalizing Theoretical Domains

wild_two_leaf_signature_translation_seal

theoremverified

In a commutative group of exponent two, take two disjoint three-element sets {x,x+e,z} and {y,y+e,w} containing no zero. If x+z equals y+w or y+w+e, their six-element union is closed under translation by z+w; that translator is nonzero and lies outside the union.

Statement

theorem wild_two_leaf_signature_translation_seal
    {G : Type*} [AddCommGroup G] [DecidableEq G]
    (h2 : ∀ a : G, a + a = 0) (e x y z w : G)
    (hA : ({x, x + e, z} : Finset G).card = 3)
    (hB : ({y, y + e, w} : Finset G).card = 3)
    (hdis : Disjoint ({x, x + e, z} : Finset G) {y, y + e, w})
    (hzero : (0 : G) ∉ ({x, x + e, z} : Finset G) ∪ {y, y + e, w})
    (hsig : x + z = y + w ∨ x + z = y + w + e) :
    let U := ({x, x + e, z} : Finset G) ∪ {y, y + e, w}
    U.card = 6 ∧ z + w ≠ 0 ∧ z + w ∉ U ∧
      ∀ v ∈ U, v + (z + w) ∈ 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
Used by 2

The proof, explained

The proof establishes that the union U of the two disjoint three-element sets is closed under translation by z + w, that |U| = 6, and that z + w is nonzero and outside U. The signature condition ensures that translation by z + w swaps the elements of U in three pairs, making U translation-invariant. The element z + w is nonzero because z and w belong to disjoint sets (hence z ≠ w), and z + w cannot lie in U because translating it by itself would place (z + w) + (z + w) = 0 in U, contradicting the assumption that U contains no zero.

  1. In an additive commutative group of exponent two, adding any element twice cancels: (a + b) + b = a.

    By associativity, (a + b) + b = a + (b + b). Since every element has order two, b + b = 0, leaving a + 0 = a.

    lines 4–6

    uses add_assoc, add_zero

    private lemma in338_cancel_pair {G : Type*} [AddCommGroup G]
        (h2 : ∀ a : G, a + a = 0) (a b : G) : (a + b) + b = a := by
      rw [add_assoc, h2, add_zero]
  2. If c = a + b, then a + c = b.

    Substituting c = a + b gives a + (a + b) = (a + a) + b by associativity; because 2a = 0, this simplifies to 0 + b = b.

    lines 8–10

    uses add_assoc, zero_add

    private lemma in338_translate_pair {G : Type*} [AddCommGroup G]
        (h2 : ∀ a : G, a + a = 0) (a b c : G) (h : c = a + b) : a + c = b := by
      rw [h, ← add_assoc, h2, zero_add]
  3. Translation by z + w swaps z and w: z + (z + w) = w and w + (z + w) = z.

    Applying the previous translation identity with c = z + w gives z + (z + w) = w. Substituting this into w + (z + w) yields (z + (z + w)) + (z + w), which simplifies to z by the cancellation identity.

    lines 12–21

    uses congrArg

    private lemma in338_leaf_translation {G : Type*} [AddCommGroup G] [DecidableEq G]
        (h2 : ∀ a : G, a + a = 0) (e x y z w : G)
        (hsig : x + z = y + w ∨ x + z = y + w + e) :
        ∀ v ∈ ({x, x + e, z, y, y + e, w} : Finset G),
          v + (z + w) ∈ ({x, x + e, z, y, y + e, w} : Finset G) := by
      have hzw := in338_translate_pair h2 z w (z + w) rfl
      have hwz : w + (z + w) = z := by
        calc
          _ = (z + (z + w)) + (z + w) := congrArg (fun v => v + (z + w)) hzw.symm
          _ = z := in338_cancel_pair h2 _ _
  4. Translating x by z + w yields either y or y + e.

    We reassociate x + (z + w) as (x + z) + w. Under the first signature case x + z = y + w, this is (y + w) + w = y by cancellation. Under the second case x + z = y + w + e, this is (y + e + w) + w = y + e.

    lines 22–34

      have hxc : x + (z + w) = y ∨ x + (z + w) = y + e := by
        rcases hsig with h | h
        · left
          calc
            _ = (x + z) + w := by abel
            _ = (y + w) + w := by rw [h]
            _ = y := in338_cancel_pair h2 _ _
        · right
          calc
            _ = (x + z) + w := by abel
            _ = (y + w + e) + w := by rw [h]
            _ = (y + e + w) + w := by abel
            _ = y + e := in338_cancel_pair h2 _ _
  5. When x + (z + w) = y, the set {x, x+e, z, y, y+e, w} is closed under translation by z + w.

    Since translation by z + w is an involution, x + (z + w) = y implies y + (z + w) = x. Shifting by e gives (x + e) + (z + w) = y + e and (y + e) + (z + w) = x + e. Together with swapping z and w, translation by z + w partitions the six elements into three pairs exchanged with each other, so every element remains in the set.

    lines 35–46

      rcases hxc with hxy | hxye
      · have hyx : y + (z + w) = x := by rw [← hxy, in338_cancel_pair h2]
        have hxeye : (x + e) + (z + w) = y + e := by
          calc
            _ = (x + (z + w)) + e := by abel
            _ = _ := by rw [hxy]
        have hyexe : (y + e) + (z + w) = x + e := by
          rw [← hxeye, in338_cancel_pair h2]
        intro v hv
        simp only [mem_insert, mem_singleton] at hv ⊢
        rcases hv with rfl | rfl | rfl | rfl | rfl | rfl <;>
          simp only [hxy, hyx, hxeye, hyexe, hzw, hwz] <;> tauto
  6. When x + (z + w) = y + e, the set {x, x+e, z, y, y+e, w} is also closed under translation by z + w.

    In this case, x + (z + w) = y + e implies (y + e) + (z + w) = x. Adding e gives (x + e) + (z + w) = (y + e) + e = y, which implies y + (z + w) = x + e. Translation by z + w exchanges the pairs (x, y+e), (x+e, y), and (z, w), so all elements again map into the set.

    lines 47–57

      · have hyex : (y + e) + (z + w) = x := by rw [← hxye, in338_cancel_pair h2]
        have hxey : (x + e) + (z + w) = y := by
          calc
            _ = (x + (z + w)) + e := by abel
            _ = (y + e) + e := by rw [hxye]
            _ = y := in338_cancel_pair h2 _ _
        have hyxe : y + (z + w) = x + e := by rw [← hxey, in338_cancel_pair h2]
        intro v hv
        simp only [mem_insert, mem_singleton] at hv ⊢
        rcases hv with rfl | rfl | rfl | rfl | rfl | rfl <;>
          simp only [hxye, hyex, hxey, hyxe, hzw, hwz] <;> tauto
  7. The union U = {x, x+e, z} ∪ {y, y+e, w} is closed under translation by z + w.

    We identify U with the six-element set {x, x+e, z, y, y+e, w} and apply the lemma establishing that translation by z + w maps every element of this set into itself.

    lines 70–74

      dsimp only
      have hU : ({x, x + e, z} : Finset G) ∪ {y, y + e, w} =
          {x, x + e, z, y, y + e, w} := by ext v; simp; tauto
      have ht := in338_leaf_translation h2 e x y z w hsig
      rw [← hU] at ht
  8. The elements z and w are distinct.

    If z = w, then z would belong to both {x, x+e, z} and {y, y+e, w}, contradicting the assumption that these two sets are disjoint.

    lines 75–78

    uses Finset.disjoint_left.mp

      have hne : z ≠ w := by
        intro h
        exact (Finset.disjoint_left.mp hdis) (by simp : z ∈ ({x, x + e, z} : Finset G))
          (by simp [h] : z ∈ ({y, y + e, w} : Finset G))
  9. The translation element z + w is nonzero.

    If z + w = 0, then z + w = w + w because 2w = 0. Right cancellation implies z = w, which contradicts z ≠ w.

    lines 79–81

    uses add_right_cancel

      have hc : z + w ≠ 0 := by
        intro h
        exact hne (add_right_cancel (h.trans (h2 w).symm))
  10. The union U has cardinality 6.

    Since U is the union of two disjoint sets of cardinality 3, its cardinality is 3 + 3 = 6.

    lines 82–83

    uses card_union_of_disjoint

      refine ⟨?_, hc, ?_, ht⟩
      · rw [card_union_of_disjoint hdis, hA, hB]
  11. The translation element z + w does not belong to U.

    If z + w were in U, then by translation invariance (z + w) + (z + w) would belong to U. But (z + w) + (z + w) = 0 by exponent two, which contradicts the hypothesis that 0 ∉ U.

    lines 84–87

      · intro h
        have hz := ht (z + w) h
        rw [h2] at hz
        exact hzero hz
add_assoc
Addition in a semigroup or group is associative: (a + b) + c = a + (b + c).
add_zero
Adding zero on the right leaves an element unchanged: a + 0 = a.
zero_add
Adding zero on the left leaves an element unchanged: 0 + a = a.
congrArg
Equal arguments to a function give equal results: if a = b, then f a = f b.
Finset.disjoint_left.mp
If two finite sets are disjoint, any element in the first set does not belong to the second set.
add_right_cancel
In an additive group, right addition is cancellable: if a + b = c + b, then a = c.
card_union_of_disjoint
The cardinality of the union of two disjoint finite sets is the sum of their cardinalities: |s ∪ t| = |s| + |t|.

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 2000000private lemma in338_cancel_pair {G : Type*} [AddCommGroup G]    (h2 : ∀ a : G, a + a = 0) (a b : G) : (a + b) + b = a := by  rw [add_assoc, h2, add_zero]private lemma in338_translate_pair {G : Type*} [AddCommGroup G]    (h2 : ∀ a : G, a + a = 0) (a b c : G) (h : c = a + b) : a + c = b := by  rw [h, ← add_assoc, h2, zero_add]private lemma in338_leaf_translation {G : Type*} [AddCommGroup G] [DecidableEq G]    (h2 : ∀ a : G, a + a = 0) (e x y z w : G)    (hsig : x + z = y + w ∨ x + z = y + w + e) :    ∀ v ∈ ({x, x + e, z, y, y + e, w} : Finset G),      v + (z + w) ∈ ({x, x + e, z, y, y + e, w} : Finset G) := by  have hzw := in338_translate_pair h2 z w (z + w) rfl  have hwz : w + (z + w) = z := by    calc      _ = (z + (z + w)) + (z + w) := congrArg (fun v => v + (z + w)) hzw.symm      _ = z := in338_cancel_pair h2 _ _  have hxc : x + (z + w) = y ∨ x + (z + w) = y + e := by    rcases hsig with h | h    · left      calc        _ = (x + z) + w := by abel        _ = (y + w) + w := by rw [h]        _ = y := in338_cancel_pair h2 _ _    · right      calc        _ = (x + z) + w := by abel        _ = (y + w + e) + w := by rw [h]        _ = (y + e + w) + w := by abel        _ = y + e := in338_cancel_pair h2 _ _  rcases hxc with hxy | hxye  · have hyx : y + (z + w) = x := by rw [← hxy, in338_cancel_pair h2]    have hxeye : (x + e) + (z + w) = y + e := by      calc        _ = (x + (z + w)) + e := by abel        _ = _ := by rw [hxy]    have hyexe : (y + e) + (z + w) = x + e := by      rw [← hxeye, in338_cancel_pair h2]    intro v hv    simp only [mem_insert, mem_singleton] at hv ⊢    rcases hv with rfl | rfl | rfl | rfl | rfl | rfl <;>      simp only [hxy, hyx, hxeye, hyexe, hzw, hwz] <;> tauto  · have hyex : (y + e) + (z + w) = x := by rw [← hxye, in338_cancel_pair h2]    have hxey : (x + e) + (z + w) = y := by      calc        _ = (x + (z + w)) + e := by abel        _ = (y + e) + e := by rw [hxye]        _ = y := in338_cancel_pair h2 _ _    have hyxe : y + (z + w) = x + e := by rw [← hxey, in338_cancel_pair h2]    intro v hv    simp only [mem_insert, mem_singleton] at hv ⊢    rcases hv with rfl | rfl | rfl | rfl | rfl | rfl <;>      simp only [hxye, hyex, hxey, hyxe, hzw, hwz] <;> tautotheorem wild_two_leaf_signature_translation_seal    {G : Type*} [AddCommGroup G] [DecidableEq G]    (h2 : ∀ a : G, a + a = 0) (e x y z w : G)    (hA : ({x, x + e, z} : Finset G).card = 3)    (hB : ({y, y + e, w} : Finset G).card = 3)    (hdis : Disjoint ({x, x + e, z} : Finset G) {y, y + e, w})    (hzero : (0 : G) ∉ ({x, x + e, z} : Finset G) ∪ {y, y + e, w})    (hsig : x + z = y + w ∨ x + z = y + w + e) :    let U := ({x, x + e, z} : Finset G) ∪ {y, y + e, w}    U.card = 6 ∧ z + w ≠ 0 ∧ z + w ∉ U ∧      ∀ v ∈ U, v + (z + w) ∈ U := by  dsimp only  have hU : ({x, x + e, z} : Finset G) ∪ {y, y + e, w} =      {x, x + e, z, y, y + e, w} := by ext v; simp; tauto  have ht := in338_leaf_translation h2 e x y z w hsig  rw [← hU] at ht  have hne : z ≠ w := by    intro h    exact (Finset.disjoint_left.mp hdis) (by simp : z ∈ ({x, x + e, z} : Finset G))      (by simp [h] : z ∈ ({y, y + e, w} : Finset G))  have hc : z + w ≠ 0 := by    intro h    exact hne (add_right_cancel (h.trans (h2 w).symm))  refine ⟨?_, hc, ?_, ht⟩  · rw [card_union_of_disjoint hdis, hA, hB]  · intro h    have hz := ht (z + w) h    rw [h2] at hz    exact hzero hz
See it in the graphDiscuss this resultChallenge it