AFTD Auto-Formalizing Theoretical Domains

wild_leaf_translation_color_unique

theoremverified

In a commutative exponent-two group, let U={x,x+e,z,y,y+e,w}, and assume z+e lies outside U. Any nonzero translation preserving U must have translator exactly z+w.

Statement

theorem wild_leaf_translation_color_unique
    {G : Type*} [AddCommGroup G] [DecidableEq G]
    (h2 : ∀ v : G, v + v = 0) (e x y z w c : G)
    (hzext : z + e ∉ ({x,x+e,z,y,y+e,w} : Finset G)) (hc : c ≠ 0)
    (ht : ∀ v ∈ ({x,x+e,z,y,y+e,w} : Finset G),
      v + c ∈ ({x,x+e,z,y,y+e,w} : Finset G)) : c = z + w
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
Used by 1

The proof, explained

To show that the translator $c$ must be $z + w$, we consider the image $z + c \in U = \{x, x+e, z, y, y+e, w\}$ under the translation preserving $U$. Using the self-inverse property of translation in exponent-two groups, we prove that if $t, t+e \in U$, then $z+c$ cannot equal $t$ or $t+e$, since otherwise the translation would map one of these elements to $z+e \notin U$. Applying this to the pairs $(x, x+e)$ and $(y, y+e)$ rules out four elements, while $z+c = z$ is ruled out because $c \neq 0$. This leaves only $z+c = w$, from which adding $z$ to both sides uniquely determines $c = z+w$.

  1. In a commutative exponent-two group, translation by $c$ is self-inverse: if $a + c = b$, then $b + c = a$.

    Applying the function $v \mapsto v + c$ to both sides of $b = a + c$ (via `congrArg`) yields $b + c = (a + c) + c$. By associativity (`add_assoc`), this reassociates to $a + (c + c)$, which reduces to $a + 0 = a$ by the exponent-two hypothesis $c + c = 0$ (`h2`) and `add_zero`.

    lines 4–9

    uses congrArg, add_assoc, add_zero

    private lemma in338_reverse_translation {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]
    
  2. In a commutative exponent-two group, $((a + e) + c) + e = a + c$.

    Using abelian group arithmetic (`abel`), $((a + e) + c) + e$ rearranges to $(a + c) + (e + e)$. Since $e + e = 0$ by the exponent-two hypothesis (`h2`), this simplifies to $a + c$ by `add_zero`.

    lines 10–15

    uses add_zero

    private lemma in338_slide_translation {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]
    
  3. Denoting $U = \{x, x+e, z, y, y+e, w\}$, for any $t \in U$ with $t + e \in U$, the translated element $z + c$ cannot equal $t$ or $t + e$.

    Suppose for contradiction that $z + c = t$. By `in338_reverse_translation`, this gives $t + c = z$. Then $(t + e) + c = (t + c) + e = z + e$ by abelian group reordering and substitution. Since $t + e \in U$, translation invariance implies $(t + e) + c \in U$, which means $z + e \in U$, contradicting the hypothesis $z + e \notin U$. Similarly, if $z + c = t + e$, `in338_reverse_translation` yields $(t + e) + c = z$. By `in338_slide_translation` and `congrArg`, $t + c = ((t + e) + c) + e = z + e$. Since $t \in U$, translation invariance implies $t + c \in U$, so $z + e \in U$, again contradicting $z + e \notin U$.

    lines 22–39

    uses in338_reverse_translation, in338_slide_translation, congrArg

      let U : Finset G := {x,x+e,z,y,y+e,w}
      have hp : ∀ t : G, t ∈ U → t + e ∈ U → z + c ≠ t ∧ z + c ≠ t + e := by
        intro t htU hteU
        constructor
        · intro h
          have hb := in338_reverse_translation h2 z t c h
          have heq : (t + e) + c = z + e := by
            calc
              _ = (t + c) + e := by abel
              _ = z + e := by rw [hb]
          exact hzext (heq ▸ ht (t+e) hteU)
        · intro h
          have hb := in338_reverse_translation h2 z (t+e) c h
          have heq : t + c = z + e := by
            calc
              _ = ((t+e)+c)+e := (in338_slide_translation h2 t e c).symm
              _ = z + e := congrArg (fun v => v+e) hb
          exact hzext (heq ▸ ht t htU)
  4. $z + c$ is not equal to $x$, $x + e$, $y$, or $y + e$. automation

    Both $x$ and $x + e$ belong to $U$, and likewise both $y$ and $y + e$ belong to $U$ (discharged by `simp`). Applying the previous result to $t = x$ and $t = y$ immediately establishes that $z + c \neq x$, $z + c \neq x + e$, $z + c \neq y$, and $z + c \neq y + e$.

    lines 40–41

      have hpx := hp x (by simp [U]) (by simp [U])
      have hpy := hp y (by simp [U]) (by simp [U])
  5. The element $z + c$ must equal one of $x$, $x + e$, $z$, $y$, $y + e$, or $w$.

    Since $z \in U$, translation invariance by $c$ guarantees that $z + c \in U$. Unfolding membership in the finite set $U = \{x, x+e, z, y, y+e, w\}$ using `mem_insert` and `mem_singleton` produces a six-way disjunction of possible values for $z + c$.

    lines 42–43

    uses mem_insert, mem_singleton

      have hz := ht z (by simp)
      simp only [mem_insert, mem_singleton] at hz
  6. The first five cases ($z + c = x$, $x + e$, $z$, $y$, $y + e$) are impossible.

    We eliminate the cases one by one: $z + c = x$ and $z + c = x + e$ contradict the inequalities from the $t = x$ specialization; $z + c = y$ and $z + c = y + e$ contradict those from $t = y$. If $z + c = z$, then since $z = z + 0$ by `add_zero`, left cancellation (`add_left_cancel`) implies $c = 0$, contradicting the assumption $c \neq 0$.

    lines 44–49

    uses add_left_cancel, add_zero

      rcases hz with h | h | h | h | h | h
      · exact (hpx.1 h).elim
      · exact (hpx.2 h).elim
      · exact (hc (add_left_cancel (h.trans (add_zero z).symm))).elim
      · exact (hpy.1 h).elim
      · exact (hpy.2 h).elim
  7. In the remaining case $z + c = w$, the translator is uniquely determined as $c = z + w$.

    From $z + c = w$, we add $z$ to both sides via `congrArg` to get $z + (z + c) = z + w$. Reassociating the left-hand side with `add_assoc` gives $(z + z) + c$, which by the exponent-two property $z + z = 0$ and `zero_add` simplifies to $0 + c = c$. Thus, $c = z + w$.

    lines 50–51

    uses congrArg, add_assoc, zero_add

      · have hh := congrArg (fun v => z + v) h
        simpa only [← add_assoc, h2, zero_add] using hh
