Recently, Luo [3] introduced the Adding–Swapping Mapping Method to provide an alternative and constructive proof of Stanley’s [4] conjecture on perfect square permutations in \(S_n\) and asked whether the method extends to higher powers. In this paper we answer that question in a more limited but precise structural sense. For each fixed \(k\ge 2\), we define the \(k\)-signature \(R_k(w)\) recording the cycle-count vector modulo \(\gcd(m,k)\) in each length \(m\), and we prove a local residue transition law describing how the insertion map \(D_i\) updates the signature once the cycle length of the insertion point is specified. We also prove explicitly that every \(k\)-th power permutation has zero \(k\)-signature, so the signature gives a necessary obstruction to being a \(k\)-th power. This yields a residue-based partition of \(S_n\) that serves as an indexing scheme for insertion updates. We then show that for \(k\ge 3\) the insertion family does not preserve the class of \(k\)-th powers, explaining why the square case is exceptional from the standpoint of Luo’s method. Finally, we include explicit small-\(n\) data for \(k=3,4\) and prove that the density of \(k\)-th powers in \(S_n\) tends to \(0\) as \(n\to\infty\).
For \(k\ge 2\), call \(w\in S_n\) a \(k\)-th power permutation if there exists \(u\in S_n\) with \(u^k=w\). Let \[\mathcal{P}_n(k)=\{w\in S_n: \exists u\in S_n \text{ with } u^k=w\}, \qquad a_k(n)=|\mathcal{P}_n(k)|.\]
In the square case \(k=2\), Luo [3] employed a family of \((n+1)\) explicit maps from \(S_n\) into \(S_{n+1}\) (the Adding–Swapping Mapping Method) to obtain a constructive proof of Stanley’s [4] conjecture for squares and concluded with the question of whether these methods extend to higher powers.
The purpose of this paper is to isolate the part of Luo’s mechanism that survives for general \(k\). The main invariant is a residue signature on cycle counts. We prove that the insertion maps satisfy a locally deterministic update rule for this signature, conditional on the cycle length receiving the insertion. We also show that the square case remains exceptional: for \(k\ge 3\), the insertion family does not preserve the class of \(k\)-th power permutations. Thus the paper establishes a residue-level extension of the method rather than a full analogue of the square case. Related work on permutation roots can also be found in Glebsky, Licón, and Rivera [2].
Let \(\alpha(n)\) denote the number of perfect square permutations in \(S_n\). Stanley [4] conjectured the identity \[\alpha(2n+1)=(2n+1)\alpha(2n) \qquad \text{for all } n\in \mathbb{N}^*.\]
Blum [1] first proved this identity using generating functions. Later, Luo [3] gave a bijective proof explaining combinatorially why the factor \(2n+1\) appears.
The problem is important because perfect square permutations lie at the intersection of enumerative combinatorics and group theory. Luo’s proof shows that the identity is controlled by the parity of even cycles, while Blum’s proof verifies the identity algebraically. In Luo’s argument, the adding–swapping maps and the three-type decomposition of \(\mathrm{EE}_n\) play a central role.
Luo’s proof proceeds in three steps. First, every perfect square permutation has an even number of even cycles, so one may work inside \(\mathrm{EE}_n\). Second, both \(\mathrm{EE}_{2n}\) and \(\mathrm{EE}_{2n+1}\) are partitioned into the three disjoint types consisting of permutations with only even cycles, only odd cycles, and both even and odd cycles. Third, Luo defines maps \(D_i\) that insert the new letter \(2n+1\) either as a fixed point or into an existing cycle, obtaining a \((2n+1)\)-to-\(1\) correspondence compatible with the square structure. At the end of that work, Luo asks whether the same method can be extended to higher powers. Our answer is structural rather than enumerative. We identify the \(k\)-signature \[{R_k(w)=\bigl(c_m(w) \bmod \gcd(m,k)\bigr)_{m\ge 1}},\] as the natural generalization of Luo’s parity invariant, and we prove a local residue transition law for the insertion maps. This gives a systematic way to track how insertion changes residue data. However, we do not obtain a full higher-power analogue of Luo’s multiplicative identity. Instead, we prove that for \(k\ge 3\) the insertion family necessarily spills out of the class of \(k\)-th powers.
Write a permutation \(w\in S_n\) as a product of disjoint cycles, and let \(c_m(w)\) denote the number of cycles of length \(m\) in \(w\).
Lemma 2.1(Power of a cycle).Let \(\gamma\) be an \(m\)-cycle. Then \(\gamma^k\) decomposes into \(\gcd(m,k)\) disjoint cycles, each of length \(m/\gcd(m,k)\).
Proof. Label the \(m\)-cycle as \((0,1,\dots,m-1)\) acting by \(x\mapsto x+1 \pmod m\). Then \(\gamma^k\) acts by \(x\mapsto x+k \pmod m\). The orbit of \(0\) under repeated addition by \(k\) has size \(m/\gcd(m,k)\), and there are exactly \(\gcd(m,k)\) distinct orbits. Hence \(\gamma^k\) splits into \(\gcd(m,k)\) disjoint cycles of length \(m/\gcd(m,k)\). ◻
Definition 2.2(\(k\)-signature).Fix \(k\ge 2\). For \(w\in S_n\), define its \(k\)-signature by \[R_k(w)=\bigl(c_m(w) \bmod \gcd(m,k)\bigr)_{m\ge 1}.\] We write \(R_k(w)=\vec{0}\) if \(c_m(w)\equiv 0 \pmod{\gcd(m,k)}\) for every \(m\ge 1\).
Remark 2.3. When \(k=2\), one has \(\gcd(m,2)=2\) for even \(m\) and \(\gcd(m,2)=1\) for odd \(m\). Thus \(R_2(w)\) is exactly the parity invariant used in Luo [3].
Theorem 2.4(Necessary signature condition for \(k\)-th powers).Fix \(k\ge 2\). If \(w=u^k\) for some \(u\in S_n\), then for every \(m\ge 1\) one has \[{c_m(w)\equiv 0 \pmod{\gcd(m,k)}.}\] Equivalently, every \(k\)-th power permutation has zero \(k\)-signature: \(R_k(w)=\vec{0}\).
Proof. Write \(u\) as a product of disjoint cycles. Consider a cycle of \(u\) of length \(L\). By the preceding lemma, its \(k\)-th power contributes exactly \(d:=\gcd(L,k)\) cycles of length \(L/d\) to \(w=u^k\). In particular, whenever a cycle of \(w\) has length \(m\), it arises from cycles of \(u\) whose lengths are of the form \(L=md\) with \(d\mid k\) and \(\gcd(m,k/d)=1\). For each such contributing root cycle length \(L\), the contribution to \(c_m(w)\) is exactly \(d=\gcd(L,k)\). Since \(m=L/d\) and \(\gcd(m,k/d)=1\), one has \(\gcd(m,k)=d'\), where \(d'\) divides \(d\); indeed, every prime dividing \(\gcd(m,k)\) must divide \(d\) because it cannot divide \(k/d\). Hence every individual contribution to \(c_m(w)\) is divisible by \(\gcd(m,k)\). Summing over all root cycles that contribute to \(m\)-cycles in \(w\), we obtain \[{c_m(w)\equiv 0 \pmod{\gcd(m,k)}.}\] Therefore \(R_k(w)=\vec{0}\). ◻
Remark 2.5. The condition \(R_k(w)=\vec{0}\) is used throughout as a necessary condition for \(w\in \mathcal{P}_n(k)\). We do not claim that it is sufficient.
For each admissible residue vector \(R\), define \[\mathcal{T}_n(R)=\{w\in S_n: R_k(w)=R\}.\] Then \(\{\mathcal{T}_n(R)\}_R\) is a partition of \(S_n\).
Remark 2.6. These type classes provide a convenient indexing scheme for the residue data. They track how insertion moves permutations among residue classes, but they do not by themselves characterize the set of \(k\)-th power permutations.
We use the insertion form of Luo’s construction: the new letter \(n+1\) is inserted into a chosen cycle immediately after a chosen symbol.
Definition 3.1(Insertion maps D\(_i\)).Fix \(n\ge 1\). For \(w\in S_n\) and \(i\in\{1,\dots,n\}\), define \(D_i(w)\in S_{n+1}\) as follows: write \(w\) in disjoint cycle notation, locate the unique cycle containing \(i\), and insert the new symbol \(n+1\) immediately after \(i\) in that cycle. Define \(D_{n+1}(w)\) to be the permutation obtained by adjoining \((n+1)\) as a fixed point.
Lemma 3.2(Injectivity and disjointness).For each \(i\in\{1,\dots,n+1\}\), the map \(D_i:S_n\to S_{n+1}\) is injective. Moreover, the images \(D_i(S_n)\) are pairwise disjoint.
Proof. Given \(\pi=D_i(w)\), the predecessor of \(n+1\) in its cycle identifies \(i\) when \(i\le n\), while the case \(i=n+1\) is characterized by \(n+1\) being a fixed point. Removing \(n+1\) from the cycle containing it recovers \(w\) uniquely. Thus each \(D_i\) is injective and the images are pairwise disjoint. ◻
We next derive an exponential generating function for the size of each residue class.
Theorem 4.1(Generating function for residue classes).Fix \(k\ge 2\) and let \(d_m=\gcd(m,k)\) for \(m\ge 1\). Let \(R=(r_m)_{m\ge 1}\) be a residue vector with \(r_m\in\{0,1,\dots,d_m-1\}\) and with all but finitely many \(r_m=0\). Define \[F_R(z)=\sum_{n\ge 0}\frac{|\mathcal{T}_n(R)|}{n!}z^n.\] Then \[F_R(z)=\prod_{m\ge 1}\left(\frac{1}{d_m}\sum_{j=0}^{d_m-1}\omega_m^{-jr_m}\exp\!\left(\frac{\omega_m^j z^m}{m}\right)\right),\] where \(\omega_m=\exp\!\left(\frac{2\pi i}{d_m}\right)\) is a primitive \(d_m\)th root of unity.
Proof. A permutation decomposes uniquely into disjoint cycles. In the usual exponential generating function for permutations, cycles of length \(m\) contribute independently with weight \(z^m/m\). Thus the unrestricted exponential generating function is \[\exp\!\left(\sum_{m\ge 1}\frac{z^m}{m}\right).\]
To impose the congruence condition \(c_m(w)\equiv r_m \pmod{d_m}\), apply the roots-of-unity filter: \[\sum_{\substack{c\ge 0\\ c\equiv r_m\ (d_m)}}\frac{1}{c!}\left(\frac{z^m}{m}\right)^c =\frac{1}{d_m}\sum_{j=0}^{d_m-1}\omega_m^{-jr_m}\exp\!\left(\frac{\omega_m^j z^m}{m}\right).\]
Multiplying these independent contributions over all \(m\ge 1\) yields the stated formula. ◻
Corollary 4.2(Zero-signature class).Let \(R=\vec{0}\). Then the exponential generating function for permutations with zero \(k\)-signature is \[F_{\vec{0}}(z)=\prod_{m\ge1}\left(\frac{1}{d_m}\sum_{j=0}^{d_m-1}\exp\!\left(\frac{\omega_m^j z^m}{m}\right)\right).\]
Theorem 4.3(Zero-signature upper bound for \(k\)-th powers).Fix \(k\ge 2\). For every \(n\ge 1\), \[a_k(n)=|\mathcal{P}_n(k)|\le |\mathcal{T}_n(\vec{0})|.\] Equivalently, \[\sum_{n\ge 0}\frac{a_k(n)}{n!}z^n\le F_{\vec{0}}(z).\] In particular, \[a_k(n)\le n!\,[z^n]F_{\vec{0}}(z).\]
Proof. If \(w\in \mathcal{P}_n(k)\), then \(w=u^k\) for some \(u\in S_n\). By Theorem 2.4, \(R_k(w)=\vec{0}\), so \(w\in \mathcal{T}_n(\vec{0})\). Hence \(\mathcal{P}_n(k)\subseteq \mathcal{T}_n(\vec{0})\), which gives the coefficientwise bound and the generating-function inequality. ◻
The insertion maps act on signatures by a locally deterministic rule: once the cycle length of the insertion point is specified, the signature update is completely determined.
Lemma 5.1(Local cycle-length update).Let \(w\in S_n\), and suppose that the cycle of \(w\) containing \(i\in\{1,\dots,n\}\) has length \(m\). Then for \(\pi=D_i(w)\in S_{n+1}\) one has \[c_m(\pi)=c_m(w)-1,\qquad c_{m+1}(\pi)=c_{m+1}(w)+1,\] and \(c_\ell(\pi)=c_\ell(w)\) for all \(\ell\notin\{m,m+1\}\). For \(i=n+1\), one has \(c_1(D_{n+1}(w))=c_1(w)+1\) and all other \(c_\ell\) unchanged.
Proof. Inserting \(n+1\) into a cycle of length \(m\) increases that cycle length to \(m+1\) and leaves all other disjoint cycles unchanged. The fixed-point case is immediate. ◻
Theorem 5.2(Residue transition law).Fix \(k\ge 2\). Let \(w\in S_n\) and let \(i\in\{1,\dots,n\}\). If \(i\) lies in a cycle of \(w\) of length \(m\), then \[R_k(D_i(w))=R_k(w)+\Delta_{m,k},\] where \(\Delta_{m,k}\) is the residue vector whose only possibly nonzero coordinates are at \(m\) and \(m+1\), given by \[(\Delta_{m,k})_m\equiv -1 \pmod{\gcd(m,k)},\qquad (\Delta_{m,k})_{m+1}\equiv +1 \pmod{\gcd(m+1,k)},\] and \((\Delta_{m,k})_\ell\equiv 0\) for \(\ell\notin\{m,m+1\}\). For \(i=n+1\), one has \(R_k(D_{n+1}(w))=R_k(w)+\Delta_{1,k}\).
Proof. Apply the previous lemma and reduce each updated cycle count modulo the corresponding \(\gcd(\ell,k)\). ◻
Corollary 5.3(Transport of type classes).Fix a residue vector \(R\) and an index \(i\in\{1,\dots,n+1\}\). Then \[{D_i(\mathcal{T}_n(R))\subseteq \bigcup_{m\in M_i(R)} \mathcal{T}_{n+1}(R+\Delta_{m,k}),}\] where \(M_i(R)\) denotes the set of cycle lengths that can occur for the cycle containing \(i\) among permutations in \(\mathcal{T}_n(R)\). In particular, the image of a residue class under \(D_i\) need not lie in a single residue class, but it is contained in a union of explicitly determined residue classes.
Proof. If \(w\in \mathcal{T}_n(R)\) and the cycle of \(w\) containing \(i\) has length \(m\), then the residue transition law gives \(R_k(D_i(w))=R+\Delta_{m,k}\). As \(m\) varies over all possible cycle lengths for the symbol \(i\) inside \(\mathcal{T}_n(R)\), the image is contained in the indicated union. ◻
Remark 5.4. Thus the transition rule is deterministic only after conditioning on the cycle length \(m\) of the insertion point. It is not deterministic at the level of the pair \((R_k(w),i)\) alone.
Example 5.5(The case \(k\) = 3).For \(k=3\), one has \(\gcd(m,3)=3\) exactly when \(3\mid m\). Hence nontrivial signature coordinates occur only at multiples of \(3\). If the insertion point lies in a cycle of length \(m\), then:
if \(m\equiv 2 \pmod 3\), the signature gains \(+1\) in the \((m+1)\)-coordinate modulo \(3\);
if \(m\equiv 0 \pmod 3\), the signature gains \(-1\) in the \(m\)-coordinate modulo \(3\);
if \(m\equiv 1 \pmod 3\), the signature is unchanged.
This illustrates the local nature of the transition law: the update is controlled by the residue class of the receiving cycle length modulo \(3\).
We now show that, for \(k\ge 3\), the insertion family does not preserve the class of \(k\)-th powers. This is the precise sense in which Luo’s square mechanism fails to extend directly.
Proposition 6.1(Insertion spillover for \(k\) ≥ 3).Fix \(k\ge 3\). Then there exist \(n\ge 1\), a permutation \(w\in \mathcal{P}_n(k)\), and an index \(i\in\{1,\dots,n\}\) such that \(D_i(w)\notin \mathcal{P}_{n+1}(k)\).
Proof. Let \(r=\operatorname{rad}(k)\) be the product of the distinct prime divisors of \(k\), and set \(m=r-1\). Then \(\gcd(m,k)=1\), since \(m\equiv -1 \pmod p\) for every prime \(p\mid k\). Choose an \(m\)-cycle \(w\in S_m\). Because \(\gcd(m,k)=1\), the map \(x\mapsto x^k\) is an automorphism of the cyclic group generated by \(w\), so \(w\) is itself a \(k\)-th power in \(S_m\).
Now insert \(m+1\) into that unique \(m\)-cycle. The permutation \(D_1(w)\) is an \((m+1)\)-cycle, that is, an \(r\)-cycle. Hence \[{c_r(D_1(w))=1.}\]
Since \(r\mid k\), one has \(\gcd(r,k)=r\), so the \(r\)-th coordinate of the signature satisfies \[{(R_k(D_1(w)))_r \equiv 1 \pmod r,}\] which is nonzero. By Theorem 2.4, any \(k\)-th power permutation must have zero \(k\)-signature. Therefore \(D_1(w)\notin \mathcal{P}_{m+1}(k)\). ◻
Corollary 6.2(Methodological consequence).For \(k\ge 3\), the insertion family \(\{D_i\}\) does not yield a direct Luo-type proof of an identity of the form \[{a_k(n+1)=(n+1)a_k(n).}\]
Proof. Proposition 6.1 shows that, unlike the square case, the insertion family does not preserve the class of \(k\)-th powers. Therefore the direct insertion mechanism used by Luo cannot be transferred unchanged to prove such an identity for general \(k\ge 3\). ◻
This section records explicit residue information for \(k=3,4\) together with small-\(n\) counts.
For \(k=3\), the only nontrivial modulus occurs at lengths divisible by \(3\). For \(k=4\), the nontrivial moduli occur at lengths \(m\) with \(\gcd(m,4)>1\), in particular at \(m=2\) modulo \(2\) and at \(m=4\) modulo \(4\).
In \(S_5\), for \(k=3\) the possible signatures are \[R_3(w)\in\{(0,0,0,0,0),\,(0,0,1,0,0)\},\] because a permutation in \(S_5\) can contain either \(0\) or \(1\) cycles of length \(3\). For \(k=4\), the possible signatures are \[R_4(w)\in\{(0,0,0,0,0),\,(0,1,0,0,0),\,(0,0,0,1,0)\},\] reflecting the residue conditions at lengths \(2\) and \(4\).
Table 1 lists \(a_k(n)=|\mathcal{P}_n(k)|\) for \(k=2,3,4\) and \(1\le n\le 7\). These values were obtained by direct enumeration of the image of the map \(u\mapsto u^k\) on \(S_n\) for each pair \((n,k)\). They illustrate that the higher-power counts do not exhibit the square-case multiplicative behavior, while still fitting naturally into the residue framework developed above.
| \(n\) | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| \(a_2(n)\) | 1 | 1 | 3 | 12 | 60 | 270 | 1890 |
| \(a_3(n)\) | 1 | 2 | 4 | 16 | 80 | 400 | 2800 |
| \(a_4(n)\) | 1 | 1 | 3 | 9 | 45 | 225 | 1575 |
Theorem 8.1(Density tends to 0).Fix \(k\ge 2\). Then \[\frac{a_k(n)}{n!}\longrightarrow 0 \qquad \text{as } n\to\infty.\]
Proof. Let \(w\) be a uniformly random permutation in \(S_n\). Fix a prime divisor \(p\) of \(k\), and let \(q_1<q_2<\cdots\) be the primes that do not divide \(k\). For each \(j\ge 1\), set \[m_j=pq_j.\]
Then \(\gcd(m_j,k)=p\) for every \(j\) such that \(q_j\nmid k/p\); by omitting finitely many indices if necessary, we may assume this holds for all \(j\) under consideration. By Theorem 2.4, a necessary condition for \(w\) to be a \(k\)-th power is \[c_{m_j}(w)\equiv 0 \pmod p \qquad \text{for every } j.\]
For fixed \(L\ge 1\), define the event \[E_L(n)=\bigcap_{j=1}^L \{c_{m_j}(w)\equiv 0 \pmod p\}.\]
Then \[\mathbb{P}(w\in \mathcal{P}_n(k))\le \mathbb{P}(E_L(n)) \qquad \text{for every } n.\]
Now fix \(L\). By the classical joint Poisson limit theorem for cycle counts of random permutations, the vector \[(c_{m_1}(w),\dots,c_{m_L}(w)),\] converges in distribution, as \(n\to\infty\), to a vector \((X_1,\dots,X_L)\) of independent Poisson random variables with means \(1/m_1,\dots,1/m_L\), respectively. Therefore \[\lim_{n\to\infty}\mathbb{P}(E_L(n)) =\prod_{j=1}^L \alpha_j, \qquad \alpha_j:=\mathbb{P}(X_j\equiv 0 \pmod p), \quad X_j\sim \mathrm{Poisson}(1/m_j).\]
Hence \[\limsup_{n\to\infty}\mathbb{P}(w\in \mathcal{P}_n(k))\le \prod_{j=1}^L \alpha_j \qquad \text{for every fixed } L.\]
It remains to show that \(\prod_{j=1}^L \alpha_j\to 0\) as \(L\to\infty\). Since the event \(\{X_j\not\equiv 0 \pmod p\}\) contains \(\{X_j=1\}\), we have \[1-\alpha_j\ge \mathbb{P}(X_j=1)=e^{-1/m_j}\frac{1}{m_j}.\]
For all sufficiently large \(j\), \(e^{-1/m_j}\ge \tfrac12\), so \[1-\alpha_j\ge \frac{1}{2m_j}=\frac{1}{2pq_j}.\]
The sum of reciprocals of the primes diverges, and removing the finitely many primes dividing \(k\) does not affect divergence. Therefore \[\sum_{j=1}^{\infty}(1-\alpha_j)=\infty.\]
A standard criterion for infinite products now gives \[\prod_{j=1}^{\infty}\alpha_j=0.\]
Since the finite products decrease to \(0\), we conclude that for every \(\varepsilon>0\) there exists \(L\) such that \(\prod_{j=1}^L \alpha_j<\varepsilon\). Combining this with the previous limsup bound yields \[\limsup_{n\to\infty}\mathbb{P}(w\in \mathcal{P}_n(k))\le \varepsilon.\]
As \(\varepsilon>0\) was arbitrary, it follows that \[\mathbb{P}(w\in \mathcal{P}_n(k))=\frac{a_k(n)}{n!}\longrightarrow 0.\] ◻
Remark 8.2. This asymptotic result complements the finite-\(n\) spillover phenomenon: the residue obstruction is not only visible at the level of individual insertions, but asymptotically rules out almost all permutations.
We have shown that Luo’s adding–swapping framework admits a residue-level extension to general \(k\ge 2\). The \(k\)-signature provides the correct necessary obstruction for \(k\)-th powers and supports a local residue transition law for insertion maps. The resulting type classes form a useful partition of \(S_n\), but not a characterization of the \(k\)-power class. We also proved that, for \(k\ge 3\), the insertion family does not preserve \(k\)-th powers, which explains why the square case is exceptional from the perspective of Luo’s method. Together with the small-\(n\) data and the asymptotic density theorem, this gives a precise and properly limited structural answer to Luo’s question.
We are indebted to an anonymous referee whose constructive criticism, directives, and guidance greatly improved the quality of this paper. We thank Wallace for providing background support of this paper and contributing to the full completion of this work. We are also grateful to Thomas Etchegaray, student researcher at the Premiere Research Academy, for assembling the historical account of the problem. After being briefed on the topic and introduced to the relevant literature and concepts, he prepared the historical background presented in the paper and assisted in verifying several bibliographic details and contextual notes related to earlier work on square permutations—an exercise that formed part of his training at Premiere.