AFTD Auto-Formalizing Theoretical Domains

op_1429_mirror_symmetric_m_leafy_trees_involution

theoremverifiedformalization

The mirror reflection involution τ preserves the class LT_n^m of m-leafy trees with n internal vertices and mn + 1 leaves.

Statement

theorem op_1429_mirror_symmetric_m_leafy_trees_involution (m n : ℕ) (t : PlaneTree)
    (h : in_m_leafy_trees m n t) :
    in_m_leafy_trees m n (plane_tree_mirror t)
Formalizes
arXiv:2611.10154 Sec. 2.3
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7
  • PlaneTreeA finite plane tree is either a leaf or an internal node with a list of child plane trees.
  • plane_tree_num_internalThe number of internal vertices of a plane tree T, denoted n(T).
  • plane_tree_subtreesThe collection of all rooted subtrees T_v of a plane tree T.
  • plane_tree_num_leavesThe number of leaves of a plane tree T, denoted ℓ(T).
  • in_m_leafy_treesLT_n^m is the set of m-leafy trees with n internal vertices and mn + 1 leaves.
  • plane_tree_mirrorThe left-right mirror reflection involution τ on plane trees, recursively reversing child order.
  • is_m_leafyA tree T is m-leafy if every rooted subtree T_v satisfies ℓ(T_v) > m * n(T_v).
Used by 2

Read back from the Lean

