A congruential recurrence characterizes the inverses of Sós permutations
Makoto Nagata, Yoshinori Takei · Tsukuba Journal of Mathematics · 2026
For a positive integer $m$ and a real number $\alpha$, the Sós permutation of degree $m$ is defined to be the permutation which sorts the $m$ fractional parts of the sequence $\alpha, 2\alpha, \ldots, m\alpha$ in increasing order. It has been reported that the inverse of a Sós permutation satisfies a mod-$m$-congruential recurrence as an $m$-term sequence. This paper proves the converse: A permutation satisfying the mod-$m$-congruential recurrence is always the inverse of a Sós permutation. This implies that if a permutation's set of the first-order differences modulo the degree $m$ is a singleton or a set of two successive integers, then the permutation is a shift of the inverse of a Sós permutation, where shift means (the result of) an operation that adds a constant in modulo $m$ to each of the $m$ terms of a given permutation. As an application of these facts, we present a stand-alone combinatorial algorithm that lifts the set of the inverses of the Sós permutations of a given degree $m$ to the set of the same kind of degree $m + 1$ without referring the underlying the Sós permutations or the Farey sequence associated to them.