AFTD Auto-Formalizing Theoretical Domains

op_1430_involution_group_n_one

theoremverified

For n = 1 and any m ≥ 1, any two involutions on MLeafyTree m 1 generate a trivial (subsingleton) permutation subgroup.

Statement

theorem op_1430_involution_group_n_one (m : ℕ) (hm : 1 ≤ m)
    (τ₁ τ₂ : Equiv.Perm (MLeafyTree m 1)) (h₁ : τ₁ ^ 2 = 1) (h₂ : τ₂ ^ 2 = 1) :
    Subsingleton (Subgroup.closure {τ₁, τ₂})
Source
arXiv:2611.10154 Sec. 2.1
Verified
11 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 7

Read back from the Lean

For any natural number $m$ with $1 \le m$, and for any two permutations $\tau_1, \tau_2$ of the type MLeafyTree m 1 such that $\tau_1^2 = 1$ and $\tau_2^2 = 1$, the subgroup of Equiv.Perm (MLeafyTree m 1) generated by $\{\tau_1, \tau_2\}$ is a subsingleton (i.e., contains at most one element, meaning it is the trivial subgroup).

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 proof shows that MLeafyTree m 1 contains at most one tree (is a subsingleton), because any plane tree with exactly one internal node and m + 1 leaves is uniquely determined as a root node with m + 1 leaf children. Since the underlying type is a subsingleton, its permutation group is trivial, and typeclass resolution immediately concludes that the subgroup generated by τ₁ and τ₂ is subsingleton.

  1. MLeafyTree m 1 is a subsingleton (it contains at most one tree).

    To show that any two trees t₁ and t₂ in MLeafyTree m 1 are equal, it suffices by Subtype.ext to show their underlying plane trees are equal. By the definition of MLeafyTree with n = 1, each tree has exactly 1 internal node and m * 1 + 1 leaves. By lemma op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate, any plane tree with exactly 1 internal node is uniquely determined by its number of leaves as a single node with that many leaf children. Substituting the common leaf count m * 1 + 1 for both trees shows that t₁ and t₂ are identical.

    lines 5–15

    uses Subtype.ext, op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate

      haveI : Subsingleton (MLeafyTree m 1) := by
        constructor
        intro t1 t2
        apply Subtype.ext
        have h1int : plane_tree_num_internal t1.1 = 1 := t1.2.2.1
        have h2int : plane_tree_num_internal t2.1 = 1 := t2.2.2.1
        have h1leaves : plane_tree_num_leaves t1.1 = m * 1 + 1 := t1.2.2.2
        have h2leaves : plane_tree_num_leaves t2.1 = m * 1 + 1 := t2.2.2.2
        rw [op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t1.1 h1int,
            op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t2.1 h2int,
            h1leaves, h2leaves]
  2. The subgroup generated by τ₁ and τ₂ is a subsingleton. automation

    Because the underlying set MLeafyTree m 1 has at most one element, its only permutation is the identity. Lean's typeclass inference automatically concludes that the permutation group, and consequently any subgroup of it, is a subsingleton.

    line 16

      infer_instance
Subtype.ext
Two elements of a subtype are equal if their underlying values are equal.
op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate
Any plane tree with exactly 1 internal node is a single root node whose children are leaves, with the number of leaf children equal to the total number of leaves in the tree.

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

/-- For n = 1, any two involutions on m-leafy trees generate a trivial permutation group. -/theorem op_1430_involution_group_n_one (m : ℕ) (hm : 1 ≤ m)    (τ₁ τ₂ : Equiv.Perm (MLeafyTree m 1)) (h₁ : τ₁ ^ 2 = 1) (h₂ : τ₂ ^ 2 = 1) :    Subsingleton (Subgroup.closure {τ₁, τ₂}) := by  haveI : Subsingleton (MLeafyTree m 1) := by    constructor    intro t1 t2    apply Subtype.ext    have h1int : plane_tree_num_internal t1.1 = 1 := t1.2.2.1    have h2int : plane_tree_num_internal t2.1 = 1 := t2.2.2.1    have h1leaves : plane_tree_num_leaves t1.1 = m * 1 + 1 := t1.2.2.2    have h2leaves : plane_tree_num_leaves t2.1 = m * 1 + 1 := t2.2.2.2    rw [op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t1.1 h1int,        op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicate t2.1 h2int,        h1leaves, h2leaves]  infer_instance
See it in the graphDiscuss this resultChallenge it