op_300_prism_three_leap_group_eq_top
For n = 3, the triangular prism graph P₁ □ C₃ on 6 vertices has full leap group S₆.
Statement
theorem op_300_prism_three_leap_group_eq_top :
simple_graph_leap_group (simple_graph_prism 3) = ⊤- Formalizes
- arXiv:2610.18463 Question 5.4
- Verified
- 29 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- simple_graph_prismThe prism graph P₁ □ C_n on vertex set Fin 2 × Fin n, defined as the Cartesian box product of the 2-vertex complete graph K₂ (the path P₁)…
- simple_graph_leap_groupThe leap group Λ₁(G) of a graph G: the subgroup of the symmetric group on the vertices generated by the hops of G.
- simple_graph_is_hopA hop (graph derangement) of a graph G is a permutation h of the vertices that sends every vertex v to a neighbour h(v) of v.
Read back from the Lean
The leap group of the triangular prism graph (the Cartesian/box product of the complete graph on Fin 2 and the cycle graph on Fin 3) is the full symmetric group on its vertex set Fin 2 × Fin 3. That is, the permutations of Fin 2 × Fin 3 that map every vertex to an adjacent vertex generate the entire group of permutations Equiv.Perm (Fin 2 × Fin 3).
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 prove that the leap group of the triangular prism graph P₁ □ C₃ on 6 vertices is the full symmetric group S₆, the proof exhibits three explicit hops H₂, H₃, and H₁₀ in the graph. The conjugate product H₂ * H₃ * H₂ yields the transposition swapping v₁ and v₄, showing this transposition belongs to the leap group. Since H₁₀ is a 6-cycle with full support mapping v₁ to v₄, the leap group contains both a full cycle and an adjacent transposition along that cycle. By `Equiv.Perm.closure_cycle_adjacent_swap`, any full cycle and adjacent transposition generate the entire symmetric group, so the leap group is S₆.
Adjacency in the Cartesian (box) product of two simple graphs is decidable whenever adjacency in both factor graphs is decidable.
For any two vertices x, y in the product graph, the box product adjacency relation is rewritten via `SimpleGraph.boxProd_adj` into a disjunction of conjunctions involving factor adjacencies and equalities. Typeclass inference (`infer_instance`) automatically synthesizes the Decidable instance for this boolean combination from the decidability of adjacency and equality on each factor.
uses
SimpleGraph.boxProd_adjintro x y rw [SimpleGraph.boxProd_adj] infer_instance
The six vertices of the triangular prism are labeled, and three candidate permutations H₂, H₃, and H₁₀ are defined.
The vertices of the triangular prism P₁ □ C₃ are represented by pairs in Fin 2 × Fin 3: the bottom triangle vertices are v₀ = (0,0), v₁ = (0,1), v₂ = (0,2) and the top triangle vertices are v₃ = (1,0), v₄ = (1,1), v₅ = (1,2). Three permutations are defined using `List.formPerm`: H₂ is the product of two disjoint 3-cycles (v₀ v₁ v₂)(v₃ v₅ v₄), H₃ is the 6-cycle (v₀ v₁ v₂ v₅ v₄ v₃), and H₁₀ is the 6-cycle (v₀ v₂ v₁ v₄ v₅ v₃).
let v0 : Fin 2 × Fin 3 := (0, 0) let v1 : Fin 2 × Fin 3 := (0, 1) let v2 : Fin 2 × Fin 3 := (0, 2) let v3 : Fin 2 × Fin 3 := (1, 0) let v4 : Fin 2 × Fin 3 := (1, 1) let v5 : Fin 2 × Fin 3 := (1, 2) let H2 : Equiv.Perm (Fin 2 × Fin 3) := List.formPerm [v0, v1, v2] * List.formPerm [v3, v5, v4] let H3 : Equiv.Perm (Fin 2 × Fin 3) := List.formPerm [v0, v1, v2, v5, v4, v3] let H10 : Equiv.Perm (Fin 2 × Fin 3) := List.formPerm [v0, v2, v1, v4, v5, v3]
The permutations H₂, H₃, and H₁₀ are hops of the prism graph, and therefore belong to its leap group.
A permutation is a hop (`simple_graph_is_hop`) if every vertex is mapped to an adjacent vertex. For each of H₂, H₃, and H₁₀, this condition is unfolded and verified by exhaustive evaluation over all six vertices using `decide`. By `Subgroup.subset_closure`, each hop belongs to the leap group, which is defined as the subgroup generated by all hops.
uses
Subgroup.subset_closurehave m2 : H2 ∈ simple_graph_leap_group (simple_graph_prism 3) := Subgroup.subset_closure (show simple_graph_is_hop _ H2 by unfold simple_graph_prism simple_graph_is_hop H2; decide) have m3 : H3 ∈ simple_graph_leap_group (simple_graph_prism 3) := Subgroup.subset_closure (show simple_graph_is_hop _ H3 by unfold simple_graph_prism simple_graph_is_hop H3; decide) have m10 : H10 ∈ simple_graph_leap_group (simple_graph_prism 3) := Subgroup.subset_closure (show simple_graph_is_hop _ H10 by unfold simple_graph_prism simple_graph_is_hop H10; decide)
The transposition swapping v₁ and v₄ belongs to the leap group.
Direct computation in the Lean kernel (`decide +kernel`) verifies that the conjugate product H₂ * H₃ * H₂ equals the transposition `Equiv.swap v₁ v₄`. Since H₂ and H₃ are in the leap group, their product also belongs to the leap group by closure under multiplication (`mul_mem`).
uses
mul_memhave hτ : H2 * H3 * H2 = Equiv.swap v1 v4 := by decide +kernel have mτ : Equiv.swap v1 v4 ∈ simple_graph_leap_group (simple_graph_prism 3) := by rw [← hτ] exact mul_mem (mul_mem m2 m3) m2
H₁₀ is a 6-cycle with full support that maps v₁ to v₄.
By `List.isCycle_formPerm`, H₁₀ is a cycle because its defining list has no duplicates and length at least 2 (both checked by `decide`). By `List.support_formPerm_of_nodup`, its support consists of all elements in the list, which `decide` confirms is the entire vertex set ⊤. Finally, `decide` verifies that H₁₀ maps v₁ directly to v₄, meaning v₁ and v₄ are adjacent along the cycle.
uses
List.isCycle_formPerm,List.support_formPerm_of_noduphave hcyc : H10.IsCycle := List.isCycle_formPerm (by decide) (by decide) have hsupp : H10.support = ⊤ := by rw [List.support_formPerm_of_nodup _ (by decide) (by decide)] decide have h14 : H10 v1 = v4 := by decide
The leap group of the triangular prism graph is the full symmetric group ⊤.
By `Equiv.Perm.closure_cycle_adjacent_swap`, any cycle with full support together with the transposition swapping an element x with its image σ(x) generates the full symmetric group ⊤. Applying this to the cycle H₁₀ and the adjacent transposition swap v₁ (H₁₀ v₁) = swap v₁ v₄, the subgroup generated by {H₁₀, swap v₁ v₄} is ⊤. By `Subgroup.closure_le`, to show the leap group is ⊤ it suffices to verify that both H₁₀ and swap v₁ v₄ belong to it, which was established in previous steps.
uses
eq_top_iff,Equiv.Perm.closure_cycle_adjacent_swap,Subgroup.closure_lerw [eq_top_iff, ← Equiv.Perm.closure_cycle_adjacent_swap hcyc hsupp v1, h14, Subgroup.closure_le] intro g hg rcases hg with rfl | rfl · exact m10 · exact mτ
SimpleGraph.boxProd_adj- Two vertices in the box product of two graphs are adjacent if and only if they are adjacent in the first factor and equal in the second, or equal in the first factor and adjacent in the second.
Subgroup.subset_closure- Every element of a subset k belongs to the subgroup generated by k.
mul_mem- If two elements belong to a subgroup, their product also belongs to the subgroup.
List.isCycle_formPerm- The permutation formed from a list with no duplicate elements and of length at least 2 is a cyclic permutation.
List.support_formPerm_of_nodup- For a list with no duplicates whose length is not 1, the support of the permutation formed by the list equals the set of elements in the list.
eq_top_iff- In a bounded partial order, an element equals the top element ⊤ if and only if ⊤ is less than or equal to that element.
Equiv.Perm.closure_cycle_adjacent_swap- For any cyclic permutation σ with full support on a finite type and any element x, the subgroup generated by σ and the transposition swapping x with σ(x) is the full symmetric group ⊤.
Subgroup.closure_le- The subgroup generated by a subset k is contained in a subgroup K if and only if k is a subset of K.
- The verification that H₂, H₃, and H₁₀ are hops, the computation H₂ * H₃ * H₂ = Equiv.swap v₁ v₄, and the cycle properties of H₁₀ are checked by finite computational evaluation (`decide` and `decide +kernel`) on the 6-element vertex set.
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.
private instance op_300_prism_three_boxProd_decidableRel {α β : Type*} [DecidableEq α] [DecidableEq β] (G : SimpleGraph α) (H : SimpleGraph β) [DecidableRel G.Adj] [DecidableRel H.Adj] : DecidableRel (G □ H).Adj := by intro x y rw [SimpleGraph.boxProd_adj] infer_instance/-- The triangular prism graph has full leap group S₆. -/theorem op_300_prism_three_leap_group_eq_top : simple_graph_leap_group (simple_graph_prism 3) = ⊤ := by let v0 : Fin 2 × Fin 3 := (0, 0) let v1 : Fin 2 × Fin 3 := (0, 1) let v2 : Fin 2 × Fin 3 := (0, 2) let v3 : Fin 2 × Fin 3 := (1, 0) let v4 : Fin 2 × Fin 3 := (1, 1) let v5 : Fin 2 × Fin 3 := (1, 2) let H2 : Equiv.Perm (Fin 2 × Fin 3) := List.formPerm [v0, v1, v2] * List.formPerm [v3, v5, v4] let H3 : Equiv.Perm (Fin 2 × Fin 3) := List.formPerm [v0, v1, v2, v5, v4, v3] let H10 : Equiv.Perm (Fin 2 × Fin 3) := List.formPerm [v0, v2, v1, v4, v5, v3] have m2 : H2 ∈ simple_graph_leap_group (simple_graph_prism 3) := Subgroup.subset_closure (show simple_graph_is_hop _ H2 by unfold simple_graph_prism simple_graph_is_hop H2; decide) have m3 : H3 ∈ simple_graph_leap_group (simple_graph_prism 3) := Subgroup.subset_closure (show simple_graph_is_hop _ H3 by unfold simple_graph_prism simple_graph_is_hop H3; decide) have m10 : H10 ∈ simple_graph_leap_group (simple_graph_prism 3) := Subgroup.subset_closure (show simple_graph_is_hop _ H10 by unfold simple_graph_prism simple_graph_is_hop H10; decide) have hτ : H2 * H3 * H2 = Equiv.swap v1 v4 := by decide +kernel have mτ : Equiv.swap v1 v4 ∈ simple_graph_leap_group (simple_graph_prism 3) := by rw [← hτ] exact mul_mem (mul_mem m2 m3) m2 have hcyc : H10.IsCycle := List.isCycle_formPerm (by decide) (by decide) have hsupp : H10.support = ⊤ := by rw [List.support_formPerm_of_nodup _ (by decide) (by decide)] decide have h14 : H10 v1 = v4 := by decide rw [eq_top_iff, ← Equiv.Perm.closure_cycle_adjacent_swap hcyc hsupp v1, h14, Subgroup.closure_le] intro g hg rcases hg with rfl | rfl · exact m10 · exact mτ