Cyclic shift's cubic-coefficient conjecture for deranged strategies

Cyclic shifting maximizes the cubic coefficient among all deranged strategies

Problem: MathDB #369086, Aurora Hiveley, Experimenting with Permutation Wordle, Journal of Integer Sequences 29 (2026), Article 26.1.7, Conjecture 6; originally Conjecture 4.2 in arXiv:2506.23452v2.

Status: The intended optimization statement is proved for every deranged strategy. The printed strict inequality requires one unavoidable correction: coherent rightward and coherent leftward cyclic shifting are distinct strategies with identical performance. The source itself explicitly recognizes both directions, so this elementary reflection is not claimed as new. The substantive result is the complete universal optimality theorem and the classification of all equality cases, extending the source's theorem for inductively constructed strategies.

Hiveley's subsequent Repetition in Permutation Wordle, Discrete Mathematics Letters 17 (2026), 93–100, DOI 10.47443/dml.2026.112, studies when strategies repeat incorrect information. Although its introduction informally describes three-guess optimality, the earlier quantitative theorem concerns inductively constructed competitors, and the subsequent paper does not prove the universal cubic-coefficient result established here.

Theorem

Let $S=(s_1,\ldots,s_n)$ be any strategy for permutation Wordle such that $s_m$ is a derangement of $[m]$ whenever $m\ge 2$. Let $f_S(x)$ count secret permutations by the number of guesses used. For every $n\ge 3$,

$$[x^3]f_S(x) \le A(n,2) =3^n-(n+1)2^n+\binom{n+1}{2},$$

where $A(n,2)$ is the Eulerian number. If $n\ge4$, equality holds if and only if either

$$s_m(i)=i+1\pmod m \quad\text{for every }2\le m\le n,$$

or

$$s_m(i)=i-1\pmod m \quad\text{for every }2\le m\le n.$$

The two maximizing strategies are therefore exactly coherent rightward and coherent leftward cyclic shift. In particular, the rightward strategy is strictly better than every deranged strategy other than itself and its reflected leftward counterpart.

Throughout, cyclic expressions on $[m]=\{1,\ldots,m\}$ are interpreted modulo $m$ with representatives in $[m]$.

1. Reduction to deranged secrets

The first guess is the identity permutation. If its incorrect positions form a set $U\subseteq[n]$ of size $m$, the secret restricted to $U$, after increasing-order relabeling, is a derangement of $[m]$. The strategy acts on these positions through the same components $s_2,\ldots,s_m$ and leaves the other positions fixed.

Write $C_m(S)$ for the number of derangements of $[m]$ whose games end on the third guess. A game with precisely two initially incorrect positions ends on the second guess, because $s_2=(2,1)$. Consequently $C_2(S)=0$ and

$$[x^3]f_S(x) =\sum_{m=3}^{n}\binom{n}{m}C_m(S). \tag{1}$$

The sum deliberately begins at $m=3$: the bounds below do not hold at $m=2$.

2. Candidate secrets are indexed by subsets

Fix $m\ge3$ and consider a deranged secret on $[m]$. Since every position of the first guess is incorrect, the second guess is

$$\delta=s_m^{-1}.$$

Suppose that the set of incorrect positions after the second guess is

$$I=\{i_1<\cdots<i_r\}\subseteq[m].$$

A game ending on its third guess must have $r\ge2$. For each such subset $I$, there is exactly one possible third guess, namely the permutation $\pi_I$ defined by

$$\begin{aligned} \pi_I(j)&=\delta(j), &&j\notin I,\\ \pi_I\bigl(i_{s_r(a)}\bigr)&=\delta(i_a), &&1\le a\le r. \end{aligned} \tag{2}$$

Since $s_r$ is a derangement and $\delta$ is injective, the positions where $\pi_I$ differs from $\delta$ are exactly $I$. Hence $\pi_I$ is the secret of a game ending on the third guess if and only if $\pi_I$ is also a derangement relative to the first guess.

Call $I$ bad when $\pi_I$ has a fixed point. Equation (2) shows that this happens precisely when, for some $1\le a\le r$,

$$s_m\bigl(i_{s_r(a)}\bigr)=i_a. \tag{3}$$

In graph language, a subset is bad when a directed edge of $s_m$ runs opposite to a directed edge of the permutation $s_r$ acting on the increasing-order ranks in $I$.