congrArg
Applying a function to both sides of an equality preserves the equality: if $a_1 = a_2$, then $f(a_1) = f(a_2)$.
add_assoc
Addition in the 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$.
add_left_cancel
Left addition can be cancelled: if $a + b = a + c$, then $b = c$.
in338_reverse_translation
In an exponent-two group, translation by $c$ is its own inverse: if $a + c = b$, then $b + c = a$.
in338_slide_translation
In an exponent-two group, shifting by $e$ before and after translating by $c$ cancels out: $((a + e) + c) + e = a + c$.
mem_insert
An element belongs to $\text{insert}(b, s)$ if and only if it equals $b$ or belongs to $s$.
mem_singleton
An element belongs to the singleton $\{a\}$ if and only if it equals $a$.

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 {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 {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_color_unique    {G : Type*} [AddCommGroup G] [DecidableEq G]    (h2 : ∀ v : G, v + v = 0) (e x y z w c : G)    (hzext : z + e ∉ ({x,x+e,z,y,y+e,w} : Finset G)) (hc : c ≠ 0)    (ht : ∀ v ∈ ({x,x+e,z,y,y+e,w} : Finset G),      v + c ∈ ({x,x+e,z,y,y+e,w} : Finset G)) : c = z + w := by  let U : Finset G := {x,x+e,z,y,y+e,w}  have hp : ∀ t : G, t ∈ U → t + e ∈ U → z + c ≠ t ∧ z + c ≠ t + e := by    intro t htU hteU    constructor    · intro h      have hb := in338_reverse_translation h2 z t c h      have heq : (t + e) + c = z + e := by        calc          _ = (t + c) + e := by abel          _ = z + e := by rw [hb]      exact hzext (heq ▸ ht (t+e) hteU)    · intro h      have hb := in338_reverse_translation h2 z (t+e) c h      have heq : t + c = z + e := by        calc          _ = ((t+e)+c)+e := (in338_slide_translation h2 t e c).symm          _ = z + e := congrArg (fun v => v+e) hb      exact hzext (heq ▸ ht t htU)  have hpx := hp x (by simp [U]) (by simp [U])  have hpy := hp y (by simp [U]) (by simp [U])  have hz := ht z (by simp)  simp only [mem_insert, mem_singleton] at hz  rcases hz with h | h | h | h | h | h  · exact (hpx.1 h).elim  · exact (hpx.2 h).elim  · exact (hc (add_left_cancel (h.trans (add_zero z).symm))).elim  · exact (hpy.1 h).elim  · exact (hpy.2 h).elim  · have hh := congrArg (fun v => z + v) h    simpa only [← add_assoc, h2, zero_add] using hh
See it in the graphDiscuss this resultChallenge it