Lemma 1.3: power-of-two cycles lift through normal 2-subgroups
ProvedCayleyErdosGyarfas.two_power_cycle_lifts_of_normal_two_subgroupLet be a finite group and let be a generating set of that is closed under inverses and does not contain the identity. Let be a normal -subgroup, so that every element of has order a power of , and write
for the image of in with the identity coset removed. Then
The exponents and 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.
No parity or size hypothesis is imposed on or . The paper proves Corollary 1.4 from this lemma, Theorem 1.1 applied to the odd-order quotient by the Sylow -subgroup, and the first two paragraphs of the proof of this lemma, which treat generators lying in and distinct generators with the same image in .
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.
import Mathlib.Combinatorics.SimpleGraph.Cayley import Mathlib.Combinatorics.SimpleGraph.Paths import Mathlib.GroupTheory.Nilpotent import Mathlib.GroupTheory.PGroup import Mathlib.Data.Set.Card
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 CayleyErdosGyarfasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
For every finite group (written multiplicatively), every subset and every subgroup such that
- is closed under inverses: ;
- the identity of is not in ;
- generates : the subgroup generated by is all of ;
- is normal in , so is a group with , whose identity element is the coset ;
- is a -group: each satisfies for some depending on . Since is finite, this is equivalent to for some , and is allowed;
- for some natural number and some vertex there is a cycle of length based at in the Cayley graph . Here , , is the quotient map and
The identity is removed from the image ; itself is not changed.
the statement asserts that for some natural number and some vertex there is a cycle of length based at in the Cayley graph . In outline, under 1–5:
Cayley graphs. For a group and a subset , is the simple graph (undirected, no loops) with vertex set and
That is, or for some , so generators act by right multiplication. The construction makes the relation symmetric and excludes loops whether or not is closed under inverses or contains the identity. In particular . Under 1 and 2, in exactly when . In , two cosets are adjacent iff or for some . By 1 and the normality of , these two alternatives are equivalent.
Cycles. A cycle of length based at a vertex is a closed walk with for , such that:
- ;
- the edges are pairwise distinct;
- are pairwise distinct.
Equivalently, and are pairwise distinct. The length is the number of edges traversed. Every cycle has length at least , so the conditions and exclude only the lengths and , which no cycle has. Hypothesis 6 therefore says exactly that contains a cycle whose length is a power of . The conclusion says exactly that contains such a cycle (possible lengths ).
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 for both exponents, but each is bound separately; here they are called and . Nothing requires or . Nothing requires to map the cycle in onto the given cycle in , and no other relation between the two cycles is asserted.
Absent assumptions.
- There is no parity or size assumption on , or , and none on beyond its being a power of .
- need not be nontrivial, proper, or a Sylow -subgroup.
- No relation between and is assumed. Elements of may lie in , in which case they contribute nothing to , and distinct elements of may have the same image in .
- There is no nilpotency, solvability, commutativity or other structural assumption on or .
- Nothing is assumed about beyond its definition from and .
Edge cases.
- : is an isomorphism with (nothing is removed, since ). So is a graph isomorphism , and hypothesis 6 and the conclusion say the same thing up to this isomorphism.
- (allowed exactly when is a power of ): has one element, so has no edges and no cycles. Hypothesis 6 fails and the statement is vacuous for this . More generally, hypothesis 6 forces .
- : then and , so the statement is vacuous.
- All the hypotheses can hold at once with nontrivial. Take cyclic of order , and . Then is a -cycle, so hypothesis 6 holds with .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.