Lemma 1.2: symmetric figure-eights lift through abelian normal subgroups
ProvedCayleyErdosGyarfas.symmetric_figure_eight_lifts_of_abelianLet be a finite group of odd order and let be a generating set of that is closed under inverses and does not contain the identity. Let be an abelian normal subgroup, and write
for the image of in with the identity coset removed. Then
A symmetric figure-eight is a pair of cycles of a common length , , that share exactly one vertex, one of which is a left translate of the other up to the choice of starting vertex (definition CayleyErdosGyarfas_HasSymmetricFigureEight). The cycle lengths upstairs and downstairs may differ. Here, for a group and a subset , is the Cayley graph with vertex set in which distinct are adjacent when or for some ; every left multiplication is an automorphism of it. A cycle of length is a closed walk with whose vertices are pairwise distinct.
In the paper this lemma drives the induction on in the proof of Theorem 1.1, through quotients by abelian normal subgroups.
Formalization Note The kernel hypotheses are [A.Normal] and [IsMulCommutative A], and the quotient generating set is (QuotientGroup.mk (s := A)) '' S \ {1}. Removing the identity coset matches the paper and does not change the quotient graph, which has no loops. The statement is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.symmetric_figure_eight_lifts_of_abelian in the Challenge of Palomar entry PALOMAR-2026-11-04-000015, where it is proved.
import Definitions.Def_CayleyErdosGyarfas_HasSymmetricFigureEight import Mathlib.GroupTheory.Nilpotent import Mathlib.GroupTheory.PGroup import Mathlib.Data.Set.Card
namespace CayleyErdosGyarfas
/-- **Lemma 1.2** (arXiv:2611.05060v1, p. 2). Let `G = ⟨S⟩` be a finite group of odd
order, with `S` symmetric and `1 ∉ S`, and let `A` be an abelian normal subgroup. Put
`S̄ = {sA : s ∈ S} \ {A}`. If `Cay(G/A, S̄)` contains a symmetric figure-eight, then
so does `Cay(G, S)`. -/
theorem symmetric_figure_eight_lifts_of_abelian
{G : Type*} [Group G] [Finite G] (S : Set G)
(hodd : Odd (Nat.card G))
(hinv : ∀ s ∈ S, s⁻¹ ∈ S)
(hone : (1 : G) ∉ S)
(hgen : Subgroup.closure S = ⊤)
(A : Subgroup G) [A.Normal] [IsMulCommutative A]
(hfigure : HasSymmetricFigureEight
((QuotientGroup.mk (s := A)) '' S \ {1})) :
HasSymmetricFigureEight S := by sorry
end CayleyErdosGyarfasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be any finite group whose order is odd, and let be a subset such that
- is closed under inverses: for every ;
- ;
- generates : the subgroup generated by is all of .
Let be a subgroup that is normal in and abelian, meaning for all . Only elements of are required to commute with each other. Nothing is assumed about commutativity in or , and need not be central.
is the quotient group. Its elements are the cosets (; left and right cosets agree because is normal), multiplied by , with identity . The map , , is the quotient map. The set in the main hypothesis is built in two steps: first take the image of under , then remove the identity coset:
Cayley graphs. For a group and a subset , is the simple graph (undirected, no loops) with vertex set . Two vertices are adjacent iff and there is some with or . Equivalently, and . The elements of act by right multiplication, so every left translation preserves adjacency.
The hypotheses on simplify adjacency in the two graphs used here:
- In : iff .
- In : iff and for some . That is, iff , where .
- Removing from does not change the quotient graph, because loops are excluded anyway. Elements of contribute no edges to it.
A closed walk of length at a vertex is a sequence of vertices with for . Its vertices are . It is a cycle if it is not the trivial walk, uses no edge twice, and are pairwise distinct. When (always the case below), this reduces to being pairwise distinct: the walk visits distinct vertices and returns to only at the end. Rotating a list to the left by positions gives , with taken modulo .
Main hypothesis. This is the property the code calls a symmetric figure eight, applied to and . Unfolded, it says that there exist an integer , a coset and two closed walks at in , whose entries are cosets:
such that:
- and are cycles, and both have length exactly . The same applies to both, so the common length is .
- There exist a coset and some such that rotating the list to the left by positions gives exactly the list .
- Equivalently, for , with subscripts read modulo (consistent because ).
- Only rotations are allowed, not reversals. So runs through the left translate of by in the same direction, starting from its vertex .
- For every : is a vertex of both and iff . That is, is the only vertex the two cycles have in common.
Conclusion. This is the same property, applied to and . There exist an integer , an element and two closed walks at in :
Here adjacency means and for . They satisfy:
- and are cycles of length exactly : are pairwise distinct, and likewise .
- There exist and with for , subscripts modulo . That is, is rotated to the left by positions.
- For every : is a vertex of both and iff .
The theorem asserts that, under all of the hypotheses above, the main hypothesis implies the conclusion. No relation is required between the witnesses of the conclusion and the witnesses of the hypothesis. For example, may differ from , and need not map onto under .
Edge cases.
- . Then is an isomorphism , and because . The main hypothesis is then exactly the conclusion transported along .
- . This is possible only if is abelian. Then has one element and , so has one vertex and no edges. The main hypothesis is false, and the statement holds vacuously.
- Small index. In general, the main hypothesis needs at least distinct cosets: two cycles of vertices each that share only . So it cannot hold, and the theorem is vacuous, whenever . Since is odd (because is), this means .
- The translating element. (respectively ) is not stated to be nontrivial, but it cannot be the identity. If it were, both cycles would have the same vertices, contradicting item 3.
- Role of the side conditions. The property being unfolded does not itself require its set to be inverse-closed, free of the identity, or generating. Those conditions, the odd order of and the commutativity of appear only as hypotheses of the theorem. Normality of is also what makes a group.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.