AFTD Auto-Formalizing Theoretical Domains

op_1429_mirror_symmetric_m_leafy_trees_nonempty

theoremverifiedformalization

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
Used by 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.

  1. 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.

    lines 7–21

    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_1

      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]
        omega
  2. 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.

    lines 25–38

    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_1

      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]
  3. 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.

    lines 43–56

    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_1

      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]
  4. 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.

    lines 61–86

    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_le

      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⟩
  5. 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.

    lines 90–98

    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_left

      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
  6. 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.

    lines 103–108

    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_mirror

      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]
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

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]
See it in the graphDiscuss this resultChallenge it