AFTD Auto-Formalizing Theoretical Domains

wild_leaf_translation_seal_iff_signature_collision

theoremverified

For two disjoint nonzero triples {x,x+e,z} and {y,y+e,w} in a commutative exponent-two group, with z+e outside their union, some nonzero translation preserves that union if and only if their leaf signatures x+z and y+w are equal modulo {0,e}.

Statement

theorem wild_leaf_translation_seal_iff_signature_collision
    {G : Type*} [AddCommGroup G] [DecidableEq G]
    (h2 : ∀ v : G, v + v = 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,y,y+e,w} : Finset G))
    (hzext : z + e ∉ ({x,x+e,z,y,y+e,w} : Finset G)) :
    (∃ c : G, c ≠ 0 ∧ ∀ v ∈ ({x,x+e,z,y,y+e,w} : Finset G),
      v + c ∈ ({x,x+e,z,y,y+e,w} : Finset G)) ↔
      x + z = y + w ∨ x + z = y + w + e
Source
OP-306 / IN-338 general construction helpers related to arXiv:2610.22142, Sections3.3.2 and6. Binary leaf-translation classification and standard maximal rainbow-matching counting, used to repair the diagnosed sampling law (experiments8414 and8442). No new exact wild-number case, numerical bound or research advance is claimed.
Verified
29 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2

The proof, explained

