op_1429_mirror_symmetric_m_leafy_trees_nonempty
For all natural numbers m ≥ 1 and n ≥ 1, the set mirror_symmetric_m_leafy_trees m n is nonempty.
Statement
theorem op_1429_mirror_symmetric_m_leafy_trees_nonempty (m n : ℕ) (hm : 1 ≤ m) (hn : 1 ≤ n) :
(mirror_symmetric_m_leafy_trees m n).Nonempty- Formalizes
- 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).
- 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.
- plane_tree_subtreesThe collection of all rooted subtrees T_v of a plane tree T.
- 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).
- plane_tree_num_leavesThe number of leaves of a plane tree T, denoted ℓ(T).
- PlaneTreeA finite plane tree is either a leaf or an internal node with a list of child plane trees.
- 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.
- in_m_leafy_treesLT_n^m is the set of m-leafy trees with n internal vertices and mn + 1 leaves.
- Used by 1
- 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.
Read back from the Lean
For all natural numbers $m$ and $n$, if $1 \le m$ and $1 \le n$, then the set mirror_symmetric_m_leafy_trees m n is nonempty (that is, there exists a PlaneTree $t$ that belongs to mirror_symmetric_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
To show that the set of mirror-symmetric m-leafy trees with n internal nodes and m * n + 1 leaves is nonempty for all m, n ≥ 1, the proof explicitly constructs a family of trees chain k j. For j = 0, the tree is a root node with k leaf children, and for j + 1 it is a root node with chain k j as its unique child. Induction shows that chain k j has j + 1 internal nodes, k leaves, is mirror-symmetric, and has only leaves and shorter chain trees as its subtrees. Choosing k = m * n + 1 and j = n - 1 produces a mirror-symmetric tree with n internal nodes and m * n + 1 leaves, and the subtree classification guarantees that the m-leafy inequality holds on every subtree.
The chain tree chain k j has exactly j + 1 internal nodes.
We argue by induction on j. In the base case j = 0, the tree consists of a root with k leaf children; by a nested induction on k, each leaf has 0 internal nodes, so the children contribute 0 internal nodes and the root gives 1 + 0 = 1. In the inductive step j + 1, the root has a single child chain k j; by the induction hypothesis, this child has j + 1 internal nodes, so the tree has 1 + (j + 1) = j + 2 internal nodes.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain,op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node,List.replicate_succ,plane_tree_num_internal.eq_1induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] have h : List.map plane_tree_num_internal (List.replicate k PlaneTree.leaf) = List.replicate k 0 := by induction k with | zero => rfl | succ k ih => simp [List.replicate_succ, plane_tree_num_internal.eq_1, ih] rw [h] simp | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] simp [ih] omega
The chain tree chain k j has exactly k leaves.
We argue by induction on j. For j = 0, the tree is a root with k leaf children; an inner induction on k shows that each leaf contributes 1 leaf, summing to k. For the inductive step j + 1, the tree has a single child chain k j, which has k leaves by the induction hypothesis, so the entire tree also has k leaves.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain,op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node,List.replicate_succ,plane_tree_num_leaves.eq_1induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node] have h : List.map plane_tree_num_leaves (List.replicate k PlaneTree.leaf) = List.replicate k 1 := by induction k with | zero => rfl | succ k ih => simp [List.replicate_succ, plane_tree_num_leaves.eq_1, ih] rw [h] simp | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node] simp [ih]
The chain tree chain k j is mirror-symmetric.
We proceed by induction on j. For j = 0, mirroring each of the k leaf children leaves each leaf unchanged (shown by induction on k), and reversing a list of k identical leaves yields the same list, so the tree is invariant under reflection. For j + 1, the tree has a single child chain k j; mirroring it and reversing a singleton list preserves the single child by the induction hypothesis.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain,op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node,List.replicate_succ,plane_tree_mirror.eq_1induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node] have h : List.map plane_tree_mirror (List.replicate k PlaneTree.leaf) = List.replicate k PlaneTree.leaf := by induction k with | zero => rfl | succ k ih => simp [List.replicate_succ, plane_tree_mirror.eq_1, ih] rw [h] simp | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node] simp [ih]
Every subtree of chain k j is either a leaf or chain k i for some i ≤ j.
We proceed by induction on j. For j = 0, the subtrees of the tree are the tree itself (which is chain k 0, giving the witness i = 0 ≤ 0) and the subtrees of its children; since every child is a leaf, any subtree of a child must be a leaf. For j + 1, the subtrees are the tree itself (which is chain k (j + 1), giving i = j + 1 ≤ j + 1) and the subtrees of its single child chain k j; by the induction hypothesis, any subtree of the child is either a leaf or chain k i with i ≤ j ≤ j + 1.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain,op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node,List.mem_cons,le_refl,List.mem_flatMap,List.eq_of_mem_replicate,plane_tree_subtrees.eq_1,List.mem_singleton,List.flatMap_cons,List.flatMap_nil,List.append_nil,Nat.le_succ_of_leinduction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain, op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node] at hs simp only [List.mem_cons] at hs rcases hs with h | h · right; exact ⟨0, le_refl 0, h⟩ · left have hsub : ∀ x ∈ List.flatMap plane_tree_subtrees (List.replicate k PlaneTree.leaf), x = PlaneTree.leaf := by intro x hx rw [List.mem_flatMap] at hx rcases hx with ⟨c, hc, hxc⟩ have hcleaf : c = PlaneTree.leaf := List.eq_of_mem_replicate hc subst hcleaf rw [plane_tree_subtrees.eq_1] at hxc simp only [List.mem_singleton] at hxc exact hxc exact hsub s h | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain, op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node] at hs simp only [List.mem_cons] at hs rcases hs with h | h · right; exact ⟨j + 1, le_refl _, h⟩ · rw [List.flatMap_cons, List.flatMap_nil, List.append_nil] at h rcases ih h with hleaf | ⟨i, hle, heq⟩ · left; exact hleaf · right; exact ⟨i, Nat.le_succ_of_le hle, heq⟩
For any n ≥ 1, the tree chain (m * n + 1) (n - 1) is m-leafy.
We verify m * num_internal(s) < num_leaves(s) for every subtree s. By the subtree classification, s is either a leaf or chain (m * n + 1) i with i ≤ n - 1. If s is a leaf, it has 0 internal nodes and 1 leaf, so m * 0 = 0 < 1 holds. If s = chain (m * n + 1) i, it has i + 1 internal nodes and m * n + 1 leaves; since i ≤ n - 1, we have i + 1 ≤ n, and multiplying by m gives m * (i + 1) ≤ m * n < m * n + 1.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_subtrees_mem,plane_tree_num_internal.eq_1,plane_tree_num_leaves.eq_1,op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal,op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves,Nat.mul_le_mul_leftintro s hs rcases op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_subtrees_mem (m * n + 1) (n - 1) hs with rfl | ⟨i, hle, rfl⟩ · rw [plane_tree_num_internal.eq_1, plane_tree_num_leaves.eq_1] omega · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal, op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves] have : i + 1 ≤ n := by omega have : m * (i + 1) ≤ m * n := Nat.mul_le_mul_left m this omega
The set mirror_symmetric_m_leafy_trees m n is nonempty.
We provide chain (m * n + 1) (n - 1) as an explicit witness. It is m-leafy by the previous step, has (n - 1) + 1 = n internal nodes (using n ≥ 1), has m * n + 1 leaves, and is invariant under reflection, showing that it belongs to the set.
uses
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain,op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_is_m_leafy,op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal,op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves,op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_mirrorrefine ⟨op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain (m * n + 1) (n - 1), ?_⟩ refine ⟨⟨op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_is_m_leafy m n hn, ?_, ?_⟩, ?_⟩ · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal] omega · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves] · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_mirror]
List.replicate_succ- A list with n + 1 copies of an element a equals a followed by n copies of a
plane_tree_num_internal.eq_1- The number of internal nodes of a leaf is 0
plane_tree_num_leaves.eq_1- The number of leaves of a leaf is 1
plane_tree_mirror.eq_1- The mirror reflection of a leaf is the leaf itself
plane_tree_subtrees.eq_1- The list of subtrees of a leaf contains only the leaf itself
List.mem_cons- An element belongs to a list constructed with cons (b :: l) if and only if it equals the head b or belongs to the tail l
le_refl- Every element is less than or equal to itself: a ≤ a
List.mem_flatMap- An element belongs to the flat-map of f over a list if and only if it belongs to f(a) for some element a of that list
List.eq_of_mem_replicate- Any element belonging to a list formed by replicating an element a must be equal to a
List.mem_singleton- An element belongs to the singleton list [b] if and only if it equals b
List.flatMap_cons- Flat-mapping a function over x :: xs equals the function evaluated at x concatenated with the flat-map over xs
List.flatMap_nil- Flat-mapping any function over an empty list yields an empty list
List.append_nil- Appending an empty list to any list leaves the list unchanged
Nat.le_succ_of_le- If n ≤ m, then n ≤ m + 1
Nat.mul_le_mul_left- Multiplying both sides of an inequality n ≤ m on the left by k yields k * n ≤ k * m
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain- Definition of the chain tree family: chain k 0 is a root node with k leaf children, and chain k (j + 1) is a root node containing chain k j as its unique child
op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node- The number of internal nodes of a node equals 1 plus the sum of the internal node counts of its children
op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node- The number of leaves of a node equals the sum of the leaf counts of its children
op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node- Mirroring a node recursively mirrors each of its children and reverses the resulting list of children
op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node- The subtrees of a node are the node itself prepended to the concatenation of the subtrees of all its children
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal- The chain tree chain k j has exactly j + 1 internal nodes
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves- The chain tree chain k j has exactly k leaves
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_mirror- The chain tree chain k j is invariant under reflection (mirror-symmetric)
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_subtrees_mem- Every subtree of chain k j is either a leaf or chain k i for some index i ≤ j
op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_is_m_leafy- For n ≥ 1, the chain tree chain (m * n + 1) (n - 1) satisfies the m-leafy condition on all of its subtrees
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.
def op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain (k : ℕ) : ℕ → PlaneTree | 0 => PlaneTree.node (List.replicate k PlaneTree.leaf) | j + 1 => PlaneTree.node [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k j]theorem op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal (k j : ℕ) : plane_tree_num_internal (op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k j) = j + 1 := by induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] have h : List.map plane_tree_num_internal (List.replicate k PlaneTree.leaf) = List.replicate k 0 := by induction k with | zero => rfl | succ k ih => simp [List.replicate_succ, plane_tree_num_internal.eq_1, ih] rw [h] simp | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_internal_node] simp [ih] omegatheorem op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves (k j : ℕ) : plane_tree_num_leaves (op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k j) = k := by induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node] have h : List.map plane_tree_num_leaves (List.replicate k PlaneTree.leaf) = List.replicate k 1 := by induction k with | zero => rfl | succ k ih => simp [List.replicate_succ, plane_tree_num_leaves.eq_1, ih] rw [h] simp | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_num_leaves_node] simp [ih]theorem op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_mirror (k j : ℕ) : plane_tree_mirror (op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k j) = op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k j := by induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node] have h : List.map plane_tree_mirror (List.replicate k PlaneTree.leaf) = List.replicate k PlaneTree.leaf := by induction k with | zero => rfl | succ k ih => simp [List.replicate_succ, plane_tree_mirror.eq_1, ih] rw [h] simp | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain] rw [op_1429_mirror_symmetric_m_leafy_trees_involution_mirror_node] simp [ih]theorem op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_subtrees_mem (k j : ℕ) {s : PlaneTree} (hs : s ∈ plane_tree_subtrees (op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k j)) : s = PlaneTree.leaf ∨ ∃ i ≤ j, s = op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain k i := by induction j with | zero => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain, op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node] at hs simp only [List.mem_cons] at hs rcases hs with h | h · right; exact ⟨0, le_refl 0, h⟩ · left have hsub : ∀ x ∈ List.flatMap plane_tree_subtrees (List.replicate k PlaneTree.leaf), x = PlaneTree.leaf := by intro x hx rw [List.mem_flatMap] at hx rcases hx with ⟨c, hc, hxc⟩ have hcleaf : c = PlaneTree.leaf := List.eq_of_mem_replicate hc subst hcleaf rw [plane_tree_subtrees.eq_1] at hxc simp only [List.mem_singleton] at hxc exact hxc exact hsub s h | succ j ih => rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain, op_1429_mirror_symmetric_m_leafy_trees_involution_subtrees_node] at hs simp only [List.mem_cons] at hs rcases hs with h | h · right; exact ⟨j + 1, le_refl _, h⟩ · rw [List.flatMap_cons, List.flatMap_nil, List.append_nil] at h rcases ih h with hleaf | ⟨i, hle, heq⟩ · left; exact hleaf · right; exact ⟨i, Nat.le_succ_of_le hle, heq⟩theorem op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_is_m_leafy (m n : ℕ) (hn : 1 ≤ n) : is_m_leafy m (op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain (m * n + 1) (n - 1)) := by intro s hs rcases op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_subtrees_mem (m * n + 1) (n - 1) hs with rfl | ⟨i, hle, rfl⟩ · rw [plane_tree_num_internal.eq_1, plane_tree_num_leaves.eq_1] omega · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal, op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves] have : i + 1 ≤ n := by omega have : m * (i + 1) ≤ m * n := Nat.mul_le_mul_left m this omega/-- For all m, n ≥ 1, the set mirror_symmetric_m_leafy_trees m n is nonempty. -/theorem op_1429_mirror_symmetric_m_leafy_trees_nonempty (m n : ℕ) (hm : 1 ≤ m) (hn : 1 ≤ n) : (mirror_symmetric_m_leafy_trees m n).Nonempty := by refine ⟨op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain (m * n + 1) (n - 1), ?_⟩ refine ⟨⟨op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_is_m_leafy m n hn, ?_, ?_⟩, ?_⟩ · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_internal] omega · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_num_leaves] · rw [op_1429_mirror_symmetric_m_leafy_trees_nonempty_chain_mirror]