op_1429_mirror_symmetric_m_leafy_trees_involution
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
- op_1429_mirror_symmetric_m_leafy_trees_n_one_uniqueFor every natural number m ≥ 1, there exists a unique tree t such that t ∈ mirror_symmetric_m_leafy_trees m 1.
- op_1429_mirror_symmetric_m_leafy_trees_nonemptyFor all natural numbers m ≥ 1 and n ≥ 1, the set mirror_symmetric_m_leafy_trees m n is nonempty.
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)$.
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.
uses
PlaneTree.rec,List.mem_consrefine 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
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.
uses
plane_tree_mirror.eq_2rw [plane_tree_mirror.eq_2] simp
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.
uses
plane_tree_num_leaves.eq_2rw [plane_tree_num_leaves.eq_2] simp
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.
uses
plane_tree_num_internal.eq_2rw [plane_tree_num_internal.eq_2] simp
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.
uses
plane_tree_subtrees.eq_2rw [plane_tree_subtrees.eq_2] simp
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.
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_leftinduction 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
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.
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_leftinduction 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
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)$.
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_mapinduction 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⟩
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.
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_mirrorintro 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
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$.
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_mirrorrcases 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
- The definitions of `plane_tree_mirror`, `plane_tree_num_leaves`, `plane_tree_num_internal`, and `plane_tree_subtrees` use well-founded recursion over the list of children using `cs.attach`. Lemmas 2 through 5 (`mirror_node`, `num_leaves_node`, `num_internal_node`, and `subtrees_node`) strip away this subtype attachment artifact so that subsequent induction arguments can work directly with standard list operations.
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
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
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]