Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Corollary 1.4: Cayley graphs of finite nilpotent groups satisfy Erdős–Gyárfás

Proved
CayleyErdosGyarfas.nilpotent_cayley_contains_two_power_cycle

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

cayley-graphscombinatoricscycleserdos-gyarfasgraph-theorygroup-theory

Let GGG be a finite nilpotent group and let S⊆GS \subseteq GS⊆G be a generating set of GGG that is closed under inverses, does not contain the identity, and has at least three elements. Then

∃ n≥2:Cay⁡(G,S) contains a cycle of length 2n.\exists\, n \ge 2 : \quad \operatorname{Cay}(G,S) \text{ contains a cycle of length } 2^n .∃n≥2:Cay(G,S) contains a cycle of length 2n.

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.

Finite nilpotent groups include all finite abelian groups and all finite ppp-groups. Theorem 1.1 of the same paper gives this conclusion for groups of odd order. Neither hypothesis contains the other: groups of odd order need not be nilpotent (for example C7⋊C3C_7 \rtimes C_3C7​⋊C3​), and nilpotent groups may have even order. The corollary therefore extends the conclusion of Theorem 1.1 to finite nilpotent groups of even order.

Formalization Note Nilpotency is Mathlib's Group.IsNilpotent G: the upper central series reaches GGG. Odd order is not assumed. Generation is Subgroup.closure S = ⊤, ∣S∣|S|∣S∣ is S.ncard, the graph is Mathlib's SimpleGraph.mulCayley S, a cycle is a closed walk with IsCycle, and the bound n≥2n \ge 2n≥2 is kept to match the paper. The statement is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.nilpotent_cayley_contains_two_power_cycle 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

