Symmetric figure-eights in Cayley graphs of noncyclic groups of odd order
ProvedCayleyErdosGyarfas.noncyclic_odd_order_symmetric_figure_eightLet be a finite noncyclic group of odd order and let be a generating set of that is closed under inverses and does not contain the identity. Then
that is, two cycles of a common length with that share exactly one vertex, one of which is the left translate of the other cycle for some , up to the choice of starting vertex. 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.
The paper announces this after Theorem 1.1 (every Cayley graph of a noncyclic group of odd order contains a symmetric figure-eight) and proves it as the claim inside the proof of Theorem 1.1. It strengthens Theorem 1.1 for noncyclic groups. The restriction to noncyclic groups is needed: for , has too few vertices for two such cycles.
Formalization Note The paper's claim assumes ; that hypothesis is omitted because the others imply . In a group of odd order no nonidentity element is its own inverse, so is a union of pairs with ; the empty set generates the trivial group and a single pair generates , both cyclic, so contains at least two pairs. Noncyclicity is ¬ IsCyclic G. The statement is identical, up to the spelling of the namespace, to CayleyErdősGyárfás.noncyclic_odd_order_symmetric_figure_eight in the Challenge of Palomar entry PALOMAR-2026-11-04-000015, where it is proved.
import Definitions.Def_CayleyErdosGyarfas_HasSymmetricFigureEight import Mathlib.GroupTheory.Nilpotent import Mathlib.GroupTheory.PGroup import Mathlib.Data.Set.Card
namespace CayleyErdosGyarfas
/-- **Noncyclic strengthening of Theorem 1.1** (arXiv:2611.05060v1, p. 1 after
Theorem 1.1, and the claim in the proof of Theorem 1.1 on p. 4). If `G` is a finite
noncyclic group of odd order and `S` is a symmetric generating set with `1 ∉ S`, then
`Cay(G, S)` contains a symmetric figure-eight. -/
theorem noncyclic_odd_order_symmetric_figure_eight
{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 = ⊤)
(hncyclic : ¬ IsCyclic G) : HasSymmetricFigureEight S := by sorry
end CayleyErdosGyarfasRead-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be an arbitrary finite group, written multiplicatively with identity , and let be an arbitrary subset. Exactly these hypotheses are assumed:
- is odd.
- is closed under inverses: .
- .
- generates , meaning the subgroup generated by is all of .
- is not cyclic: there is no with .
Nothing else is assumed. There is no explicit lower bound on , no minimality or independence condition on , and no further condition on (for example abelian, nilpotent, or of prime-power order). The hypotheses can all hold at once, for example with and ; is the smallest possible order. Together they force to be even with . The reason is that a group of odd order has no element of order , so splits into pairs with . Then would make trivial, and would make cyclic.
Let be the Cayley graph used here, in which generators act on the right. It is the simple graph with vertex set in which are adjacent if and only if
that is, and ( or ). By construction this relation is symmetric and has no loops, whether or not hypotheses 2 and 3 hold. Under hypotheses 2 and 3 it is equivalent to . So each is adjacent to exactly the distinct vertices with . Every left multiplication preserves adjacency, since .
Conclusion. There exist a natural number , a vertex , and two closed walks and in , each starting and ending at , such that all of the conditions below hold. Write . Write the vertex sequence of as and that of as . Consecutive terms are adjacent in .
- Length: , so . Both and have exactly edges, with the same for both.
- Both are cycles: each is a nonempty closed walk that repeats no edge, and its vertices after the starting one (, respectively ) are pairwise distinct. So is the only repeated vertex, and it occurs only at the start and the end. Since , this amounts to the following: are distinct elements with for (where ), and likewise for the .
- Translation and rotation: there exist and such that rotating the list to the left by positions gives exactly the list . The number comes from the definition of "is a cyclic rotation of". The rotation is by , so one may take , and then
The translation is left multiplication by , applied to the vertices of ; equivalently, applied to the vertices of . The two lists leave out the initial copy of but keep the final one, so they are the cyclic vertex sequences of the two cycles. Only cyclic shifts are allowed, not reversals, so and must run in the same direction. This can always be arranged by reversing , since the reverse is again a cycle at with the same vertices. Equivalently, the cyclic step sequences and , whose entries lie in , are cyclic shifts of each other. No explicit condition is placed on .
- They meet only at : for every ,
The direction "" holds automatically. The content is . It follows that:
- the two cycles share no edge;
- together they use distinct elements of , so ;
- , because with the two vertex sets would coincide. Hence has no fixed points, and in particular .
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.