Corollary 1.4: Cayley graphs of finite nilpotent groups satisfy Erdős–Gyárfás
ProvedCayleyErdosGyarfas.nilpotent_cayley_contains_two_power_cycleLet be a finite nilpotent group and let be a generating set of that is closed under inverses, does not contain the identity, and has at least three elements. Then
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.
Finite nilpotent groups include all finite abelian groups and all finite -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 ), 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 . Odd order is not assumed. Generation is Subgroup.closure S = ⊤, is S.ncard, the graph is Mathlib's SimpleGraph.mulCayley S, a cycle is a closed walk with IsCycle, and the bound 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.
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
/-- **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 CayleyErdosGyarfasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be any group, written multiplicatively, whose underlying set is finite. Assume is nilpotent. Let be any subset satisfying all four of the following:
- is closed under inverses: .
- .
- generates as a group: the subgroup generated by (the intersection of all subgroups containing ) is all of .
- . Here is the number of elements of . The cardinality function used returns the junk value on infinite sets, but is finite because is, so this is the genuine count.
The statement asserts that there exist a natural number , an element , and a closed walk from back to in the Cayley graph , such that
Nilpotency. "Nilpotent" means the library definition. Write and define the upper central series by and , so is the centre. Then is nilpotent iff for some . This is the usual notion. It covers every abelian group (including cyclic groups) and every finite -group. For finite groups it is equivalent to being the direct product of its Sylow subgroups.
The graph. is a simple graph (undirected, no loops) with vertex set . Two vertices are adjacent iff and there is some with or (multiplication on the right). Equivalently, and ( or ). Under hypotheses 1 and 2 this reduces exactly to ; the condition then holds automatically. So each vertex has exactly neighbours, namely the elements with . By hypothesis 3, is connected.
The cycle. A closed walk at of length is a sequence of vertices in which is adjacent to for each . Its length is the number of steps. " is a cycle" means three things:
- ;
- the edges are pairwise distinct as unordered pairs;
- the vertices are pairwise distinct, so is the only repeated vertex and it occurs only at the start and the end.
Together these force .
In group terms, the conclusion is equivalent to the following. There are , and with
such that the elements are pairwise distinct. Put simply, contains a cycle, in the usual graph-theoretic sense, whose length is a power of and at least .
Edge cases and remarks.
- The other two clauses imply the clause . Every cycle has length at least , while and are smaller. So the conclusion is equivalent to "some cycle of has length for some ". The possible lengths are , and always holds because the cycle's vertices are distinct.
- The base vertex is only required to exist. Left multiplication by any fixed element of is an automorphism of . So this is equivalent to requiring such a cycle through the identity, or through any prescribed vertex.
- The hypotheses force , since has at least 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 with , or the Klein four-group with its three elements of order .
- The order of may be even or odd. If is odd, no non-identity element is its own inverse, so is even and hypotheses 1, 2 and 4 together force . If is even, may contain elements of order , and is possible.
- need not be a minimal generating set, and there is no upper bound on other than . Nothing requires the cycle to use any particular elements of .
- Hypothesis 2 does not change the graph, because adjacency already requires . It does affect hypothesis 4: the bound counts only non-identity elements.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.