op_1429_mirror_symmetric_m_leafy_trees_n_one_unique
For every natural number m ≥ 1, there exists a unique tree t such that t ∈ mirror_symmetric_m_leafy_trees m 1.
Statement
theorem op_1429_mirror_symmetric_m_leafy_trees_n_one_unique (m : ℕ) (hm : 1 ≤ m) :
∃! t : PlaneTree, t ∈ mirror_symmetric_m_leafy_trees m 1- Source
- arXiv:2611.10154 Sec. 2.3
- Verified
- 11 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 9
- plane_tree_num_internalThe number of internal vertices of a plane tree T, denoted n(T).
- PlaneTreeA finite plane tree is either a leaf or an internal node with a list of child plane trees.
- 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.
- is_m_leafyA tree T is m-leafy if every rooted subtree T_v satisfies ℓ(T_v) > m * n(T_v).
- plane_tree_num_leavesThe number of leaves of a plane tree T, denoted ℓ(T).
- op_1429_mirror_symmetric_m_leafy_trees_involutionThe mirror reflection involution τ preserves the class LT_n^m of m-leafy trees with n internal vertices and mn + 1 leaves.
- mirror_symmetric_m_leafy_treesThe set mirror_symmetric_m_leafy_trees m n consists of all trees t in in_m_leafy_trees m n satisfying plane_tree_mirror t = t.
- plane_tree_mirrorThe left-right mirror reflection involution τ on plane trees, recursively reversing child order.
- in_m_leafy_treesLT_n^m is the set of m-leafy trees with n internal vertices and mn + 1 leaves.
- Used by 2
- plane_tree_subtrees_nodeThe rooted subtrees of a node with children cs are the node itself together with the rooted subtrees of each child: s is a rooted subtree…
- op_1430_involution_group_n_oneFor n = 1 and any m ≥ 1, any two involutions on MLeafyTree m 1 generate a trivial (subsingleton) permutation subgroup.
Read back from the Lean
For every natural number $m$ with $1 \le m$, there exists a unique plane tree $t$ belonging to the set of mirror-symmetric $m$-leafy trees with parameter $n = 1$.
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
For n = 1 and any m ≥ 1, a tree in mirror_symmetric_m_leafy_trees m 1 must have exactly 1 internal node and m + 1 leaves. A tree with 1 internal node is necessarily a root node whose children all have 0 internal nodes, making every child a leaf. Therefore, any such tree must be the unique root node with m + 1 leaf children. Existence comes from the nonemptiness theorem, and uniqueness follows because any two elements share this identical shape.
A plane tree with 0 internal nodes must be a leaf.
We proceed by cases on the tree t. If t is a leaf, the claim is trivial. If t is a node, its internal node count is 1 plus the sum of internal nodes of its children, which is at least 1, contradicting that the count is 0.
uses
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_nodecases t with | leaf => rfl | node cs => rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at h omega
A list whose elements are all leaves is equal to a replicate of leaves.
By induction on the list cs. If cs is empty, both sides are empty. In the inductive step, the head is a leaf and every element of the tail is a leaf; rewriting by the induction hypothesis on the tail completes the step.
uses
List.mem_cons_self,List.mem_cons_of_mem,List.length_cons,List.replicate_succinduction cs with | nil => rfl | cons head tail ih => have hhead : head = PlaneTree.leaf := h head List.mem_cons_self have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc) rw [hhead, List.length_cons, List.replicate_succ] congr 1 exact ih htail
The total number of leaves across a list of leaves equals the length of the list.
By induction on the list cs. If cs is empty, both the sum and length are 0. For head :: tail, head contributes 1 leaf and the tail contributes tail.length leaves by the induction hypothesis, so the sum is 1 + tail.length = tail.length + 1.
uses
List.mem_cons_self,List.mem_cons_of_mem,List.map_cons,List.sum_cons,plane_tree_num_leaves.eq_1,List.length_consinduction cs with | nil => rfl | cons head tail ih => have hhead : head = PlaneTree.leaf := h head List.mem_cons_self have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc) rw [List.map_cons, List.sum_cons, hhead, plane_tree_num_leaves.eq_1, ih htail, List.length_cons] omega
If a list of natural numbers sums to 0, every element in the list is 0.
By induction on the list l. An empty list has no elements. For head :: tail, head + tail.sum = 0 forces head = 0 and tail.sum = 0; if x is the head then x = 0, and if x is in the tail then x = 0 by the induction hypothesis.
uses
List.sum_cons,List.mem_cons.mpinduction l with | nil => contradiction | cons head tail ih => rw [List.sum_cons] at h have : head = 0 ∧ tail.sum = 0 := by omega rcases List.mem_cons.mp hx with rfl | hmem · exact this.1 · exact ih this.2 hmem
A tree with 1 internal node cannot be a leaf.
A leaf has 0 internal nodes by definition, which contradicts the assumption that it has 1 internal node.
uses
plane_tree_num_internal.eq_1cases t with | leaf => rw [plane_tree_num_internal.eq_1] at hint contradiction
A tree with 1 internal node is a node whose children are all leaves, replicated to match the tree's leaf count.
If t = node cs has 1 internal node, then 1 + ∑ internal(cs) = 1, so the sum of internal nodes of the children is 0. Therefore every child has 0 internal nodes and is a leaf. Thus cs is a list of leaves, which means cs = replicate cs.length leaf. Since each child is a leaf, the number of leaves of t is exactly cs.length.
uses
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node,List.mem_map_of_mem,op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero,op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero,op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf,op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node,op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum| node cs => rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at hint have hsum : (List.map plane_tree_num_internal cs).sum = 0 := by omega have hcs_zero : ∀ c ∈ cs, plane_tree_num_internal c = 0 := by intro c hc have hmem : plane_tree_num_internal c ∈ List.map plane_tree_num_internal cs := List.mem_map_of_mem hc exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero _ hsum _ hmem have hcs_leaf : ∀ c ∈ cs, c = PlaneTree.leaf := fun c hc => op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero c (hcs_zero c hc) have hcs_eq : cs = List.replicate cs.length PlaneTree.leaf := op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf cs hcs_leaf have hleaves : plane_tree_num_leaves (PlaneTree.node cs) = cs.length := by rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node] exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum cs hcs_leaf rw [hleaves] congr 1There exists a witness tree t₀ in mirror_symmetric_m_leafy_trees m 1.
We invoke the nonemptiness theorem for m ≥ 1 and n = 1 to obtain a witness tree t₀, reducing the goal to showing that any tree in the set must equal t₀.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty,le_rflrcases op_1429_mirror_symmetric_m_leafy_trees_nonempty m 1 hm le_rfl with ⟨t0, ht0⟩ refine ⟨t0, ht0, fun y hy => ?_⟩
Any tree in mirror_symmetric_m_leafy_trees m 1 is a node with m + 1 leaf children.
Any tree t in the set has 1 internal node and m · 1 + 1 = m + 1 leaves. By our earlier lemma, any tree with 1 internal node is a node whose children are leaves equal in number to the tree's leaf count, so t must be a node with m + 1 leaves.
uses
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicatehave h_eq : ∀ t, t ∈ mirror_symmetric_m_leafy_trees m 1 → t = PlaneTree.node (List.replicate (m + 1) PlaneTree.leaf) := by intro t ht rcases ht with ⟨⟨-, hint, hleaves⟩, -⟩ have ht_shape := op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t hint rw [hleaves] at ht_shape have : m * 1 + 1 = m + 1 := by omega rw [this] at ht_shape exact ht_shape
The tree in mirror_symmetric_m_leafy_trees m 1 is unique.
Both an arbitrary element y and the witness t₀ equal the unique node with m + 1 leaf children, so y = t₀.
rw [h_eq y hy, h_eq t0 ht0]
List.length_cons- Prepending an element to a list increases its length by 1.
List.map_cons- Mapping a function over a non-empty list applies the function to the head and maps over the tail.
List.mem_map_of_mem- If an element belongs to a list, its image under a function belongs to the mapped list.
List.mem_cons.mp- If an element belongs to a prepended list, it either equals the head or belongs to the tail.
List.mem_cons_of_mem- An element belonging to a list also belongs to that list prepended with any head.
List.mem_cons_self- An element is always a member of any list of which it is the head.
List.replicate_succ- Replicating an element n + 1 times equals prepending the element to its n-fold replication.
List.sum_cons- The sum of a non-empty list is its head plus the sum of its tail.
le_rfl- The relation ≤ is reflexive on any preorder.
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node- The number of internal nodes in a node tree is 1 plus the sum of the internal nodes of its children.
op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node- The number of leaves of a node tree is the sum of the leaves of its children.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf- A list in which every tree is a leaf is equal to replicating a leaf as many times as the list's length.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum- If every tree in a list is a leaf, the sum of their leaf counts equals the length of the list.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero- If the sum of a list of natural numbers is 0, every element in the list is 0.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero- A plane tree with 0 internal nodes must be a leaf.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate- A tree with exactly 1 internal node is a node whose children are all leaves, with count equal to the number of leaves of the tree.
op_1429_mirror_symmetric_m_leafy_trees_nonempty- For any m ≥ 1 and n ≥ 1, the set of mirror-symmetric m-leafy trees with parameter n is nonempty.
plane_tree_num_internal.eq_1- A leaf tree has 0 internal nodes.
plane_tree_num_leaves.eq_1- A leaf tree has 1 leaf.
- Automated linear arithmetic (`omega`) is used throughout for trivial inequalities and equalities on natural numbers, such as showing 1 + ∑ ... = 0 is impossible, 1 + |tail| = |tail| + 1, and m * 1 + 1 = m + 1.
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.
lemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero (t : PlaneTree) (h : plane_tree_num_internal t = 0) : t = PlaneTree.leaf := by cases t with | leaf => rfl | node cs => rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at h omegalemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf (cs : List PlaneTree) (h : ∀ c ∈ cs, c = PlaneTree.leaf) : cs = List.replicate cs.length PlaneTree.leaf := by induction cs with | nil => rfl | cons head tail ih => have hhead : head = PlaneTree.leaf := h head List.mem_cons_self have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc) rw [hhead, List.length_cons, List.replicate_succ] congr 1 exact ih htaillemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum (cs : List PlaneTree) (h : ∀ c ∈ cs, c = PlaneTree.leaf) : (List.map plane_tree_num_leaves cs).sum = cs.length := by induction cs with | nil => rfl | cons head tail ih => have hhead : head = PlaneTree.leaf := h head List.mem_cons_self have htail : ∀ c ∈ tail, c = PlaneTree.leaf := fun c hc => h c (List.mem_cons_of_mem head hc) rw [List.map_cons, List.sum_cons, hhead, plane_tree_num_leaves.eq_1, ih htail, List.length_cons] omegalemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero (l : List ℕ) (h : l.sum = 0) (x : ℕ) (hx : x ∈ l) : x = 0 := by induction l with | nil => contradiction | cons head tail ih => rw [List.sum_cons] at h have : head = 0 ∧ tail.sum = 0 := by omega rcases List.mem_cons.mp hx with rfl | hmem · exact this.1 · exact ih this.2 hmemlemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate (t : PlaneTree) (hint : plane_tree_num_internal t = 1) : t = PlaneTree.node (List.replicate (plane_tree_num_leaves t) PlaneTree.leaf) := by cases t with | leaf => rw [plane_tree_num_internal.eq_1] at hint contradiction | node cs => rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] at hint have hsum : (List.map plane_tree_num_internal cs).sum = 0 := by omega have hcs_zero : ∀ c ∈ cs, plane_tree_num_internal c = 0 := by intro c hc have hmem : plane_tree_num_internal c ∈ List.map plane_tree_num_internal cs := List.mem_map_of_mem hc exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_nat_list_sum_eq_zero _ hsum _ hmem have hcs_leaf : ∀ c ∈ cs, c = PlaneTree.leaf := fun c hc => op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_num_internal_eq_zero c (hcs_zero c hc) have hcs_eq : cs = List.replicate cs.length PlaneTree.leaf := op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_eq_replicate_leaf cs hcs_leaf have hleaves : plane_tree_num_leaves (PlaneTree.node cs) = cs.length := by rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node] exact op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_list_leaves_sum cs hcs_leaf rw [hleaves] congr 1/-- For n = 1 and any m ≥ 1, there exists a unique tree in mirror_symmetric_m_leafy_trees m 1. -/theorem op_1429_mirror_symmetric_m_leafy_trees_n_one_unique (m : ℕ) (hm : 1 ≤ m) : ∃! t : PlaneTree, t ∈ mirror_symmetric_m_leafy_trees m 1 := by rcases op_1429_mirror_symmetric_m_leafy_trees_nonempty m 1 hm le_rfl with ⟨t0, ht0⟩ refine ⟨t0, ht0, fun y hy => ?_⟩ have h_eq : ∀ t, t ∈ mirror_symmetric_m_leafy_trees m 1 → t = PlaneTree.node (List.replicate (m + 1) PlaneTree.leaf) := by intro t ht rcases ht with ⟨⟨-, hint, hleaves⟩, -⟩ have ht_shape := op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t hint rw [hleaves] at ht_shape have : m * 1 + 1 = m + 1 := by omega rw [this] at ht_shape exact ht_shape rw [h_eq y hy, h_eq t0 ht0]