AFTD Auto-Formalizing Theoretical Domains

op_300_prism_three_leap_group_eq_top

theoremverifiedformalization

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

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

    lines 4–6

    uses SimpleGraph.boxProd_adj

      intro x y
      rw [SimpleGraph.boxProd_adj]
      infer_instance
  2. 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₃).

    lines 11–19

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

    lines 20–28

    uses Subgroup.subset_closure

      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)
  4. 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`).

    lines 29–33

    uses mul_mem

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

    lines 34–39

    uses List.isCycle_formPerm, List.support_formPerm_of_nodup

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

    lines 40–44

    uses eq_top_iff, Equiv.Perm.closure_cycle_adjacent_swap, Subgroup.closure_le

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

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

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