Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 1.3: power-of-two cycles lift through normal 2-subgroups

Proved
CayleyErdosGyarfas.two_power_cycle_lifts_of_normal_two_subgroup

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

cayley-graphscombinatoricscycleserdos-gyarfasgraph-theorygroup-theory

Let GGG be a finite group 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 P⊴GP \trianglelefteq GP⊴G be a normal 222-subgroup, so that every element of PPP has order a power of 222, and write

S‾={sP:s∈S}∖{P}⊆G/P.\overline{S} = \{ sP : s \in S \} \setminus \{ P \} \subseteq G/P .S={sP:s∈S}∖{P}⊆G/P.

for the image of SSS in G/PG/PG/P with the identity coset removed. Then

Cay⁡(G/P,S‾) has a cycle of length 2n for some n≥2  ⟹  Cay⁡(G,S) has a cycle of length 2m for some m≥2.\operatorname{Cay}(G/P, \overline{S}) \text{ has a cycle of length } 2^n \text{ for some } n \ge 2 \;\Longrightarrow\; \operatorname{Cay}(G,S) \text{ has a cycle of length } 2^m \text{ for some } m \ge 2 .Cay(G/P,S) has a cycle of length 2n for some n≥2⟹Cay(G,S) has a cycle of length 2m for some m≥2.

The exponents nnn and mmm 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.

No parity or size hypothesis is imposed on GGG or SSS. The paper proves Corollary 1.4 from this lemma, Theorem 1.1 applied to the odd-order quotient by the Sylow 222-subgroup, and the first two paragraphs of the proof of this lemma, which treat generators lying in PPP and distinct generators with the same image in G/PG/PG/P.

Formalization Note The kernel hypotheses are [P.Normal] and IsPGroup 2 P, and the quotient generating set is (QuotientGroup.mk (s := P)) '' S \ {1}. The statement is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.two_power_cycle_lifts_of_normal_two_subgroup in the Challenge of Palomar entry PALOMAR-2026-11-04-000015, where it is proved.

Preamble
import Mathlib.Combinatorics.SimpleGraph.Cayley
import Mathlib.Combinatorics.SimpleGraph.Paths
import Mathlib.GroupTheory.Nilpotent
import Mathlib.GroupTheory.PGroup
import Mathlib.Data.Set.Card
Formal statement
namespace CayleyErdosGyarfas

