# How to see that the polynomial $4x^2 - 3x^7$ is a permutation of the elements of $\mathbb{Z}/{11}\mathbb{Z}$

This is from Rotman's Group Theory book, although I don't have the specific reference right now, as the book is with a friend. He asks to show that $\alpha (x) = 4x^2 - 3x^7$ is a permutation of the elements of $\mathbb{Z}_{11} = \mathbb{Z} / 11\mathbb{Z}$.

I can show this by brute force calculation, but I feel there must be some more elegant way to show this. I looked at the Wikipedia page on permutation polynomials, which, based on a quick perusal, seemed to suggest that it is not an easy question when the degree of the polynomial is greater than 2. It also mentioned the Dickson polynomials, but unless I am missing something, the polynomial in the question isn't a Dickson polynomial.

I understand that there might not be a general method for this type of question, but even if someone can help me understand this particular example better, I would appreciate it. In particular, what I'd like to know is:

1. is there a nice way to build a permutation polynomial given some quotient of $\mathbb{Z}$ to be permuted?
2. can we say something about the inverse of the polynomial -- is it also a polynomial? How is it related to the initial polynomial?
3. is there some faster way than plugging in to see that this polynomial must act as a permutation on $\mathbb{Z}_{11}$?
4. what other sets $\mathbb{Z}_{n}$ will be permuted by this polynomial? How can we see this?

Answers to any or all of these questions, or explanations why there are not good answers, would be much appreciated. Thanks!

p.s. this is my first post, so please feel free to edit/re-tag as necessary as I am not yet sure how this all works.

-
On 2. Yes. Every permutation $\alpha$ of $\mathbb{F}_{11}$ is of finite order $o(\alpha)$. So if $f\in\mathbb{F}_{11}[X]$ acts on $\mathbb{F}_{11}$ as a permutation, then the inverse of that permuation is given by $f^{\circ o(f)-1},$ the $o(f)-1$-fold iterate of $f.$ – jspecter Sep 19 '11 at 14:59
A minor caveat, $\mathbb Z_p$ is often used to denote the $p$-adic integers. If you give the definition in the question it's fine. However keep in mind that at times it can be unclear from context whether you talk about $\mathbb Z/p\mathbb Z$ or $p$-adic integers. Just so you know for a future reference. – Asaf Karagila Sep 19 '11 at 16:14
jspecter -- Thanks for the answer to question 2; it seems somewhat obvious now, but that's the value of a good answer -- it makes the non-obvious seems obvious. – Jeremy Levick Sep 20 '11 at 17:49
Asaf Karagila -- thanks for pointing that out. I've made the change in the title of the question, so as not to confuse anyone who doesn't read far enough into the body of the question to see the definition I gave. – Jeremy Levick Sep 20 '11 at 17:53

I will give a shorter proof that $\alpha$ is a permutation on $\mathbb Z/11\mathbb Z$. (All the operations here are modulo $11$.) First of all, we make the following observation:

