Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1.2: symmetric figure-eights lift through abelian normal subgroups

Proved
CayleyErdosGyarfas.symmetric_figure_eight_lifts_of_abelian

by burkh4rt · Nov 12, 2026 · Mathlib 0df444a (Lean v4.33.1)

cayley-graphscombinatoricscycleserdos-gyarfasgraph-theorygroup-theory

Let GGG be a finite group of odd order and let S⊆GS \subseteq GS⊆G be a generating set of GGG that is closed under inverses and does not contain the identity. Let A⊴GA \trianglelefteq GA⊴G be an abelian normal subgroup, and write

S‾={sA:s∈S}∖{A}⊆G/A\overline{S} = \{ sA : s \in S \} \setminus \{ A \} \subseteq G/AS={sA:s∈S}∖{A}⊆G/A

for the image of SSS in G/AG/AG/A with the identity coset removed. Then

Cay⁡(G/A,S‾) contains a symmetric figure-eight  ⟹  Cay⁡(G,S) contains a symmetric figure-eight.\operatorname{Cay}(G/A, \overline{S}) \text{ contains a symmetric figure-eight} \;\Longrightarrow\; \operatorname{Cay}(G, S) \text{ contains a symmetric figure-eight}.Cay(G/A,S) contains a symmetric figure-eight⟹Cay(G,S) contains a symmetric figure-eight.

A symmetric figure-eight is a pair of cycles of a common length 2n2^n2n, n≥2n \ge 2n≥2, 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 HHH and a subset T⊆HT \subseteq HT⊆H, Cay⁡(H,T)\operatorname{Cay}(H,T)Cay(H,T) is the Cayley graph with vertex set HHH in which distinct x,y∈Hx, y \in Hx,y∈H are adjacent when y=xty = xty=xt or x=ytx = ytx=yt for some t∈Tt \in Tt∈T; every left multiplication z↦hzz \mapsto hzz↦hz is an automorphism of it. A cycle of length kkk is a closed walk (v0,v1,…,vk=v0)(v_0, v_1, \dots, v_k = v_0)(v0​,v1​,…,vk​=v0​) with k≥3k \ge 3k≥3 whose vertices v1,…,vkv_1, \dots, v_kv1​,…,vk​ are pairwise distinct.

In the paper this lemma drives the induction on ∣G∣|G|∣G∣ 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.

Preamble
import Definitions.Def_CayleyErdosGyarfas_HasSymmetricFigureEight
import Mathlib.GroupTheory.Nilpotent
import Mathlib.GroupTheory.PGroup
import Mathlib.Data.Set.Card
Formal statement
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 CayleyErdosGyarfas
Source
M. C. Burkhart, Odd-ordered Cayley graphs satisfy Erdős–Gyárfás, arXiv:2611.05060v1 (3 Nov 2026), https://arxiv.org/abs/2611.05060v1, §1, p. 2, Lemma 1.2 (proof in §2, pp. 2–3); standing conventions of §1.1, p. 2. Lean statement as in the Challenge of Palomar entry PALOMAR-2026-11-04-000015 (https://palomar-registry.org/entry?id=PALOMAR-2026-11-04-000015).
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let GGG be any finite group whose order ∣G∣|G|∣G∣ is odd, and let S⊆GS \subseteq GS⊆G be a subset such that

  • SSS is closed under inverses: s−1∈Ss^{-1} \in Ss−1∈S for every s∈Ss \in Ss∈S;
  • 1∉S1 \notin S1∈/S;
  • SSS generates GGG: the subgroup generated by SSS is all of GGG.

Let A≤GA \le GA≤G be a subgroup that is normal in GGG and abelian, meaning ab=baab = baab=ba for all a,b∈Aa, b \in Aa,b∈A. Only elements of AAA are required to commute with each other. Nothing is assumed about commutativity in GGG or G/AG/AG/A, and AAA need not be central.

G/AG/AG/A is the quotient group. Its elements are the cosets xAxAxA (x∈Gx \in Gx∈G; left and right cosets agree because AAA is normal), multiplied by (xA)(yA)=xyA(xA)(yA) = xyA(xA)(yA)=xyA, with identity 1G/A=A1_{G/A} = A1G/A​=A. The map π:G→G/A\pi : G \to G/Aπ:G→G/A, π(x)=xA\pi(x) = xAπ(x)=xA, is the quotient map. The set in the main hypothesis is built in two steps: first take the image of SSS under π\piπ, then remove the identity coset:

S‾  =  π(S)∖{1G/A}  =  {sA:s∈S}∖{A}  =  {sA:s∈S, s∉A}⊆G/A.\overline{S} \;=\; \pi(S)\setminus\{1_{G/A}\} \;=\; \{sA : s\in S\}\setminus\{A\} \;=\; \{sA : s\in S,\ s\notin A\} \subseteq G/A.S=π(S)∖{1G/A​}={sA:s∈S}∖{A}={sA:s∈S, s∈/A}⊆G/A.

