op_1430_involution_group_n_one
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
- MLeafyTreeThe type MLeafyTree m n is the subtype of plane trees belonging to LT_n^m.
- 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_n_one_uniqueFor every natural number m ≥ 1, there exists a unique tree t such that t ∈ mirror_symmetric_m_leafy_trees m 1.
- is_m_leafyA tree T is m-leafy if every rooted subtree T_v satisfies ℓ(T_v) > m * n(T_v).
- plane_tree_num_internalThe number of internal vertices of a plane tree T, denoted n(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.
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.
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.
uses
Subtype.ext,op_1429_mirror_symmetric_m_leafy_trees_n_one_unique_tree_eq_node_replicatehaveI : 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]
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.
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.
- The hypotheses that τ₁ and τ₂ are involutions (h₁ : τ₁ ^ 2 = 1 and h₂ : τ₂ ^ 2 = 1) and that m ≥ 1 (hm : 1 ≤ m) are not actually used in the proof; the conclusion holds solely because MLeafyTree m 1 has at most one element, making its entire permutation group trivial.
- Line 16 relies entirely on Lean's typeclass synthesis (infer_instance) to deduce that a subgroup of permutations on a subsingleton type is itself a subsingleton.
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.
/-- 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