For all natural numbers $m$ and $n$, and every plane tree $t$, if $t$ is an $m$-leafy tree with $n$ internal nodes and $m \cdot n + 1$ leaves (that is, in_m_leafy_trees m n t holds), then the mirror image of $t$ (plane_tree_mirror t) also satisfies in_m_leafy_trees m n.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The mirror reflection involution $\tau$ acts on a plane tree by recursively reversing the order of the children at every internal node while reflecting each child. To prove that $\tau$ preserves membership in the family $\mathrm{LT}_n^m$ of $m$-leafy trees with $n$ internal vertices and $mn + 1$ leaves, the argument proceeds by structural tree induction. First, it shows that $\tau$ preserves the total number of leaves and internal vertices because list reversal does not affect list sums. Next, it establishes that every subtree of $\tau(t)$ is the reflection of some subtree of $t$, ensuring that the defining inequality $m \cdot \mathrm{internal}(s) < \mathrm{leaves}(s)$ holds on all subtrees of $\tau(t)$.

  1. A property $P$ holds for all plane trees if it holds for leaves and holds for any internal node whose children all satisfy $P$.

    Lean's built-in recursor `PlaneTree.rec` requires mutual recursion over trees and lists of trees. By choosing the list motive to be $\lambda cs. \, \forall c \in cs, P(c)$, the base case for the empty list is vacuously true, and the induction step for $c :: cs$ splits on whether an element is the head or in the tail, resolving each by the respective induction hypothesis.

    lines 5–15

    uses PlaneTree.rec, List.mem_cons

      refine PlaneTree.rec (motive_1 := P) (motive_2 := fun cs => ∀ c ∈ cs, P c)
        hleaf
        (fun cs ih => hnode cs ih)
        (by intro c hc; cases hc)
        (fun head tail ih_head ih_tail => by
          intro c hc
          simp only [List.mem_cons] at hc
          rcases hc with rfl | hc
          · exact ih_head
          · exact ih_tail c hc)
        t
  2. The mirror reflection of an internal node reverses its reflected children: $\tau(\mathrm{node}(cs)) = \mathrm{node}((\mathrm{map}(\tau, cs)).\mathrm{reverse})$. automation

    Rewriting with the definitional equation `plane_tree_mirror.eq_2` and simplifying away the subtype attachment (`attach`) used in the well-founded recursive definition.

    lines 19–20

    uses plane_tree_mirror.eq_2

      rw [plane_tree_mirror.eq_2]
      simp
  3. The number of leaves of an internal node equals the sum of the leaf counts of its children: $\mathrm{leaves}(\mathrm{node}(cs)) = \sum_{c \in cs} \mathrm{leaves}(c)$. automation

    Rewriting with `plane_tree_num_leaves.eq_2` and simplifying away the subtype attachment.

    lines 24–25

    uses plane_tree_num_leaves.eq_2

      rw [plane_tree_num_leaves.eq_2]
      simp
  4. The number of internal vertices of an internal node equals $1 + \sum_{c \in cs} \mathrm{internal}(c)$. automation

    Rewriting with `plane_tree_num_internal.eq_2` and simplifying away the subtype attachment.

    lines 29–30

    uses plane_tree_num_internal.eq_2

      rw [plane_tree_num_internal.eq_2]
      simp
  5. The subtrees of an internal node consist of the node itself followed by all subtrees of its children: $\mathrm{subtrees}(\mathrm{node}(cs)) = \mathrm{node}(cs) :: \mathrm{flatMap}(\mathrm{subtrees}, cs)$. automation

    Rewriting with `plane_tree_subtrees.eq_2` and simplifying away the subtype attachment.

    lines 34–35

    uses plane_tree_subtrees.eq_2

      rw [plane_tree_subtrees.eq_2]
      simp
  6. Mirror reflection preserves the number of leaves of any plane tree: $\mathrm{leaves}(\tau(t)) = \mathrm{leaves}(t)$.

    By tree induction on $t$. For a leaf, $\tau(\mathrm{leaf}) = \mathrm{leaf}$, so the leaf count is unchanged. For an internal node with children $cs$, mirror reflection reverses the list of mirrored children; since list reversal preserves list sums (`List.sum_reverse`), and by the induction hypothesis $\mathrm{leaves}(\tau(c)) = \mathrm{leaves}(c)$ for each child $c \in cs$ via `List.map_congr_left`, the total leaf count is preserved.

    lines 39–51

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_induction, plane_tree_mirror.eq_1, op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node, op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node, List.map_reverse, List.sum_reverse, List.map_map, List.map_congr_left

      induction t using op_1429_mirror_symmetric_m_leafy_trees_involution_induction with
      | hleaf =>
        rw [plane_tree_mirror.eq_1]
      | hnode cs ih =>
        rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,
            op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node,
            op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node]
        rw [List.map_reverse, List.sum_reverse]
        congr 1
        rw [List.map_map]
        apply List.map_congr_left
        intro x hx
        exact ih x hx
  7. Mirror reflection preserves the number of internal vertices of any plane tree: $\mathrm{internal}(\tau(t)) = \mathrm{internal}(t)$.

    By tree induction on $t$. For a leaf, $\tau(\mathrm{leaf}) = \mathrm{leaf}$ has 0 internal vertices. For an internal node with children $cs$, its internal count is $1$ plus the sum over its children; list reversal preserves the sum, and by the induction hypothesis $\mathrm{internal}(\tau(c)) = \mathrm{internal}(c)$ for each child, so the internal vertex count is preserved.

    lines 55–67

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_induction, plane_tree_mirror.eq_1, op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node, op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node, List.map_reverse, List.sum_reverse, List.map_map, List.map_congr_left

      induction t using op_1429_mirror_symmetric_m_leafy_trees_involution_induction with
      | hleaf =>
        rw [plane_tree_mirror.eq_1]
      | hnode cs ih =>
        rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,
            op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node,
            op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node]
        rw [List.map_reverse, List.sum_reverse]
        congr 2
        rw [List.map_map]
        apply List.map_congr_left
        intro x hx
        exact ih x hx
  8. Every subtree of the mirror tree $\tau(t)$ is the mirror reflection $\tau(u)$ of some subtree $u$ of $t$.

    By tree induction on $t$, generalizing over the subtree $s$. If $t$ is a leaf, its only subtree is itself, which is $\tau(\mathrm{leaf})$. If $t = \mathrm{node}(cs)$, any subtree $s$ of $\tau(t)$ is either the root node itself—which is $\tau(\mathrm{node}(cs))$—or a subtree of some reversed child $c' \in (\mathrm{map}(\tau, cs)).\mathrm{reverse}$. In the latter case, $c' = \tau(c)$ for some child $c \in cs$, and the induction hypothesis on $c$ yields a subtree $u$ of $c$ (and hence of $t$) such that $s = \tau(u)$.

    lines 72–92

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_induction, plane_tree_mirror.eq_1, plane_tree_subtrees.eq_1, List.mem_singleton, op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node, op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node, List.mem_cons, List.mem_flatMap, List.mem_reverse, List.mem_map

      induction t using op_1429_mirror_symmetric_m_leafy_trees_involution_induction generalizing s with
      | hleaf =>
        rw [plane_tree_mirror.eq_1, plane_tree_subtrees.eq_1] at hs
        simp only [List.mem_singleton] at hs
        subst hs
        exact ⟨.leaf, by rw [plane_tree_subtrees.eq_1]; simp, plane_tree_mirror.eq_1.symm⟩
      | hnode cs ih =>
        rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,
            op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node] at hs
        simp only [List.mem_cons, List.mem_flatMap] at hs
        rcases hs with rfl | ⟨c', hc', hs⟩
        · exact ⟨.node cs, by rw [op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node]; simp,
                 by rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node]⟩
        · rw [List.mem_reverse, List.mem_map] at hc'
          rcases hc' with ⟨c, hc, rfl⟩
          rcases ih c hc s hs with ⟨u, hu, rfl⟩
          refine ⟨u, ?_, rfl⟩
          rw [op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node]
          simp only [List.mem_cons, List.mem_flatMap]
          right
          exact ⟨c, hc, hu⟩
  9. If a plane tree $t$ is $m$-leafy, its mirror reflection $\tau(t)$ is also $m$-leafy.

    To show that $\tau(t)$ is $m$-leafy, consider any subtree $s \in \mathrm{subtrees}(\tau(t))$. By `mem_subtrees_mirror`, $s = \tau(u)$ for some subtree $u$ of $t$. Since mirror reflection preserves both internal vertex count and leaf count, the condition $m \cdot \mathrm{internal}(s) < \mathrm{leaves}(s)$ reduces to $m \cdot \mathrm{internal}(u) < \mathrm{leaves}(u)$, which holds because $t$ is $m$-leafy.

    lines 97–101

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_mem_subtrees_mirror, op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror, op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror

      intro s hs
      rcases op_1429_mirror_symmetric_m_leafy_trees_involution_mem_subtrees_mirror t s hs with ⟨u, hu, rfl⟩
      rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror,
          op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror]
      exact h u hu
  10. Mirror reflection preserves membership in $\mathrm{LT}_n^m$: if $t \in \mathrm{LT}_n^m$, then $\tau(t) \in \mathrm{LT}_n^m$.

    Unpacking $t \in \mathrm{LT}_n^m$ gives that $t$ is $m$-leafy, has $n$ internal vertices, and has $mn + 1$ leaves. By `is_m_leafy_mirror`, $\tau(t)$ is $m$-leafy; by `num_internal_mirror`, $\mathrm{internal}(\tau(t)) = \mathrm{internal}(t) = n$; and by `num_leaves_mirror`, $\mathrm{leaves}(\tau(t)) = \mathrm{leaves}(t) = mn + 1$. Together, these establish $\tau(t) \in \mathrm{LT}_n^m$.

    lines 107–110

    uses op_1429_mirror_symmetric_m_leafy_trees_involution_is_m_leafy_mirror, op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror, op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror

      rcases h with ⟨hlef, hint, hlea⟩
      refine ⟨op_1429_mirror_symmetric_m_leafy_trees_involution_is_m_leafy_mirror m t hlef, ?_, ?_⟩
      · rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror, hint]
      · rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror, hlea]
