Reading a Paper 2026, 08 - Repetition in Permutation Wordle

I found a paper of the type that I really admire in spirit: Rigorously looking into something plucked from daily (sort of) life. It concerns itself with a Wordle variation and the strategies in solving it, and while I'm more of a crosswords person myself these days, I like being able to centering actual research acumen around something that doesn't require anything than some paper and a few good ideas. https://arxiv.org/abs/2601.05971v1

Permutation Wordle is a hypothesized game that functions like World, though given all correct letters. It remains then to figure out the permutation, reducing the problem to a 5-letter anagram. There exists a conjecture that a "cyclic shift" strategy would be optimal. This strategy was proven optimal for games ending in exactly three guesses. The paper we're reading formalizes another strategy as a list of permutations, which considers the set of incorrect entries in the previous guess, and only permuting the incorrect places. Defining an efficient guess as one that maximizes the learned information on each turn, meaning that permutations re-guessing wrong placements are a priori excluded from the next guess. Each incorrect entry then is automatically moved to a spot it's not been in before (Section 1, Introduction).

Assume rightward cyclic shifting by default, as well as no additional information than whether positions are correct or incorrect. The paper cites an example for a game that is both suboptimal by repeated wrong guesses, which and claims that there is always one repetition of incorrect information for at least one possible secret permutation, except if applying cyclic shift. Assuming initially that CS never duplicates incorrect information (Lemma 1), which follows primarily from the fact that positions are matched to symbols, and not to constituent indices, then any other strategy with derangement components repeats information for at least one permutation. All games of permutation wordle begins with a trivial guess, and will aim to achieve that the set of wrong indices I = ∅. The guesses are derangements, in order to avoid CS. The inverse of derangements are also derangements. Displacements are constructed as displacement vectors d(π) for a permutation π ∈ S_n with length n: d(π)[i] := π[i] - i ∀ 1 ≤ i ≤ n (Def. 3). An offending permutation (indexed ω) must be an entry γ₂ = S[n]^-1 to get a sense of how often each character needs to be shifted to the right to get to the correct position. Strategies with length can only have S[n]^-1 can only have entries of 1, 2, 3, which is odd since generally, strategies of length n will have entries in 1, 2, ..., n - 1. As such, the displacement vector used to construct ω to not have any 2's (2.3). An algorithm yielding offending permutation constructors for 2 ∉ D begins as the n-th strategy component S[n] of an inductive strategy with μ = min_{e ∈ D\{1}}. Then, given ι = min{x | D[x] = μ}, K = {ι + k | 1 ≤ k ≤ μ - 1}, for each ι ∈ K: ω[i] := S[n]^-1[i] and for each j ∈ [n]\K, shift S[n]^-1[j] rightward twice (Algorithm 2). If S[n] is a derangement of length n with 2 ∉ D = d(S[n]^-1), then this algorithm produces an offending permutation for the inductive strategy with S[n]. A derangement δ of length n with cycle type [t₁, ..., t_k] has multiplicity μ_i of the cycle length t_i. If μ_i ≥ 2, then any strategy enters an infinite loop for at least one possible secret permutation.

An algorithm can be established for determining the offending permutation constructor for D ⊂ {1, n - 1}n. It primarily distinguishes between the initial strategy S[n], which decomposes into cycles (Algorithm 3). Leaving out cyclic shift vectors, these cases will have addressed all replacement vectors (2.5). The components of a strategy S are required to be derangements since fixed points would cause repetition of wrong information. An offending permutation can be arrived at through inductive strategies of sufficient length. The first κ components of S form an inductive strategy of length κ. The offending permutation is constructed by fixing permutation entries beyond κ, so that after the trivial permutation γ₁, further permutations are created as per the methods above. Essentially, this creates sub-permutations of length κ. For some edge cases, this method does not yield offending permutations, because it defaults back to CS (Section 3). The left displacement vector dl(π) of a permutation in S_n is the list of length n with dl(π)[i] := i - π[i], so a correct entry in an inductive strategy, the incorrect entries will shift left, back into repeated positions (Def 7). Given in mind cyclic shifts either leftward or rightward, the constructor for offending permutations is

(1) If S = CSL = [[1],[2,1],...,[2,...,n−1,1],[n,1,...,n−1]], then ω= [2,n,1,3,...,n−1] (2) If S = CSR = [[1],[2,1],[3,1,2],...,[n−1,1,...,n−2],[2,...,n,1]], then ω= [n,3,...,n−1,1,2]

(Algorithm 4). For a general strategy, this becomes

(1) S[3] defines the problem as left or right shifting. (2) Let κ = min{k≥4 |S[k] is not cyclic shifting in the direction from Step 1} (3) If Step 1 was right-cyclic shifting, let D= dl(S[k]−1). If Step 1 was left-cyclic shifting, let D= dl(S[k]−1) Once determined, ω′ can be constructed. (4) The offending permutation is ω= [ω′[1],ω′[2],...,ω′[k],k+ 1,...,n]

(Algorithm 5)