# Theorem in finite fields fails in my example

I need to understand the following theorem, so i did an example. But i realized that i don't get everything in the finite field theory. can somebody check the example and say where the mistake is?

Thm: Let $$q=p^e$$ for some positive integer $$e$$.

a) if $$k \geq 2$$ is an even integer or $$k$$ is odd and $$q$$ is even, then $$f_{a,b,k}(x):=ax^q+bx+(x^q-x)^k, a,b \in \mathbb{F}_{q^2}$$ with $$a+b \in \mathbb{F}^*_q$$, permutes $$\mathbb{F}_{q^2}$$ if and only if $$b\not=a^q$$.

b) if $$k$$ and $$q$$ are odd positive integers, then $$f_{a,k}(x):=ax^q+a^qx+(x^q-x)^k, a \in \mathbb{F}^*_{q^2}$$ with $$a+a^q \not=0$$, permutes $$\mathbb{F}_{q^2}$$ if and only if gcd($$k,q-1)=1$$.

My example for a): I take $$k=2,q=2$$. So $$k$$ is an even integer bigger or equal 2. Now i choose $$a$$ and $$b$$, and i think here is my mistake: $$a,b \in \mathbb{F}_{q^2}$$. That means a,b are polynomials in the form: $$a_1+a_2w$$ where $$a_1,a_2$$ are in $$\mathbb{F}_2$$, hence $$a_1,a_2$$ are either $$0$$ or $$1$$.$$w$$ is in $$\mathbb{F}_{2^2}$$, that means w is either $$1,x$$ or $$x^2$$.

So I choose: $$a=1+x^2, b=1.$$

Then i check if $$a+b \in \mathbb{F}^*_q$$: $$a+b=1+1+x^2=2+x^2=x^2$$, since we have $$q=2$$. Therefore $$a+b=x^2 \in \mathbb{F}^*_q$$.

So i can apply the theorem: $$a^q=(1+x^2)^2=1+x^4=1+x \not=b$$.

Therefore $$f_{a,b,k}$$ permutes $$\mathbb{F}_{q^2}$$.

So I check if this is true:

$$f_{a,b,k}(x)=(1+x^2)x^2+x+(x^2-x)^2=x^2+x^4+x+x^4+x^2=x$$ since $$x \in \mathbb{F}_4.$$

Therfore $$f_{a,b,k}$$ does permutes $$\mathbb{F}_{q^2}$$.

I hope anybody can help! I appreciate any help!

b) I take $$q=k=3$$.

$$\Rightarrow F_3=\{0,1,2\}$$ and $$F^*_9=\{1,2,\alpha, 2\alpha, 1+\alpha, 1+2\alpha, 2+\alpha, 2+2\alpha\}.$$

So to choose a, i have the condition $$a+a^q \not=0$$. So for example, i take $$a=1$$. $$\Rightarrow 1+1^2=2 \not=0$$.

Since gcd$$(3,2)=1$$, it follows by the theorem that $$f_{1,3}(x)$$ permutes $$F_9$$.

Check: $$f_{1,3}(x)=x^3+x+(x^3-x)^3=2x^3+2x.$$

$$\Rightarrow: f_{1,3}(0)=0 \ (modulo \ 9), f_{1,3}(1)=4 \ (modulo \ 9), f_{1,3}(2)=2 \ (modulo \ 9), f_{1,3}(3)=6 \ (modulo \ 9), f_{1,3}(4)=1 \ (modulo \ 9), f_{1,3}(5)=8 \ (modulo \ 9), f_{1,3}(6)=3 \ (modulo \ 9), f_{1,3}(7)=7 \ (modulo \ 9), f_{1,3}(8)=5 \ (modulo \ 9).$$

So it is true!

• Firstly you seem to be using $x$ with two different meanings. In the definition of $F_{a,b,k}(x)$, $x$ is a variable that takes values in $F_{q^2}$, not a fixed element of $F_{q^2}$. Secondly, the dimension on $F_{q^2}$ over $F_2$ is $2$, not $3$, so elements of $F_{q^2}$ have the form $a + bw$, where $a,b \in F_q$, and $w$ is a fixed element of $F_{q^2}$ (the basis is $1,w$). Commented May 25, 2014 at 12:50
• I'm afraid your attempted example reveals serious misunderstandings about finite fields. I think you should spend some time learning the basics about their construction and various presentations of their elements before you try your hand at grasphing relatively non-trivial constructions of permutation polynomials. I will take a quick look at the case $q=k=2$, but I have this nagging feeling that it may not help you very much. Commented May 25, 2014 at 13:33
• thanx both of you! i just edited my example with the input of derek. I know that i have a lot of missunderstandings, so i try to do as much examples as possible. is it right now?
– mr_T
Commented May 25, 2014 at 13:37
• You didn't fully get Derek's point. You still use $a=1+x^2$, but $a$ is supposed to be a constant from $\Bbb{F}_4$. Commented May 25, 2014 at 13:58
• It looks like you need to gain familiarity with the constructions and arithmetic of finite fields. I cannot do all that, but this CW question/answer pair I designed for the benefit of our tag wiki may help you a little. Commented May 25, 2014 at 14:05

Let's look at the case $q=2, k=2$. We seek to get permutations of $\Bbb{F}_4$, so let's first recall that $$\Bbb{F}_4=\{0,1,\alpha,\alpha+1\},$$ where $\alpha$ is a zero of the polynomial $x^2+x+1$. Therefore the multiplication table looks like $\alpha^2=\alpha+1$, $\alpha(\alpha+1)=\alpha^2+\alpha=1$, and $(\alpha+1)^2=\alpha^2+1=(\alpha+1)+1=\alpha$.
The construction calls for a pair of elements $a,b\in \Bbb{F}_4$ such that $a+b\in\Bbb{F}_2^*$. This is very restrictive as $\Bbb{F}_2=\{0,1\}$, so we are forced to choose $a+b=1$. Furthermore the pairs $\{a,b\}=\{\alpha,\alpha+1\}$ are excluded, because we just saw that those two elements are squares of each other. Thus we are left with the two choices $a=0,b=1$ or $a=1,b=0$. Let's do the first one. $$f_{0,1,2}(x)=ax^2+bx+(x^2+x)^2=x+(x^2+x)^2=x+(x^4+x^2)=x+x^4+x^2.$$ For all $x\in\Bbb{F}_4$ we have $x^4=x$. So as a polynomial function from $\Bbb{F}_4$ to itself $f_{0,1,2}(x)=x^2$ is just the Frobenius automorphism, and hence known to be permutation: $$f_{0,1,2}:0\mapsto 0,1\mapsto1,\alpha\mapsto \alpha+1,\alpha+1\mapsto \alpha.$$ As another check let's explain what goes wrong, if we don't observe the condition $a\neq b^q$. If we try here $a=\alpha, b=a^2=\alpha+1$, then we get the polynomial $$f_{\alpha,\alpha+1,2}(x)=\alpha x^2+(\alpha+1)x+(x^2+x)^2=x^4+(\alpha+1)(x^2+x).$$ We see that $f_{\alpha,\alpha+1,2}(0)=0$, but also that $$f_{\alpha,\alpha+1,2}(\alpha+1)=(\alpha+1)^4+(\alpha+1)([\alpha+1]^2+[\alpha+1])= (\alpha+1)+(\alpha+1)\cdot1=0,$$ so we don't get a permutation in this case.