What are some examples of numbering systems for which it is easy to generalize permutation polynomials?

Question

I'm writing an assignment on permutation polynomials (PP). I've already explored quite a few generalizations and characterization of PPs over $\mathbb{Z}_p$ for $p$ prime (and finite fields in general) and $\mathbb{Z}$. I'm looking for another numbering system to analyze, ideally one where it is easy to derive a general form for any PP. This was was easily accomplishable for $\mathbb{Z}$ using basic properties of the evaluation map and for $\mathbb{Z}_p$ using Lagrange interpolation + related techniques. I would like this numbering system to be a non-finite field or any commutative ring with unity. If anyone has any suggestions, it would be much appreciated.

Answer 1

The following springs to mind.

Quadratic permutation polynomials on $\Bbb{Z}_m$.

Let $m>1$ be any integer. Consider the quadratic polynomial function $$ f:\Bbb{Z}_m\to\Bbb{Z}_m, x\mapsto ax+bx^2. $$ Prove the following (it's relatively easy, ask if you need a hint).

Lemma. If $\gcd(a,m)=1$ and $b$ is divisible by every prime factor of $m$, then $f$ is a permutation.

---

The reason I recommend this is that such permutation polynomials are used heavily in the LTE standard as turbo code interleavers (the version of the standard that was finalized in 2009, updates pending, and eventually this part is likely to become obsolete). In other words, unless my information is "dated", chances are your cell phone is calculating such permutations a few million times per second. The version of LTE I recall specified a range of values for $m$, each divisible by a relatively high power of two, and an optimized $(a,b)$ pair for each such $m$. The reasons for selecting such permutations are a bit technical, but I think this application is too cool to pass.

The idea was introduced in

J. Sun and O. Y. Takeshita, “Interleavers for turbo codes using permutation polynomials over integer rings,” IEEE Trans. Inf. Theory, vol.51, no. 1, pp. 101–119, Jan. 2005.

This is behind IEEE paywall, but hopefully your institute has access. Probably any reference to 3GPP minutes and/or specs I used back in the day are outdated. When I worked for at the time largish cellular player, I studied the inverse permutations a bit more intensely :-)