Cayley graphs. For a group HHH and a subset T⊆HT\subseteq HT⊆H, Cay(H,T)\mathrm{Cay}(H,T)Cay(H,T) is the simple graph (undirected, no loops) with vertex set HHH. Two vertices x,yx, yx,y are adjacent iff x≠yx\ne yx=y and there is some t∈Tt\in Tt∈T with y=xty = xty=xt or x=ytx = ytx=yt. Equivalently, x≠yx\neq yx=y and x−1y∈T∪T−1x^{-1}y\in T\cup T^{-1}x−1y∈T∪T−1. The elements of TTT act by right multiplication, so every left translation z↦hzz\mapsto hzz↦hz preserves adjacency.

The hypotheses on SSS simplify adjacency in the two graphs used here:

  • In Cay(G,S)\mathrm{Cay}(G,S)Cay(G,S): x∼yx\sim yx∼y iff x−1y∈Sx^{-1}y\in Sx−1y∈S.
  • In Cay(G/A,S‾)\mathrm{Cay}(G/A,\overline{S})Cay(G/A,S): xA∼yAxA\sim yAxA∼yA iff xA≠yAxA\neq yAxA=yA and yA=xsAyA = xsAyA=xsA for some s∈Ss\in Ss∈S. That is, iff x−1y∈SA∖Ax^{-1}y\in SA\setminus Ax−1y∈SA∖A, where SA={sa:s∈S, a∈A}SA=\{sa : s\in S,\ a\in A\}SA={sa:s∈S, a∈A}.
  • Removing 1G/A1_{G/A}1G/A​ from π(S)\pi(S)π(S) does not change the quotient graph, because loops are excluded anyway. Elements of S∩AS\cap AS∩A contribute no edges to it.

A closed walk of length LLL at a vertex vvv is a sequence of vertices (v=z0,z1,…,zL=v)(v = z_0, z_1, \ldots, z_L = v)(v=z0​,z1​,…,zL​=v) with zi−1∼ziz_{i-1}\sim z_izi−1​∼zi​ for 1≤i≤L1\le i\le L1≤i≤L. Its vertices are z0,…,zLz_0,\ldots,z_Lz0​,…,zL​. It is a cycle if it is not the trivial walk, uses no edge twice, and z1,…,zLz_1,\ldots,z_Lz1​,…,zL​ are pairwise distinct. When L≥3L\ge 3L≥3 (always the case below), this reduces to z1,…,zLz_1,\ldots,z_Lz1​,…,zL​ being pairwise distinct: the walk visits LLL distinct vertices and returns to vvv only at the end. Rotating a list (a1,…,aM)(a_1,\ldots,a_M)(a1​,…,aM​) to the left by kkk positions gives (ak+1,…,aM,a1,…,ak)(a_{k+1},\ldots,a_M,a_1,\ldots,a_k)(ak+1​,…,aM​,a1​,…,ak​), with kkk taken modulo MMM.

Main hypothesis. This is the property the code calls a symmetric figure eight, applied to G/AG/AG/A and S‾\overline{S}S. Unfolded, it says that there exist an integer n≥2n\ge 2n≥2, a coset vˉ∈G/A\bar v\in G/Avˉ∈G/A and two closed walks at vˉ\bar vvˉ in Cay(G/A,S‾)\mathrm{Cay}(G/A,\overline{S})Cay(G/A,S), whose entries are cosets:

αˉ=(vˉ=xˉ0,xˉ1,…,xˉ2n=vˉ),βˉ=(vˉ=yˉ0,yˉ1,…,yˉ2n=vˉ),\bar\alpha = (\bar v = \bar x_0,\bar x_1,\ldots,\bar x_{2^n} = \bar v),\qquad \bar\beta = (\bar v = \bar y_0,\bar y_1,\ldots,\bar y_{2^n} = \bar v),αˉ=(vˉ=xˉ0​,xˉ1​,…,xˉ2n​=vˉ),βˉ​=(vˉ=yˉ​0​,yˉ​1​,…,yˉ​2n​=vˉ),

such that:

  1. αˉ\bar\alphaαˉ and βˉ\bar\betaβˉ​ are cycles, and both have length exactly 2n2^n2n. The same nnn applies to both, so the common length is 4,8,16,…4, 8, 16, \ldots4,8,16,….
  2. There exist a coset gˉ∈G/A\bar g\in G/Agˉ​∈G/A and some k∈Nk\in\mathbb Nk∈N such that rotating the list (gˉ xˉ1,…,gˉ xˉ2n)(\bar g\,\bar x_1,\ldots,\bar g\,\bar x_{2^n})(gˉ​xˉ1​,…,gˉ​xˉ2n​) to the left by kkk positions gives exactly the list (yˉ1,…,yˉ2n)(\bar y_1,\ldots,\bar y_{2^n})(yˉ​1​,…,yˉ​2n​).
    • Equivalently, yˉj=gˉ xˉj+k\bar y_j = \bar g\,\bar x_{j+k}yˉ​j​=gˉ​xˉj+k​ for 1≤j≤2n1\le j\le 2^n1≤j≤2n, with subscripts read modulo 2n2^n2n (consistent because xˉ0=xˉ2n\bar x_0=\bar x_{2^n}xˉ0​=xˉ2n​).
    • Only rotations are allowed, not reversals. So βˉ\bar\betaβˉ​ runs through the left translate of αˉ\bar\alphaαˉ by gˉ\bar ggˉ​ in the same direction, starting from its vertex gˉ xˉk=vˉ\bar g\,\bar x_k = \bar vgˉ​xˉk​=vˉ.
  3. For every wˉ∈G/A\bar w\in G/Awˉ∈G/A: wˉ\bar wwˉ is a vertex of both αˉ\bar\alphaαˉ and βˉ\bar\betaβˉ​ iff wˉ=vˉ\bar w=\bar vwˉ=vˉ. That is, vˉ\bar vvˉ is the only vertex the two cycles have in common.

