example about permutation in a finite field

Question

I want to give an example to a corollary in my seminar, but i m not sure if it is ok. can somebody check it quickly?

This is the corollary:

Corollary: Let $n$ and $k$ be positive integers such that $\gcd(n,k)>1$, and let $s$ be any positive integer with $s(q^k-1)\equiv 0 \pmod{q^n-1}$. Then $$h(x)=(x^{q^k}-x+\delta)^s +x$$ permutes $\mathbb{F}_{q^n}$ for any $\delta \in \mathbb{F}_{q^n}.$

And this is my example:

I take $n=2,k=4,q=2$. Then of course $gcd(n,k)=2>1.$

Futhermore: $s(q^k−1)=s(16−1)=s(15)=s(1)=s.$ and $q^n−1=4−1=3.$

So then i choose $s=3$.

$\Rightarrow s(q^k−1)=3=0 \ (mod \ 3)=0 \ (mod \ q^n−1).$ Then I can apply my corollary and i get, that $h$ permutes $\mathbb{F}_{q^n}$ by corollary.

I can check if it is true: $h(0)=δ^s=1$ or $0$, since $\delta \in \mathbb{F}_{2^2}.$

$h(1)=δ^s+1=0$ or $1$, since $\delta \in \mathbb{F}_{2^2}$ means that $\delta$ is either $0$ or $1$.

Therefore $h$ is a permutation and the corallary is true for my example. Is that ok what i did? I think it is maybe wrong, since it is only true for all $s$ modulo 3 and not for any positive integer... I appreciate any help!! Also if u have a better example! Thank you very much!!

Answer 1

A small example I might use is the following. Let $q=2$, $n=4$, $k=2$. Then we can use $s=5$ and $\delta=0$. In this case $$ h(x)=(x^4-x)^5+x=(x^4-x)(x^4-x)^4+x=(x^4+x)(x^{16}+x^4)+x. $$ For all $x\in F=\Bbb{F}_{16}$ we have $x^{16}=x$, so this simplifies to $$ h(x)=(x^4+x)^2+x=x^8+x^2+x. $$ This is, indeed, a permutation of $F$. A quick way of seeing this without the theorem is to realize that $h$ is a so called linearized polynomial (only terms of degree the power of the characteristic occur). Thus the mapping is linear over the prime field $\Bbb{F}_2$. $F$ being finite dimensional $h$ is a permutation iff its kernel is trivial. This is quickly established by observing that the conventional associate (see e.g. Lidl & Niederreiter) of $h$ is $\tau^3+\tau+1$ which is coprime to the conventional associate $\tau^4+1$ of $x^{16}+x$. Thus the kernels of $h(x)$ and $x^{16}+x$ (in an algebraic closure of $F$) intersect trivially, which is what we needed here.

Answer 2

I realize this is far too late for your seminar, but here is an explanation of the quoted result, for the benefit of anyone who finds this post in the future. I note that the condition on $\gcd(n,k)$ is irrelevant. Write $L(x):=x^{q^k}-x$, so that $h(x)=x+g(L(x))$ where $g(x):=(x+\delta)^s$. We show bijectivity of $h(x)$ on $\mathbb F_{q^n}$ in two steps: first we show that $h(x)$ maps each $L$-fiber bijectively onto an $L$-fiber, where an $L$-fiber is a set of the form $\{\alpha\in\mathbb F_{q^n}: L(\alpha)=L(\beta)\}$ for some prescribed $\beta\in\mathbb F_{q^n}$. And then we show that $h(x)$ permutes the set of all $L$-fibers. The combination of these two steps shows that $h(x)$ permutes $\mathbb F_{q^n}$. The key identity that makes this procedure work is that $L(h(x))=f(L(x))$ where $f(x):=x+L(g(x))$. This observation follows immediately from the fact that $L(x+y)=L(x)+L(y)$.

Step 1: $h(x)$ maps each $L$-fiber bijectively onto an $L$-fiber.

Since $L(x)$ induces a homomorphism from the additive group of $\mathbb F_{q^n}$ to itself, if we write $K$ for the kernel of this homomorphism then $\mathbb F_{q^n}\cap L^{-1}(L(\beta))=\beta+K$. It follows that the $L$-fiber containing any $\beta\in\mathbb F_{q^n}$ is $\beta+K$ (since $(\beta+\kappa)+K=\beta+K$ for any $\kappa\in K$, because $K$ is a group). Now since $h(x)=x+g(L(x))$ and $L(K)=0$, we see that $h(\beta+K)=\beta+K+g(\beta)=h(\beta)+K$, so that $h(x)$ maps the fiber $\beta+K$ bijectively onto the fiber $h(\beta)+K$. Note that the fiber $\beta+K$ is the set of $L$-preimages of $L(\beta)$ which are contained in $\mathbb F_{q^n}$, so that each $L$-fiber $\beta+K$ is uniquely determined by the value $L(\beta)=L(\beta+K)$.