/-- **Corollary 1.4** (arXiv:2611.05060v1, p. 2). If `G` is a finite nilpotent group and
`S` is a symmetric generating set with `1 ∉ S` and `|S| ≥ 3`, then `Cay(G, S)` contains a
simple cycle of length `2 ^ n` for some `n ≥ 2`. -/
theorem nilpotent_cayley_contains_two_power_cycle
    {G : Type*} [Group G] [Finite G] [Group.IsNilpotent G] (S : Set G)
    (hinv : ∀ s ∈ S, s⁻¹ ∈ S)
    (hone : (1 : G) ∉ S)
    (hgen : Subgroup.closure S = ⊤)
    (hcard : 3 ≤ S.ncard) :
    ∃ (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, Corollary 1.4 (proof in §3, p. 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

Let GGG be any group, written multiplicatively, whose underlying set is finite. Assume GGG is nilpotent. Let S⊆GS \subseteq GS⊆G be any subset satisfying all four of the following:

  1. SSS is closed under inverses: s∈S  ⟹  s−1∈Ss \in S \implies s^{-1} \in Ss∈S⟹s−1∈S.
  2. 1∉S1 \notin S1∈/S.
  3. SSS generates GGG as a group: the subgroup ⟨S⟩\langle S \rangle⟨S⟩ generated by SSS (the intersection of all subgroups containing SSS) is all of GGG.
  4. ∣S∣≥3|S| \ge 3∣S∣≥3. Here ∣S∣|S|∣S∣ is the number of elements of SSS. The cardinality function used returns the junk value 000 on infinite sets, but SSS is finite because GGG is, so this is the genuine count.

The statement asserts that there exist a natural number nnn, an element v∈Gv \in Gv∈G, and a closed walk ccc from vvv back to vvv in the Cayley graph Γ=Cay(G,S)\Gamma = \mathrm{Cay}(G,S)Γ=Cay(G,S), such that

n≥2,c is a cycle,length⁡(c)=2n.n \ge 2, \qquad c \text{ is a cycle}, \qquad \operatorname{length}(c) = 2^n .n≥2,c is a cycle,length(c)=2n.

Nilpotency. "Nilpotent" means the library definition. Write [x,y]=xyx−1y−1[x,y] = xyx^{-1}y^{-1}[x,y]=xyx−1y−1 and define the upper central series by Z0={1}Z_0 = \{1\}Z0​={1} and Zi+1={x∈G:[x,y]∈Zi for all y∈G}Z_{i+1} = \{x \in G : [x,y] \in Z_i \text{ for all } y \in G\}Zi+1​={x∈G:[x,y]∈Zi​ for all y∈G}, so Z1Z_1Z1​ is the centre. Then GGG is nilpotent iff ZN=GZ_N = GZN​=G for some N∈NN \in \mathbb{N}N∈N. This is the usual notion. It covers every abelian group (including cyclic groups) and every finite ppp-group. For finite groups it is equivalent to GGG being the direct product of its Sylow subgroups.

The graph. Γ\GammaΓ is a simple graph (undirected, no loops) with vertex set GGG. Two vertices a,ba, ba,b are adjacent iff a≠ba \ne ba=b and there is some g∈Sg \in Sg∈S with b=agb = agb=ag or a=bga = bga=bg (multiplication on the right). Equivalently, a≠ba \ne ba=b and (a−1b∈Sa^{-1}b \in Sa−1b∈S or b−1a∈Sb^{-1}a \in Sb−1a∈S). Under hypotheses 1 and 2 this reduces exactly to a−1b∈Sa^{-1}b \in Sa−1b∈S; the condition a≠ba \ne ba=b then holds automatically. So each vertex aaa has exactly ∣S∣|S|∣S∣ neighbours, namely the elements asasas with s∈Ss \in Ss∈S. By hypothesis 3, Γ\GammaΓ is connected.

The cycle. A closed walk ccc at vvv of length kkk is a sequence of vertices v=x0,x1,…,xk=vv = x_0, x_1, \ldots, x_k = vv=x0​,x1​,…,xk​=v in which xi−1x_{i-1}xi−1​ is adjacent to xix_ixi​ for each 1≤i≤k1 \le i \le k1≤i≤k. Its length kkk is the number of steps. "ccc is a cycle" means three things:

  • k≥1k \ge 1k≥1;
  • the kkk edges {xi−1,xi}\{x_{i-1}, x_i\}{xi−1​,xi​} are pairwise distinct as unordered pairs;
  • the vertices x1,…,xkx_1, \ldots, x_kx1​,…,xk​ are pairwise distinct, so vvv is the only repeated vertex and it occurs only at the start and the end.

Together these force k≥3k \ge 3k≥3.

In group terms, the conclusion is equivalent to the following. There are n≥2n \ge 2n≥2, v∈Gv \in Gv∈G and s1,…,s2n∈Ss_1, \ldots, s_{2^n} \in Ss1​,…,s2n​∈S with

s1s2⋯s2n=1,s_1 s_2 \cdots s_{2^n} = 1,s1​s2​⋯s2n​=1,

such that the 2n2^n2n elements v, vs1, vs1s2, …, vs1⋯s2n−1v,\ v s_1,\ v s_1 s_2,\ \ldots,\ v s_1 \cdots s_{2^n-1}v, vs1​, vs1​s2​, …, vs1​⋯s2n−1​ are pairwise distinct. Put simply, Γ\GammaΓ contains a cycle, in the usual graph-theoretic sense, whose length is a power of 222 and at least 444.

Edge cases and remarks.

  • The other two clauses imply the clause n≥2n \ge 2n≥2. Every cycle has length at least 333, while 20=12^0 = 120=1 and 21=22^1 = 221=2 are smaller. So the conclusion is equivalent to "some cycle of Γ\GammaΓ has length 2n2^n2n for some n∈Nn \in \mathbb{N}n∈N". The possible lengths are 4,8,16,…4, 8, 16, \ldots4,8,16,…, and 2n≤∣G∣2^n \le |G|2n≤∣G∣ always holds because the cycle's 2n2^n2n vertices are distinct.
  • The base vertex vvv is only required to exist. Left multiplication by any fixed element of GGG is an automorphism of Γ\GammaΓ. So this is equivalent to requiring such a cycle through the identity, or through any prescribed vertex.
  • The hypotheses force ∣G∣≥4|G| \ge 4∣G∣≥4, since S⊆G∖{1}S \subseteq G \setminus \{1\}S⊆G∖{1} has at least 333 elements, and so they exclude the trivial group. They can all be satisfied at once. For example, take any abelian group of order at least 444 with S=G∖{1}S = G \setminus \{1\}S=G∖{1}, or the Klein four-group with SSS its three elements of order 222.
  • The order of GGG may be even or odd. If ∣G∣|G|∣G∣ is odd, no non-identity element is its own inverse, so ∣S∣|S|∣S∣ is even and hypotheses 1, 2 and 4 together force ∣S∣≥4|S| \ge 4∣S∣≥4. If ∣G∣|G|∣G∣ is even, SSS may contain elements of order 222, and ∣S∣=3|S| = 3∣S∣=3 is possible.
  • SSS need not be a minimal generating set, and there is no upper bound on ∣S∣|S|∣S∣ other than ∣S∣≤∣G∣−1|S| \le |G| - 1∣S∣≤∣G∣−1. Nothing requires the cycle to use any particular elements of SSS.
  • Hypothesis 2 does not change the graph, because adjacency already requires a≠ba \ne ba=b. It does affect hypothesis 4: the bound ∣S∣≥3|S| \ge 3∣S∣≥3 counts only non-identity elements.
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