PlaneTree.rec
structural recursion on plane trees with motives for trees and for child lists
List.mem_cons
membership in a cons list: $a \in b :: l \iff a = b \lor a \in l$
plane_tree_mirror.eq_2
definitional equation expanding `plane_tree_mirror` on an internal node using `attach`
plane_tree_num_leaves.eq_2
definitional equation expanding `plane_tree_num_leaves` on an internal node using `attach`
plane_tree_num_internal.eq_2
definitional equation expanding `plane_tree_num_internal` on an internal node using `attach`
plane_tree_subtrees.eq_2
definitional equation expanding `plane_tree_subtrees` on an internal node using `attach`
op_1429_mirror_symmetric_m_leafy_trees_involution_induction
structural induction principle for plane trees: a property holds for all trees if it holds for leaves and holds for any internal node whose children all satisfy it
plane_tree_mirror.eq_1
the mirror reflection of a leaf is a leaf
op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node
the mirror reflection of an internal node reverses its reflected children: $\tau(\mathrm{node}(cs)) = \mathrm{node}((\mathrm{map}(\tau, cs)).\mathrm{reverse})$
op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node
the number of leaves of an internal node is the sum of the leaf counts of its children
List.map_reverse
mapping over a reversed list equals reversing the mapped list: $\mathrm{map}(f, l.\mathrm{reverse}) = (\mathrm{map}(f, l)).\mathrm{reverse}$
List.sum_reverse
the sum of elements in a reversed list equals the sum of the original list
List.map_map
functoriality of map: $\mathrm{map}(g, \mathrm{map}(f, l)) = \mathrm{map}(g \circ f, l)$
List.map_congr_left
if two functions agree on every element of a list, mapping them over that list yields the same result
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node
the number of internal vertices of an internal node is $1$ plus the sum of the internal counts of its children
plane_tree_subtrees.eq_1
the only subtree of a leaf is the leaf itself
List.mem_singleton
membership in a singleton list: $a \in [b] \iff a = b$
op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node
the subtrees of an internal node consist of the node itself followed by all subtrees of its children
List.mem_flatMap
membership in a flattened list map: $b \in \mathrm{flatMap}(f, l) \iff \exists a \in l, b \in f(a)$
List.mem_reverse
membership in a reversed list is equivalent to membership in the original list: $x \in as.\mathrm{reverse} \iff x \in as$
List.mem_map
membership in an image list: $b \in \mathrm{map}(f, l) \iff \exists a \in l, f(a) = b$
op_1429_mirror_symmetric_m_leafy_trees_involution_mem_subtrees_mirror
every subtree of $\tau(t)$ is the mirror reflection $\tau(u)$ of some subtree $u$ of $t$
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror
mirror reflection preserves the number of internal vertices: $\mathrm{internal}(\tau(t)) = \mathrm{internal}(t)$
op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror
mirror reflection preserves the number of leaves: $\mathrm{leaves}(\tau(t)) = \mathrm{leaves}(t)$
op_1429_mirror_symmetric_m_leafy_trees_involution_is_m_leafy_mirror
if a plane tree is $m$-leafy, its mirror reflection is also $m$-leafy

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