To prove that the union of two disjoint triples in an exponent-two group is preserved by a nonzero translation if and only if their leaf signatures match modulo {0, e}, the argument splits into two directions. In the forward direction, any preserving nonzero translation c must equal z + w by uniqueness; analyzing the six possible values of x + c rules out four cases and leaves x + z = y + w or x + z = y + w + e. In the backward direction, the existence lemma wild_two_leaf_signature_translation_seal ensures that c = z + w is a valid preserving translation whenever the leaf signatures match modulo e.

  1. In an exponent-two group, if a + c = b then b + c = a

    Translating both sides of b = a + c by c gives b + c = (a + c) + c = a + (c + c) = a + 0 = a, since every element is its own inverse.

    lines 6–8

    uses congrArg, add_assoc, add_zero

      calc
        _ = (a + c) + c := congrArg (fun v => v + c) h.symm
        _ = a := by rw [add_assoc, h2, add_zero]
  2. In an exponent-two group, translating a by e then c and then e gives a + c

    Rearranging the sum ((a + e) + c) + e using commutativity and associativity yields (a + c) + (e + e) = (a + c) + 0 = a + c.

    lines 12–14

    uses add_zero

      calc
        _ = (a + c) + (e + e) := by abel
        _ = a + c := by rw [h2, add_zero]
  3. The union of {x, x+e, z} and {y, y+e, w} equals the 6-element set {x, x+e, z, y, y+e, w}

    We check extensional equality by verifying that any element v belongs to the union of the two triples if and only if it belongs to the 6-element set.

    lines 27–28

      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
  4. Split the equivalence into forward and backward implications

    We split the if-and-only-if statement into two independent goals.

    line 29

      constructor
  5. Any nonzero translation preserving the union must equal z + w

    Assuming c is a nonzero translation preserving the union, the uniqueness lemma wild_leaf_translation_color_unique establishes that c = z + w, using the hypothesis that z + e lies outside the union.

    lines 30–31

    uses wild_leaf_translation_color_unique

      · rintro ⟨c, hc, ht⟩
        have hcw := wild_leaf_translation_color_unique h2 e x y z w c hzext hc ht
  6. x cannot equal z

    If x = z, the triple {x, x+e, z} would be a subset of {x, x+e} and thus have cardinality at most 2, contradicting the hypothesis that its cardinality is 3.

    lines 32–40

    uses card_le_card, card_le_two

        have hxz : x ≠ z := by
          intro h
          subst z
          have hsub : ({x,x+e,x} : Finset G) ⊆ {x,x+e} := by
            intro v hv
            simp only [mem_insert, mem_singleton] at hv ⊢
            tauto
          have hh := (card_le_card hsub).trans (card_le_two (a := x) (b := x+e))
          omega
  7. x cannot equal w

    Since x belongs to the first triple and w belongs to the second triple, x = w would contradict the assumption that the two triples are disjoint.

    lines 41–44

    uses disjoint_left

        have hxw : x ≠ w := by
          intro h
          exact disjoint_left.mp hdis (by simp : x ∈ ({x,x+e,z} : Finset G))
            (by simp [h] : x ∈ ({y,y+e,w} : Finset G))
  8. Translation by c swaps z and w: z + c = w and w + c = z

    Substituting c = z + w gives z + c = (z + z) + w = w. Applying lemma in338_reverse_translation_sig in an exponent-two group then yields w + c = z.

    lines 45–46

    uses in338_reverse_translation_sig

        have hzw : z + c = w := by rw [hcw, ← add_assoc, h2, zero_add]
        have hwz := in338_reverse_translation_sig h2 z w c hzw
  9. (x + c) + w equals x + z

    Since c = z + w, we have (x + c) + w = (x + z + w) + w = x + z + (w + w) = x + z.

    lines 47–50

    uses add_assoc, add_zero

        have hcancel : (x+c)+w = x+z := by
          calc
            _ = ((x+z)+w)+w := by rw [hcw]; abel
            _ = x+z := by rw [add_assoc, h2, add_zero]
  10. The translate x + c must be one of the six elements in the union

    Since x belongs to the union and translation by c preserves the union, x + c must equal x, x+e, z, y, y+e, or w.

    lines 51–53

        have hx := ht x (by simp)
        simp only [mem_insert, mem_singleton] at hx
        rcases hx with h | h | h | h | h | h
  11. x + c cannot equal x, x + e, or z

    If x + c = x, cancelling x gives c = 0, contradiction. If x + c = x + e, cancelling x gives c = e, which would mean z + e = z + c is in the union, contradicting hzext. If x + c = z, reversing yields z + c = x; but z + c = w, so x = w, contradicting disjointness.

    lines 54–58

    uses add_left_cancel, in338_reverse_translation_sig

        · exact (hc (add_left_cancel (h.trans (add_zero x).symm))).elim
        · have hce : c = e := add_left_cancel h
          exact (hzext (hce ▸ ht z (by simp))).elim
        · have hb := in338_reverse_translation_sig h2 x z c h
          exact (hxw (hb.symm.trans hzw)).elim
  12. If x + c = y, then x + z = y + w

    Adding w to both sides of x + c = y gives (x + c) + w = y + w. Since (x + c) + w = x + z, this directly implies x + z = y + w.

    lines 59–60

    uses congrArg

        · left
          exact hcancel.symm.trans (congrArg (fun v => v+w) h)
  13. If x + c = y + e, then x + z = y + w + e

    Adding w to both sides of x + c = y + e gives (x + c) + w = (y + e) + w = y + w + e. Since (x + c) + w = x + z, this yields x + z = y + w + e.

    lines 61–65

    uses congrArg

        · right
          calc
            _ = (x+c)+w := hcancel.symm
            _ = (y+e)+w := congrArg (fun v => v+w) h
            _ = y+w+e := by abel
  14. x + c cannot equal w

    If x + c = w, reversing gives w + c = x. But w + c = z, so x = z, which contradicts the cardinality of the first triple. This completes the forward direction.

    lines 66–67

    uses in338_reverse_translation_sig

        · have hb := in338_reverse_translation_sig h2 x w c h
          exact (hxz (hb.symm.trans hwz)).elim
  15. If the leaf signatures match modulo e, there exists a nonzero translation preserving the union

    Lemma wild_two_leaf_signature_translation_seal directly supplies that c = z + w is nonzero and preserves the union of the two triples under the signature collision hypothesis.

    lines 68–71

    uses wild_two_leaf_signature_translation_seal

      · intro hsig
        obtain ⟨_, hc, _, ht⟩ := wild_two_leaf_signature_translation_seal h2 e x y z w
          hA hB hdis (by simpa only [hU] using hzero) hsig
        exact ⟨z+w, hc, by simpa only [hU] using ht⟩