Step 2: $h(x)$ permutes the set of $L$-fibers.

The key identity $L(h(x))=f(L(x))$ implies that $L(h(\beta)) = f(L(\beta))$, so we must show that $f(x)$ permutes the set $L(\mathbb F_{q^n})$. But the conditions in the corollary were designed to make this immediate, and more generally to imply that $f(x)$ is the identity map on all of $\mathbb F_{q^n}$. Namely, $f(x)=x+L(g(x))$ where $g(x)=(x+\delta)^s$ with $s(q^k-1)\equiv 0\pmod{q^n-1}$. For any nonzero $\alpha\in\mathbb F_{q^n}$, we have $(\alpha^s)^{q^k-1}=1$, so that $\alpha^s\in\mathbb F_{q^k}$; since plainly $0^s\in\mathbb F_{q^k}$, it follows that $g(\alpha)\in\mathbb F_{q^k}$ for any $\alpha\in\mathbb F_{q^n}$, and thus $g(\alpha)$ is a root of $L(x)=x^{q^k}-x$, so that $f(\alpha)=\alpha$.

QED

===============================================================================

This method for proving that certain polynomials permute $\mathbb F_{q^n}$ was introduced in my paper "Classes of permutation polynomials based on cyclotomy and an additive analogue", and has been used in many subsequent papers by other authors. It is the additive analogue of an older and even more useful "multiplicative" result, namely that $x^r h(x^n)$ permutes $\mathbb F_q$ if and only if $\gcd(r,n,q-1)=1$ and $x^r h(x)^n$ permutes the set of $n$-th powers in $\mathbb F_q$.

I view both of these results as showing how to construct permutation polynomials over $\mathbb F_q$ by, in a sense, "disguising" very simple permutations of an additive or multiplicative subgroup of $\mathbb F_q$. For instance, the result in the post came from the identity permutation of an additive subgroup, and there are hundreds of results in the literature which exhibit classes of permutation polynomials over $\mathbb F_q$ induced from automorphisms of an additive or multiplicative subgroup.

I view both of these results as coming from the same circle of ideas as the following:

(1) The Chebyshev polynomial $T_n(x)$, which is defined by $T_n(\cos \theta)=\cos n\theta$, satisfies the functional equation $T_n(\pi(z))=\pi(z^n)$ where $\pi(z):=(z+1/z)/2$ (so that if $z=e^{i\theta}=\cos\theta+i\sin\theta$ then $\pi(z)=\cos\theta$ is the projection of $z$ onto the $x$-axis). Thus we can study $T_n(x)$ by "lifting" questions about $T_n(x)$ to questions about $x^n$, and phrased the other way, essentially every nice property of $x^n$ as a function yields an analogous nice property of $T_n(x)$. One can do very similar things with the Chebyshev polynomial replaced by a Dickson polynomial $D_n(x,a)$.

(2) Some of the most interesting functions in one-dimensional complex dynamics are the Latt`es maps, which for instance include the map $f(x)$ on $x$-coordinates induced by an endomorphism $\varphi$ of an elliptic curve $E$. These yield a very similar functional equation to case 1, namely $f\circ\pi=\pi\circ\varphi$ where $\pi\colon E\to\mathbb P^1$ is projection on the $x$-axis. These are always studied by lifting questions about $f(x)$ to questions about $\varphi$, which are easier to handle because $\varphi$ is a group homomorphism.

(3) A less-well-known class of examples are the "subadditive polynomials", which date back to Dickson's 1896 Ph.D. thesis. Over a field $K$ of characteristic $p>0$, an "additive polynomial" is a polynomial of the form $\sum_{i=0}^n \alpha_i x^{p^i}$ with $\alpha_i\in K$, and a "subadditive polynomial" is a polynomial of the form $x H(x)^e$ where $H(x)$ is a polynomial and $e$ is a positive integer such that $x H(x^e)$ is additive. In other words, subadditive polynomials $S(x)$ satisfy the equation $S\circ x^e=x^e\circ L$ with $L(x)$ additive. As above, properties of $L(x)$ yield analogous properties of $S(x)$.

Returning to the result at hand, there are now dozens of papers producing examples of permutation polynomials having similar forms to this corollary, but as yet there is no general theory of such polynomials which, for instance, would explain all permutation polynomials of such forms that satisfy certain additional mild constraints. Any such explanation should enable one to count the examples, and also to determine all examples with desirable properties such as having few terms or low degree.