theorem op_1429_mirror_symmetric_m_leafy_trees_involution_induction (P : PlaneTree → Prop)    (hleaf : P .leaf)    (hnode : ∀ cs : List PlaneTree, (∀ c ∈ cs, P c) → P (.node cs))    (t : PlaneTree) : P t := by  refine PlaneTree.rec (motive_1 := P) (motive_2 := fun cs => ∀ c ∈ cs, P c)    hleaf    (fun cs ih => hnode cs ih)    (by intro c hc; cases hc)    (fun head tail ih_head ih_tail => by      intro c hc      simp only [List.mem_cons] at hc      rcases hc with rfl | hc      · exact ih_head      · exact ih_tail c hc)    ttheorem op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node (cs : List PlaneTree) :    plane_tree_mirror (.node cs) = .node (cs.map plane_tree_mirror).reverse := by  rw [plane_tree_mirror.eq_2]  simptheorem op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node (cs : List PlaneTree) :    plane_tree_num_leaves (.node cs) = (cs.map plane_tree_num_leaves).sum := by  rw [plane_tree_num_leaves.eq_2]  simptheorem op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node (cs : List PlaneTree) :    plane_tree_num_internal (.node cs) = 1 + (cs.map plane_tree_num_internal).sum := by  rw [plane_tree_num_internal.eq_2]  simptheorem op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node (cs : List PlaneTree) :    plane_tree_subtrees (.node cs) = .node cs :: cs.flatMap plane_tree_subtrees := by  rw [plane_tree_subtrees.eq_2]  simptheorem op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror (t : PlaneTree) :    plane_tree_num_leaves (plane_tree_mirror t) = plane_tree_num_leaves t := by  induction t using op_1429_mirror_symmetric_m_leafy_trees_involution_induction with  | hleaf =>    rw [plane_tree_mirror.eq_1]  | hnode cs ih =>    rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,        op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node,        op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node]    rw [List.map_reverse, List.sum_reverse]    congr 1    rw [List.map_map]    apply List.map_congr_left    intro x hx    exact ih x hxtheorem op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror (t : PlaneTree) :    plane_tree_num_internal (plane_tree_mirror t) = plane_tree_num_internal t := by  induction t using op_1429_mirror_symmetric_m_leafy_trees_involution_induction with  | hleaf =>    rw [plane_tree_mirror.eq_1]  | hnode cs ih =>    rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,        op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node,        op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node]    rw [List.map_reverse, List.sum_reverse]    congr 2    rw [List.map_map]    apply List.map_congr_left    intro x hx    exact ih x hxtheorem op_1429_mirror_symmetric_m_leafy_trees_involution_mem_subtrees_mirror (t : PlaneTree) (s : PlaneTree)    (hs : s ∈ plane_tree_subtrees (plane_tree_mirror t)) :    ∃ u ∈ plane_tree_subtrees t, s = plane_tree_mirror u := by  induction t using op_1429_mirror_symmetric_m_leafy_trees_involution_induction generalizing s with  | hleaf =>    rw [plane_tree_mirror.eq_1, plane_tree_subtrees.eq_1] at hs    simp only [List.mem_singleton] at hs    subst hs    exact ⟨.leaf, by rw [plane_tree_subtrees.eq_1]; simp, plane_tree_mirror.eq_1.symm⟩  | hnode cs ih =>    rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,        op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node] at hs    simp only [List.mem_cons, List.mem_flatMap] at hs    rcases hs with rfl | ⟨c', hc', hs⟩    · exact ⟨.node cs, by rw [op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node]; simp,             by rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node]⟩    · rw [List.mem_reverse, List.mem_map] at hc'      rcases hc' with ⟨c, hc, rfl⟩      rcases ih c hc s hs with ⟨u, hu, rfl⟩      refine ⟨u, ?_, rfl⟩      rw [op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node]      simp only [List.mem_cons, List.mem_flatMap]      right      exact ⟨c, hc, hu⟩theorem op_1429_mirror_symmetric_m_leafy_trees_involution_is_m_leafy_mirror (m : ℕ) (t : PlaneTree)    (h : is_m_leafy m t) :    is_m_leafy m (plane_tree_mirror t) := by  intro s hs  rcases op_1429_mirror_symmetric_m_leafy_trees_involution_mem_subtrees_mirror t s hs with ⟨u, hu, rfl⟩  rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror,      op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror]  exact h u hu/-- The mirror reflection map preserves membership in LT_n^m. -/theorem op_1429_mirror_symmetric_m_leafy_trees_involution (m n : ℕ) (t : PlaneTree)    (h : in_m_leafy_trees m n t) :    in_m_leafy_trees m n (plane_tree_mirror t) := by  rcases h with ⟨hlef, hint, hlea⟩  refine ⟨op_1429_mirror_symmetric_m_leafy_trees_involution_is_m_leafy_mirror m t hlef, ?_, ?_⟩  · rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_mirror, hint]  · rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_mirror, hlea]
See it in the graphDiscuss this resultChallenge it