add_assoc
Addition in an additive semigroup is associative: (a + b) + c = a + (b + c)
add_zero
Adding zero to an element leaves it unchanged: a + 0 = a
add_left_cancel
In an additive group, if a + b = a + c then b = c
card_le_card
A subset of a finite set has cardinality at most the cardinality of the superset
card_le_two
A set with at most two elements has cardinality at most 2
congrArg
Applying a function to equal arguments yields equal values
disjoint_left
Two sets are disjoint if and only if no element of the first belongs to the second
in338_reverse_translation_sig
In an exponent-two group, a + c = b implies b + c = a
wild_leaf_translation_color_unique
In an exponent-two group, any nonzero translation preserving the union of two disjoint triples {x, x+e, z} and {y, y+e, w} (with z+e outside) must be z + w
wild_two_leaf_signature_translation_seal
If the leaf signatures of two disjoint triples match modulo e, then translating by z + w preserves their union

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 2500000private lemma in338_reverse_translation_sig {G : Type*} [AddCommGroup G]    (h2 : ∀ v : G, v + v = 0) (a b c : G) (h : a + c = b) : b + c = a := by  calc    _ = (a + c) + c := congrArg (fun v => v + c) h.symm    _ = a := by rw [add_assoc, h2, add_zero]private lemma in338_slide_translation_sig {G : Type*} [AddCommGroup G]    (h2 : ∀ v : G, v + v = 0) (a e c : G) : ((a + e) + c) + e = a + c := by  calc    _ = (a + c) + (e + e) := by abel    _ = a + c := by rw [h2, add_zero]theorem wild_leaf_translation_seal_iff_signature_collision    {G : Type*} [AddCommGroup G] [DecidableEq G]    (h2 : ∀ v : G, v + v = 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,y,y+e,w} : Finset G))    (hzext : z + e ∉ ({x,x+e,z,y,y+e,w} : Finset G)) :    (∃ c : G, c ≠ 0 ∧ ∀ v ∈ ({x,x+e,z,y,y+e,w} : Finset G),      v + c ∈ ({x,x+e,z,y,y+e,w} : Finset G)) ↔      x + z = y + w ∨ x + z = y + w + e := by  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  constructor  · rintro ⟨c, hc, ht⟩    have hcw := wild_leaf_translation_color_unique h2 e x y z w c hzext hc ht    have hxz : x ≠ z := by      intro h      subst z      have hsub : ({x,x+e,x} : Finset G) ⊆ {x,x+e} := by        intro v hv        simp only [mem_insert, mem_singleton] at hv ⊢        tauto      have hh := (card_le_card hsub).trans (card_le_two (a := x) (b := x+e))      omega    have hxw : x ≠ w := by      intro h      exact disjoint_left.mp hdis (by simp : x ∈ ({x,x+e,z} : Finset G))        (by simp [h] : x ∈ ({y,y+e,w} : Finset G))    have hzw : z + c = w := by rw [hcw, ← add_assoc, h2, zero_add]    have hwz := in338_reverse_translation_sig h2 z w c hzw    have hcancel : (x+c)+w = x+z := by      calc        _ = ((x+z)+w)+w := by rw [hcw]; abel        _ = x+z := by rw [add_assoc, h2, add_zero]    have hx := ht x (by simp)    simp only [mem_insert, mem_singleton] at hx    rcases hx with h | h | h | h | h | h    · exact (hc (add_left_cancel (h.trans (add_zero x).symm))).elim    · have hce : c = e := add_left_cancel h      exact (hzext (hce ▸ ht z (by simp))).elim    · have hb := in338_reverse_translation_sig h2 x z c h      exact (hxw (hb.symm.trans hzw)).elim    · left      exact hcancel.symm.trans (congrArg (fun v => v+w) h)    · right      calc        _ = (x+c)+w := hcancel.symm        _ = (y+e)+w := congrArg (fun v => v+w) h        _ = y+w+e := by abel    · have hb := in338_reverse_translation_sig h2 x w c h      exact (hxz (hb.symm.trans hwz)).elim  · intro hsig    obtain ⟨_, hc, _, ht⟩ := wild_two_leaf_signature_translation_seal h2 e x y z w      hA hB hdis (by simpa only [hU] using hzero) hsig    exact ⟨z+w, hc, by simpa only [hU] using ht⟩
See it in the graphDiscuss this resultChallenge it