Conclusion. This is the same property, applied to GGG and SSS. There exist an integer m≥2m\ge 2m≥2, an element u∈Gu\in Gu∈G and two closed walks at uuu in Cay(G,S)\mathrm{Cay}(G,S)Cay(G,S):

α=(u=x0,x1,…,x2m=u),β=(u=y0,y1,…,y2m=u).\alpha = (u = x_0,x_1,\ldots,x_{2^m} = u),\qquad \beta = (u = y_0,y_1,\ldots,y_{2^m} = u).α=(u=x0​,x1​,…,x2m​=u),β=(u=y0​,y1​,…,y2m​=u).

Here adjacency means xi−1−1xi∈Sx_{i-1}^{-1}x_i\in Sxi−1−1​xi​∈S and yi−1−1yi∈Sy_{i-1}^{-1}y_i\in Syi−1−1​yi​∈S for 1≤i≤2m1\le i\le 2^m1≤i≤2m. They satisfy:

  1. α\alphaα and β\betaβ are cycles of length exactly 2m2^m2m: x1,…,x2mx_1,\ldots,x_{2^m}x1​,…,x2m​ are pairwise distinct, and likewise y1,…,y2my_1,\ldots,y_{2^m}y1​,…,y2m​.
  2. There exist h∈Gh\in Gh∈G and l∈Nl\in\mathbb Nl∈N with yj=h xj+ly_j = h\,x_{j+l}yj​=hxj+l​ for 1≤j≤2m1\le j\le 2^m1≤j≤2m, subscripts modulo 2m2^m2m. That is, (y1,…,y2m)(y_1,\ldots,y_{2^m})(y1​,…,y2m​) is (hx1,…,hx2m)(hx_1,\ldots,hx_{2^m})(hx1​,…,hx2m​) rotated to the left by lll positions.
  3. For every w∈Gw\in Gw∈G: www is a vertex of both α\alphaα and β\betaβ iff w=uw=uw=u.

The theorem asserts that, under all of the hypotheses above, the main hypothesis implies the conclusion. No relation is required between the witnesses (m,u,α,β,h,l)(m,u,\alpha,\beta,h,l)(m,u,α,β,h,l) of the conclusion and the witnesses (n,vˉ,αˉ,βˉ,gˉ,k)(n,\bar v,\bar\alpha,\bar\beta,\bar g,k)(n,vˉ,αˉ,βˉ​,gˉ​,k) of the hypothesis. For example, mmm may differ from nnn, and α,β\alpha,\betaα,β need not map onto αˉ,βˉ\bar\alpha,\bar\betaαˉ,βˉ​ under π\piπ.

Edge cases.

  • A={1}A=\{1\}A={1}. Then π\piπ is an isomorphism G→G/AG\to G/AG→G/A, and S‾=π(S)\overline{S}=\pi(S)S=π(S) because 1∉S1\notin S1∈/S. The main hypothesis is then exactly the conclusion transported along π\piπ.
  • A=GA=GA=G. This is possible only if GGG is abelian. Then G/AG/AG/A has one element and S‾=∅\overline{S}=\varnothingS=∅, so Cay(G/A,S‾)\mathrm{Cay}(G/A,\overline{S})Cay(G/A,S) 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 2⋅2n−1≥72\cdot 2^n-1\ge 72⋅2n−1≥7 distinct cosets: two cycles of 2n2^n2n vertices each that share only vˉ\bar vvˉ. So it cannot hold, and the theorem is vacuous, whenever [G:A]<7[G:A]<7[G:A]<7. Since [G:A][G:A][G:A] is odd (because ∣G∣|G|∣G∣ is), this means [G:A]∈{1,3,5}[G:A]\in\{1,3,5\}[G:A]∈{1,3,5}.
  • The translating element. gˉ\bar ggˉ​ (respectively hhh) is not stated to be nontrivial, but it cannot be the identity. If it were, both cycles would have the same 2n≥42^n\ge 42n≥4 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 GGG and the commutativity of AAA appear only as hypotheses of the theorem. Normality of AAA is also what makes G/AG/AG/A a group.
Human review
  • Endorsed by Shuze Chen · Nov 12, 2026

    Confirmed by the moderator at approval.

  • Endorsed by burkh4rt · Nov 12, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me