/-- **Lemma 1.3** (arXiv:2611.05060v1, p. 2). Let `G = ⟨S⟩` be a finite group, with
`S` symmetric and `1 ∉ S`, and let `P` be a normal 2-subgroup. Put
`S̄ = {sP : s ∈ S} \ {P}`. If `Cay(G/P, S̄)` contains a simple cycle of length `2 ^ n`
with `n ≥ 2`, then `Cay(G, S)` contains a simple cycle of length `2 ^ m` with `m ≥ 2`;
the two exponents may differ. -/
theorem two_power_cycle_lifts_of_normal_two_subgroup
    {G : Type*} [Group G] [Finite G] (S : Set G)
    (hinv : ∀ s ∈ S, s⁻¹ ∈ S)
    (hone : (1 : G) ∉ S)
    (hgen : Subgroup.closure S = ⊤)
    (P : Subgroup G) [P.Normal] (hP : IsPGroup 2 P)
    (hcycle : ∃ (n : ℕ) (v : G ⧸ P)
      (c : (SimpleGraph.mulCayley
        ((QuotientGroup.mk (s := P)) '' S \ {1})).Walk v v),
      2 ≤ n ∧ c.IsCycle ∧ c.length = 2 ^ n) :
    ∃ (n : ℕ) (v : G) (c : (SimpleGraph.mulCayley S).Walk v v),
      2 ≤ n ∧ c.IsCycle ∧ c.length = 2 ^ n := 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.3 (proof in §3, pp. 5–6); standing conventions of §1.1, p. 2; power-of-two length in the sense of §1, p. 1 (a simple cycle of length 2^n, n ≥ 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

For every finite group GGG (written multiplicatively), every subset S⊆GS \subseteq GS⊆G and every subgroup P≤GP \le GP≤G such that

  1. SSS is closed under inverses: s∈S  ⟹  s−1∈Ss \in S \implies s^{-1} \in Ss∈S⟹s−1∈S;
  2. the identity 111 of GGG is not in SSS;
  3. SSS generates GGG: the subgroup generated by SSS is all of GGG;
  4. PPP is normal in GGG, so G/PG/PG/P is a group with (xP)(yP)=xyP(xP)(yP) = xyP(xP)(yP)=xyP, whose identity element is the coset PPP;
  5. PPP is a 222-group: each g∈Pg \in Pg∈P satisfies g2k=1g^{2^k} = 1g2k=1 for some k∈Nk \in \mathbb{N}k∈N depending on ggg. Since GGG is finite, this is equivalent to ∣P∣=2a|P| = 2^a∣P∣=2a for some a≥0a \ge 0a≥0, and P={1}P = \{1\}P={1} is allowed;
  6. for some natural number n≥2n \ge 2n≥2 and some vertex v∈G/Pv \in G/Pv∈G/P there is a cycle of length 2n2^n2n based at vvv in the Cayley graph Cay(G/P,Sˉ)\mathrm{Cay}(G/P, \bar S)Cay(G/P,Sˉ). Here π:G→G/P\pi : G \to G/Pπ:G→G/P, g↦gPg \mapsto gPg↦gP, is the quotient map and
Sˉ  =  π(S)∖{1G/P}  =  { sP:s∈S }∖{P}  =  { sP:s∈S, s∉P }.\bar S \;=\; \pi(S) \setminus \{1_{G/P}\} \;=\; \{\, sP : s \in S \,\} \setminus \{P\} \;=\; \{\, sP : s \in S,\ s \notin P \,\}.Sˉ=π(S)∖{1G/P​}={sP:s∈S}∖{P}={sP:s∈S, s∈/P}.

The identity is removed from the image π(S)\pi(S)π(S); SSS itself is not changed.

the statement asserts that for some natural number m≥2m \ge 2m≥2 and some vertex w∈Gw \in Gw∈G there is a cycle of length 2m2^m2m based at www in the Cayley graph Cay(G,S)\mathrm{Cay}(G, S)Cay(G,S). In outline, under 1–5:

[∃ n≥2: Cay(G/P,Sˉ) has a cycle of length 2n]  ⟹  [∃ m≥2: Cay(G,S) has a cycle of length 2m].\Bigl[\exists\, n \ge 2:\ \mathrm{Cay}(G/P,\bar S)\ \text{has a cycle of length}\ 2^n\Bigr] \;\Longrightarrow\; \Bigl[\exists\, m \ge 2:\ \mathrm{Cay}(G,S)\ \text{has a cycle of length}\ 2^m\Bigr].[∃n≥2: Cay(G/P,Sˉ) has a cycle of length 2n]⟹[∃m≥2: Cay(G,S) has a cycle of length 2m].

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 and

x∼y  ⟺  x≠y  and  (x−1y∈T  or  y−1x∈T).x \sim y \iff x \ne y \ \text{ and } \ \bigl(x^{-1}y \in T \ \text{ or } \ y^{-1}x \in T\bigr).x∼y⟺x=y  and  (x−1y∈T  or  y−1x∈T).

That is, y=xty = xty=xt or x=ytx = ytx=yt for some t∈Tt \in Tt∈T, so generators act by right multiplication. The construction makes the relation symmetric and excludes loops whether or not TTT is closed under inverses or contains the identity. In particular Cay(G/P,Sˉ)=Cay(G/P,π(S))\mathrm{Cay}(G/P,\bar S) = \mathrm{Cay}(G/P,\pi(S))Cay(G/P,Sˉ)=Cay(G/P,π(S)). Under 1 and 2, x∼yx \sim yx∼y in Cay(G,S)\mathrm{Cay}(G,S)Cay(G,S) exactly when x−1y∈Sx^{-1}y \in Sx−1y∈S. In Cay(G/P,Sˉ)\mathrm{Cay}(G/P,\bar S)Cay(G/P,Sˉ), two cosets xP≠yPxP \ne yPxP=yP are adjacent iff x−1y∈sPx^{-1}y \in sPx−1y∈sP or y−1x∈sPy^{-1}x \in sPy−1x∈sP for some s∈Ss \in Ss∈S. By 1 and the normality of PPP, these two alternatives are equivalent.

Cycles. A cycle of length LLL based at a vertex uuu is a closed walk u=x0,x1,…,xL=uu = x_0, x_1, \dots, x_L = uu=x0​,x1​,…,xL​=u with xi−1∼xix_{i-1} \sim x_ixi−1​∼xi​ for 1≤i≤L1 \le i \le L1≤i≤L, such that:

  • L≥1L \ge 1L≥1;
  • the LLL edges {xi−1,xi}\{x_{i-1}, x_i\}{xi−1​,xi​} are pairwise distinct;
  • x1,…,xLx_1, \dots, x_Lx1​,…,xL​ are pairwise distinct.

Equivalently, L≥3L \ge 3L≥3 and x0,…,xL−1x_0, \dots, x_{L-1}x0​,…,xL−1​ are pairwise distinct. The length is the number of edges traversed. Every cycle has length at least 333, so the conditions n≥2n \ge 2n≥2 and m≥2m \ge 2m≥2 exclude only the lengths 20=12^0 = 120=1 and 21=22^1 = 221=2, which no cycle has. Hypothesis 6 therefore says exactly that Cay(G/P,Sˉ)\mathrm{Cay}(G/P,\bar S)Cay(G/P,Sˉ) contains a cycle whose length is a power of 222. The conclusion says exactly that Cay(G,S)\mathrm{Cay}(G,S)Cay(G,S) contains such a cycle (possible lengths 4,8,16,…4, 8, 16, \dots4,8,16,…).

Quantifier structure. The exponent, base vertex and cycle in the conclusion are existentially quantified independently of those in hypothesis 6. The code uses the letter nnn for both exponents, but each is bound separately; here they are called nnn and mmm. Nothing requires m=nm = nm=n or π(w)=v\pi(w) = vπ(w)=v. Nothing requires π\piπ to map the cycle in Cay(G,S)\mathrm{Cay}(G,S)Cay(G,S) onto the given cycle in Cay(G/P,Sˉ)\mathrm{Cay}(G/P,\bar S)Cay(G/P,Sˉ), and no other relation between the two cycles is asserted.

Absent assumptions.

  • There is no parity or size assumption on ∣G∣|G|∣G∣, ∣S∣|S|∣S∣ or ∣G/P∣|G/P|∣G/P∣, and none on ∣P∣|P|∣P∣ beyond its being a power of 222.
  • PPP need not be nontrivial, proper, or a Sylow 222-subgroup.
  • No relation between SSS and PPP is assumed. Elements of SSS may lie in PPP, in which case they contribute nothing to Sˉ\bar SSˉ, and distinct elements of SSS may have the same image in G/PG/PG/P.
  • There is no nilpotency, solvability, commutativity or other structural assumption on GGG or G/PG/PG/P.
  • Nothing is assumed about Sˉ\bar SSˉ beyond its definition from SSS and PPP.

Edge cases.

  • P={1}P = \{1\}P={1}: π\piπ is an isomorphism G→G/PG \to G/PG→G/P with π(S)=Sˉ\pi(S) = \bar Sπ(S)=Sˉ (nothing is removed, since 1∉S1 \notin S1∈/S). So π\piπ is a graph isomorphism Cay(G,S)≅Cay(G/P,Sˉ)\mathrm{Cay}(G,S) \cong \mathrm{Cay}(G/P,\bar S)Cay(G,S)≅Cay(G/P,Sˉ), and hypothesis 6 and the conclusion say the same thing up to this isomorphism.
  • P=GP = GP=G (allowed exactly when ∣G∣|G|∣G∣ is a power of 222): G/PG/PG/P has one element, so Cay(G/P,Sˉ)\mathrm{Cay}(G/P,\bar S)Cay(G/P,Sˉ) has no edges and no cycles. Hypothesis 6 fails and the statement is vacuous for this PPP. More generally, hypothesis 6 forces ∣G/P∣≥2n≥4|G/P| \ge 2^n \ge 4∣G/P∣≥2n≥4.
  • G={1}G = \{1\}G={1}: then S=∅S = \varnothingS=∅ and P=GP = GP=G, so the statement is vacuous.
  • All the hypotheses can hold at once with PPP nontrivial. Take G=⟨g⟩G = \langle g \rangleG=⟨g⟩ cyclic of order 888, S={g,g−1}S = \{g, g^{-1}\}S={g,g−1} and P={1,g4}P = \{1, g^4\}P={1,g4}. Then Cay(G/P,Sˉ)\mathrm{Cay}(G/P,\bar S)Cay(G/P,Sˉ) is a 444-cycle, so hypothesis 6 holds with n=2n = 2n=2.
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