1. If $x = 0$, then $\alpha (x) = 0$.
2. If $x \neq 0$ is a quadratic residue modulo $11$, then $x^5 = 1$. Therefore, $\alpha(x) = x^2(4-3) = x^2,$ which is also nonzero and is a quadratic residue.
3. If $x \neq 0$ is a quadratic non-residue modulo $11$, then $x^5 = -1$, so that $\alpha(x) = x^2(4+3) = 7x^2 \equiv -4x^2$, which is also a quadratic non-residue. (I'll drop the term "quadratic" from now on.)

We now start with the proof. Clearly it suffices to show that $\alpha$ is injective. Since $\alpha(x) = 0$ iff $x=0$, we may restrict ourselves to $\mathbb Z_{11}^{\ast}$. Suppose $x, y \in \mathbb Z_{11}^{\ast}$ are such that $\alpha(x) = \alpha(y)$. Then from the observations (2.) and (3.), it follows that either both $x$ and $y$ are residues, or both are non-residues. In either case, we have $4 - 3x^5 = 4-3y^5 (\neq 0)$. Hence we have $$x^2(4-3x^5) = y^2(4-3y^5) \implies x^2 = y^2 \implies y \in \{ -x, x\}.$$ If $y = -x$, then exactly one of $\{ x, y \}$ is a residue and the other is a non-residue, which we have already ruled out as impossible. Hence the only remaining possibility is that $x=y$, and we are done. $\ \ \ \ \Box$

I think the same idea can be used to manufacture permutation polynomials for $\mathbb Z/p\mathbb Z$ for any prime $p \equiv 3 \pmod{4}$. (The restriction on $p$ is so that $-1$ is a quadratic non-residue.) Pick a residue $c$ and a non-residue $d$ modulo $p$ (where $c,d \neq 0$), and define $$\alpha(x) = x^2 \left( \frac{c+d}{2} + \frac{c-d}{2} x^{\frac{p-1}{2}} \right) .$$ By the above proof, this polynomial is a permutation polynomial for $\mathbb Z/p\mathbb Z$. This question is a specific example with $c = 1$ and $d=7$.

-
+1 This is a very nice argument. The observation the QRs and QNRs won't mix is the key. – Jyrki Lahtonen Sep 19 '11 at 18:39
Thanks for this answer! It took a little while to satisfy myself I could see why this works, but this is exactly what I was looking for. – Jeremy Levick Sep 20 '11 at 17:46

HINT $\$ It is easy to verify that the map is onto (so $1$-to-$1$) by breaking it down as follows:

$$\rm\begin{array}{lllll} &\rm on \ \ \ \{n:\ n^5 \equiv 1\}&\rm it's &\rm x\to\quad x^2 &\rm with\ orbit\ \ \ \ (1)\ \ (-2\ \ 4\ \ 5\ \ 3) \\ &\rm on\ \ \{n:\ n^5 \equiv -1\} &\rm it's\ \ &\rm x\to\: -(2\:x)^2 &\rm with\ orbit\ \ (-3)\ (-1\ \:{-}4\ \ 2\:\ {-}5) \end{array}$$ Alternatively you could verify the resultant $\rm\:res(f(x)-y,\:x^{11}-x)\ =\ y^{11}-y\$ over $\rm\:\mathbb Z/11\:,\:$ which calculation could be broken down and simplified as above. Generally one easily shows that $\rm\:f(x)\:$ is a permutation polynomial on $\rm\:\mathbb F_q[x]\:$ $\:\iff\:$ $\rm\:y^q-y\ |\ res(f(x)-y,\:x^q-x)\:.$

-

On 1. As it turns out every permutation of $\mathbb{Z}/p$ for $p$ prime is given by a unique polynomial of degree less than p.

Let $\alpha$ be an element of $\mathbb{Z}/p$ and consider the following polynomial

$$f_{\alpha}(X) := \displaystyle\prod_{\begin{subarray}{l} \beta\in\mathbb{Z}/p\\ \alpha \neq \beta \end{subarray}} { } (X- \beta) \in \mathbb{Z}/p[X].$$

Then $f_{\alpha}(\beta)$ is equal to zero if $\alpha \neq \beta$ and is nonzero otherwise. It follows, as $\mathbb{Z}/p$ is a field, there exists a multiplicative inverse of $f_{\alpha}(\alpha).$ Define

$$\delta_{\alpha}(X) := \frac{f_{\alpha}(X)}{f_{\alpha}(\alpha)}.$$

The polynomial $\delta_{\alpha}$ then satisfies $$\delta_{\alpha}(\beta) = \left\{ \begin{array}{ll} 1 &\mbox{if } \beta = \alpha \\ 0 &\mbox{otherwise} \end{array} \right.$$

and is of degree $p-1.$

Now let $F:\mathbb{Z}/p \rightarrow \mathbb{Z}/p$ be any function and consider the polynomial

$$f_{F}(X) = \sum_{\alpha\in\mathbb{Z}/p} F(\alpha)\delta_{\alpha}(X).$$

Then $f_{F}$ has degree less than $p$ and satisfies $f_{F}(\beta) = F(\beta)$ for all $\beta \in \mathbb{Z}/p.$

It follows that any element $\mathbb{\sigma} \in S_{\mathbb{Z}/p},$ $f_{\sigma}$ is a polynomial of degree less than $p$ which acts on $\mathbb{Z}/p$ as $\sigma.$

Now assume $g$ is any polynomial of degree less than $p$ which acts as $\sigma.$ Then $g - f_{\sigma}$ acts on $\mathbb{Z}/p$ as the zero map. It follows that $g - f_{\sigma}$ is either equal to $0$ or divisible by $O_p := \displaystyle\prod_{\begin{subarray}{l} \beta\in\mathbb{Z}/p \end{subarray}} { } (X- \beta).$ As the latter cannot occur by degree considerations, it must the case $g - f_{\sigma} = 0$ and we conclude $f_{\sigma}$ is the unique polynomial of degree less than $p$ which acts on $\mathbb{Z}/p$ as $\sigma.$

Moreover, for any $\sigma\in S_{\mathbb{Z}/p}$

$$\{g\in \mathbb{Z}/p[X]: g(\beta) = \sigma(\beta) \mbox{ for all } \beta\in\mathbb{Z}/11\} = f_{\sigma} + O_p\mathbb{Z}/p[X].$$

-
Just a remark: your procedure constructs all functions from a finite field $\mathbb{F}_q$ to itself as reduced polynomials (i.e., of degree less than $q$), not just bijections. So in a sense this is an answer to the OP's question: using this one can write down all permutation polynomials over a given finite field...but nevertheless I think this is the beginning of the theory, not the end of it. – Pete L. Clark Sep 19 '11 at 17:05
Another remark. You can in fact get the better upper bound on $\mathrm{deg}(f_{\sigma})$ of $p-2$ when $p$ is odd. This is because in this case, $f_{\alpha}(\alpha) = \prod_{\beta \in \mathbb{Z}/p^{\times}} \beta = -1$ for all $\alpha\in\mathbb{Z}/p.$ It follows that the coefficient of $X^{p-1}$ in $f_{\sigma}$ is $-\sum_{\beta\in{\mathbb{Z}/p}} \beta = 0.$ – jspecter Sep 19 '11 at 17:18