Depth of the in-tree of $s$ under $q \mapsto q s q^{-1}$ on $n$ -cycles

Fix an $n$ -cycle $s$ and map every $n$ -cycle $q$ to its conjugate $D(q) = q s q^{-1}$ , which is the same as reading the one-line word $(q(0), \ldots, q(n-1))$ back as a cycle. Iterating $D$ turns the $(n-1)!$ $n$ -cycles into a functional graph. Its only fixed point is $s$ , and the cycles that eventually reach $s$ form a tree feeding into it. How deep is that tree?

Exactly $\varphi(n)$ cycles map directly onto $s$ , and the tree stays shallow - depth 1 - unless $8 \mid n$ or $p^2 \mid n$ for an odd prime $p$ , which is the Hull-Dobell threshold for the existence of a full-period non-translation affine map on $\mathbb{Z}/n$ . Past it the depth is $p^{e-1}$ for $n = p^e$ with $p$ odd, $2^{e-1} - 1$ for $n = 2^e$ , and for general $n$ the largest of these over the prime powers dividing $n$ .

Result: Proved(see note)
Status: Candidate (review pending)
AI contribution: AI-discovered
Method: Argument
Field: Permutation combinatorics / functional graphs
Posed by: Frédéric Lefebvre-Naré
Year posed: 2006
Years open: 20y
Solved: 2026-07-24
Model: Claude FABLE 5
Vendor: Anthropic
Collaborators: —
Verification: Unreviewed
Publication: Announced
Significance: 3 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What was actually shown

Opus 4.8 constructed a branch of the stated depth, giving a lower bound, and believed it had a matching upper bound; that proof was wrong and the statement stayed a conjecture. FABLE 5 later proved it. In the author's summary of the method: "The proof turns conjugation, near $s$ , into base- $p$ arithmetic." A cycle near the fixed point splits into a coarse base permutation and a vector of carries in $\mathbb{Z}/p$ , $D$ acts on the carries by the carrying of ordinary base- $p$ addition, and the depth comes out as the nilpotency length of a shift difference - exactly that for odd $p$ , one less for $p = 2$ . The single missing carry that odd primes absorb and $2$ cannot is what produces the two-branch answer.

A companion survey paper covers the rest of the graph: the other periodic orbits, congruences on basin sizes, and a cyclic-sieving count. The depth theorem is the substantive part.

What the AI did

Claude Opus 4.8 in a first phase, then Claude FABLE 5, which obtained the result, did 99.9% of the research, in manual mode (that is, with more than 50 human prompts by an amateur, and step-by-step approvals). OpenAI's GPT-5.5 and others were used to proofread; all corrections after human and AI proofreading were made by Claude. Diagrams were made by Claude under human instructions.

Verification

Not refereed, not formalised, and the paper says so itself on page one: "An end-to-end verification of the assembled whole, and human peer review, remain to be done; the argument should be examined critically before being relied upon." The author, an amateur, states plainly that he cannot check the proof. So this stays Unreviewed and Candidate.

The claim is unusually checkable, though, and this site checked it independently, from the statement rather than from the author's code. Enumerating every $n$ -cycle and building the whole functional graph for $n \le 10$ : $|D^{-1}(s)| = \varphi(n)$ at every $n$ , and the depth matches the formula at every $n$ , including both nontrivial cases in range, depth 3 at $n = 8$ and at $n = 9$ . Walking the tree backwards, which costs $n$ checks per node instead of $(n-1)!$ , reaches depth 7 at $n = 16$ , 5 at $n = 25$ , 3 at $n = 18$ , and 9 at $n = 27$ across 472,392 nodes - every one the predicted value. The Hull-Dobell mechanism was checked directly: preimages of a translation are exactly the affine maps with that multiplier, Hull-Dobell decides which are $n$ -cycles, and the threshold predicts a nonempty second level exactly, no exceptions at $n = 6, 8, 9, 12, 16, 18, 25, 27$ . The survey's basin-count sequence recounts to 1, 2, 2, 6, 7, 18, 17, 29 for $n = 3 \ldots 10$ , matching, and OEIS returns nothing for it.

What none of that touches is the proof, which is the novelty: a formula confirmed at every $n$ reachable is not a theorem for all $n$ .

Sources

Submitted by StormyRaven240 on 17 Aug 2026

Depth of the in-tree of sss under q↦qsq−1q \mapsto q s q^{-1}q↦qsq−1 on nnn-cycles

What was actually shown

What the AI did

Verification

Sources

Discussion

Depth of the in-tree of $s$ under $q \mapsto q s q^{-1}$ on $n$ -cycles