There are $2^m-m-1$ subsets of size at least two. Therefore

$$C_m(S)=2^m-m-1-B_m(S), \tag{4}$$

where $B_m(S)$ denotes the number of bad subsets.

3. At least $m$ subsets are bad

Let $t$ be the number of two-cycles in the disjoint-cycle decomposition of $s_m$. Because $s_2$ swaps its two positions, every unordered pair

$$\{i,s_m(i)\}$$

is bad. A cycle of length at least three contributes one distinct pair for each of its vertices, while a two-cycle contributes one pair for both vertices. Thus there are exactly

$$m-t \tag{5}$$

bad two-element subsets.

Every three-element subset containing both vertices of a two-cycle is also bad. Indeed, either possible derangement $s_3$ is a directed three-cycle, so one of its directed edges, in the appropriate reverse direction, joins those two vertices. Since $s_m$ contains both directed orientations of that edge, condition (3) holds.

For each of the $t$ two-cycles there are $m-2$ such triples. No triple can contain two distinct two-cycles, so all these triples are different. Hence

$$B_m(S) \ge (m-t)+t(m-2) =m+t(m-3) \ge m. \tag{6}$$

Combining (4) and (6) proves the universal local bound

$$C_m(S)\le 2^m-2m-1 \qquad(m\ge3). \tag{7}$$

If $m\ge4$ and $s_m$ contains any two-cycle, inequality (7) is strict.

4. Evaluation of the global bound

Substituting (7) into (1) gives

$$\begin{aligned} [x^3]f_S(x) &\le \sum_{m=3}^n\binom{n}{m}\bigl(2^m-2m-1\bigr)\\ &= 3^n-(n+1)2^n+n+\binom n2\\ &= 3^n-(n+1)2^n+\binom{n+1}{2}\\ &=A(n,2). \end{aligned} \tag{8}$$

For the rightward cyclic strategy, write $c_m(i)=i+1\pmod m$. A two-element subset is bad exactly when its elements are consecutive in cyclic order, giving exactly $m$ bad pairs. No subset of size $r\ge3$ is bad: condition (3) would say that the immediate cyclic successor of some element of $[m]$ is simultaneously its predecessor among the $r$ selected elements, which is impossible when at least three elements are selected.

Therefore

$$C_m(CS)=2^m-2m-1$$

for every $m\ge3$, and equality holds in (8). The same argument with the cyclic order reversed applies to coherent leftward shifting.

5. Classification of all equality cases

Assume $n\ge4$ and equality holds in (8). All binomial weights in (1) are positive, so equality must hold separately in (7) for every $3\le m\le n$.

The component $s_3$ is necessarily one of the two directed three-cycles. First suppose

$$s_3=(2,3,1).$$

Fix any $m\ge4$. By (6), equality forces $s_m$ to have no two-cycles. Its $m$ bad pairs already exhaust the permissible $m$ bad subsets, so no triple may be bad.

Consider a directed edge $i\mapsto j=s_m(i)$. If $j$ is not the immediate cyclic successor of $i$ in

$$1,2,\ldots,m,1,$$

there exists a vertex $k$ strictly between $i$ and $j$ in that cyclic order. Within the triple $\{i,k,j\}$, the vertex $j$ is the cyclic predecessor of $i$. Since $s_3$ acts by cyclic succession on the increasing-order ranks, this is exactly condition (3). The triple would therefore be bad, a contradiction.

Thus $j=i+1\pmod m$ for every $i$, and consequently

$$s_m=(2,3,\ldots,m,1).$$

This argument applies independently to every $m\ge4$. Together with $s_2=(2,1)$ and the prescribed choice of $s_3$, it proves that the entire strategy is coherent rightward cyclic shift.

If instead

$$s_3=(3,1,2),$$

reverse the cyclic order in the same argument. Every edge of every $s_m$ must then point to the immediate cyclic predecessor, so the whole strategy is coherent leftward cyclic shift.

Finally, reflecting positions and values by $i\mapsto n+1-i$ conjugates the entire rightward game to the leftward game. In particular, their complete generating functions agree:

$$f_{\mathrm{right}}(x)=f_{\mathrm{left}}(x).$$

The source already acknowledges the leftward analogue, so this reflection is an inherent correction to its printed strict comparison, not a new counterexample. The new content is the proof that no other deranged strategy can match or exceed cyclic shifting at the three-guess horizon.