op_300_hypercube_one_leap_group_card
The hypercube graph Q₁ (the path K₂) has leap group of cardinality 2.
Statement
theorem op_300_hypercube_one_leap_group_card :
Nat.card (simple_graph_leap_group (simple_graph_hypercube 1)) = 2- Formalizes
- arXiv:2610.18463 Question 5.4
- Verified
- 26 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 5
- simple_graph_hypercubeThe hypercube graph Q_n on vertex set Fin n → Bool, where two vertices are adjacent if and only if they differ at exactly one coordinate.
- 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_hypercube_coordinate_flipThe permutation of the vertices of the hypercube Q_n that inverts a single coordinate i.
- simple_graph_is_hop_mem_leap_groupEvery hop lies in the leap group.
- 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 cardinality (via Nat.card) of the leap group of the 1-dimensional hypercube graph simple_graph_hypercube 1 is equal to 2, where the 1-dimensional hypercube is the simple graph on vertices Fin 1 → Bool with adjacency given by differing at exactly one coordinate (via SimpleGraph.fromRel), and the leap group of a graph is the subgroup of vertex permutations generated by all permutations $h$ such that every vertex $v$ is adjacent to $h(v)$.
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 the leap group of the 1-dimensional hypercube graph Q₁ is the full symmetric group on its two vertices. Flipping the single coordinate exchanges the two vertices, which satisfies the adjacency condition and makes the flip a hop belonging to the leap group. Since every permutation of a two-element set is either the identity or this coordinate flip, the leap group is the entire symmetric group ⊤. The order of the leap group is therefore the order of the symmetric group on two elements, which is 2.
The coordinate flip at index 0 is a hop of Q₁, and therefore belongs to the leap group of Q₁.
To show that the leap group is the top subgroup, we first show that the coordinate flip at index 0 is a hop. By the definition of hypercube adjacency (`SimpleGraph.fromRel_adj`), two vertices are adjacent if and only if they differ at exactly one coordinate. For any vertex v : Fin 1 → Bool, flipping coordinate 0 negates its value, so v differs from its image. Because the index set Fin 1 has only one coordinate, index 0 is the unique coordinate where they differ, proving that every vertex is adjacent to its flip. Thus the flip is a hop, and by `simple_graph_is_hop_mem_leap_group`, it belongs to the leap group.
uses
SimpleGraph.fromRel_adj,simple_graph_is_hop_mem_leap_grouphave htop : simple_graph_leap_group (simple_graph_hypercube 1) = ⊤ := by have hflip_hop : simple_graph_is_hop (simple_graph_hypercube 1) (simple_graph_hypercube_coordinate_flip 1 0) := by intro v rw [simple_graph_hypercube, SimpleGraph.fromRel_adj] refine ⟨?_, ?_⟩ · intro h apply_fun (· 0) at h change v 0 = Function.update v 0 (!v 0) 0 at h simp at h · left refine ⟨0, ?_, ?_⟩ · change v 0 ≠ Function.update v 0 (!v 0) 0 simp · intro j hj fin_cases j rfl have hflip_mem : simple_graph_hypercube_coordinate_flip 1 0 ∈ simple_graph_leap_group (simple_graph_hypercube 1) := simple_graph_is_hop_mem_leap_group _ _ hflip_hop
The leap group of Q₁ is the full symmetric group ⊤.
A subgroup equals ⊤ if and only if it contains every element of the group (`Subgroup.eq_top_iff'`). Since the vertex set Fin 1 → Bool has order 2, an exhaustive check (`decide`) shows that any permutation σ is either the identity 1 or the coordinate flip at index 0. The identity belongs to every subgroup (`Subgroup.one_mem`), and the coordinate flip was shown to belong to the leap group. Thus every permutation is in the leap group, establishing that the leap group is ⊤.
uses
Subgroup.eq_top_iff',Subgroup.one_memrw [Subgroup.eq_top_iff'] intro σ have hcases : σ = 1 ∨ σ = simple_graph_hypercube_coordinate_flip 1 0 := by revert σ decide rcases hcases with rfl | rfl · exact Subgroup.one_mem _ · exact hflip_mem
The cardinality of the leap group of Q₁ is 2.
Since the leap group is ⊤, its cardinality equals that of the full permutation group on Fin 1 → Bool (`Subgroup.topEquiv.toEquiv`, `Nat.card_congr`, `Nat.card_eq_fintype_card`). The vertex set has 2 elements, so its symmetric group has cardinality 2! = 2, which Lean evaluates by computation (`decide`).
uses
Nat.card_congr,Subgroup.topEquiv.toEquiv,Nat.card_eq_fintype_cardrw [htop, Nat.card_congr Subgroup.topEquiv.toEquiv, Nat.card_eq_fintype_card] decide
SimpleGraph.fromRel_adj- In a graph defined by a relation via `SimpleGraph.fromRel r`, two vertices are adjacent if and only if they are distinct and either the relation holds from the first to the second or vice versa.
simple_graph_is_hop_mem_leap_group- Every hop of a graph belongs to its leap group.
Subgroup.eq_top_iff'- A subgroup H is the full group ⊤ if and only if every element of the group belongs to H.
Subgroup.one_mem- The group identity element 1 belongs to every subgroup.
Nat.card_congr- Equivalent types have the same cardinality.
Subgroup.topEquiv.toEquiv- The top subgroup ⊤ of a group is equivalent, as a type, to the group itself.
Nat.card_eq_fintype_card- For a finite type, `Nat.card` equals `Fintype.card`.
- The fact that the symmetric group on two elements contains only the identity and the transposition (line 26), as well as its order being 2 (line 31), are verified by computational reflection via the `decide` tactic.
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.
/-- The 1-dimensional hypercube has leap group of order 2. -/theorem op_300_hypercube_one_leap_group_card : Nat.card (simple_graph_leap_group (simple_graph_hypercube 1)) = 2 := by have htop : simple_graph_leap_group (simple_graph_hypercube 1) = ⊤ := by have hflip_hop : simple_graph_is_hop (simple_graph_hypercube 1) (simple_graph_hypercube_coordinate_flip 1 0) := by intro v rw [simple_graph_hypercube, SimpleGraph.fromRel_adj] refine ⟨?_, ?_⟩ · intro h apply_fun (· 0) at h change v 0 = Function.update v 0 (!v 0) 0 at h simp at h · left refine ⟨0, ?_, ?_⟩ · change v 0 ≠ Function.update v 0 (!v 0) 0 simp · intro j hj fin_cases j rfl have hflip_mem : simple_graph_hypercube_coordinate_flip 1 0 ∈ simple_graph_leap_group (simple_graph_hypercube 1) := simple_graph_is_hop_mem_leap_group _ _ hflip_hop rw [Subgroup.eq_top_iff'] intro σ have hcases : σ = 1 ∨ σ = simple_graph_hypercube_coordinate_flip 1 0 := by revert σ decide rcases hcases with rfl | rfl · exact Subgroup.one_mem _ · exact hflip_mem rw [htop, Nat.card_congr Subgroup.topEquiv.toEquiv, Nat.card_eq_fintype_card] decide