2
$\begingroup$

I'm preparing a seminar and the problem is that I never had a lecture before in finite fields. So I had to learn everything by myself, and that is unfortunately not easy at all... Can anyone help me by understanding the following corollary and give me an example! I would really appreciate that!!

Corollary: If $h(x) \in \mathbb{F}_q[x], h(0) \not= 0$, then the polynomial $p(x)=x h(Tr(x))$ permutes $\mathbb{F}_{q^n}$ if and only if $u(x)=x(h(x))$ permutes $\mathbb{F}_q$.

$Tr$ is the trace function from $\mathbb{F}_{q^n}$ to $\mathbb{F}_q$: $ Tr(x)=x+ x^q+x^{q^2}+...+x^{q^{n-1}}. $

Can someone help me by giving me an example? Thank you very much!

$\endgroup$
4
  • $\begingroup$ What do you mean by $\operatorname{Tr}(x)$ in this context? $\endgroup$
    – Servaes
    Commented May 21, 2014 at 12:12
  • $\begingroup$ It is the trace function from $\mathbb{F}_{q^n}$ to $\mathbb{F}_q$: $Tr(x)=x+x^q+x^{q^2}+...+x^{q^{n-1}}.$ $\endgroup$
    – mr_T
    Commented May 21, 2014 at 12:16
  • $\begingroup$ Ah I see, thank you. It might also help to post the theorem/lemma/proposition of which this is a corollary. $\endgroup$
    – Servaes
    Commented May 21, 2014 at 12:17
  • $\begingroup$ it is a big theorem... it is theorem 5.2 on page 8 of the following pdf: cse.ust.hk/faculty/cding/JOURNALS/ffa111.pdf $\endgroup$
    – mr_T
    Commented May 21, 2014 at 12:21

1 Answer 1

1
$\begingroup$

An example: Let $q=5$. Consider $h(x)=x^2+x+2=(x-2)^2-2$. Then $u(0)=0$, $u(1)=4$, $u(2)=1$, $u(3)=2$ and $u(4)=3$, so $u$ is a permutation of the field $\Bbb{F}_5$. The theorem then states that for all positive integers $n$ the function $$ p(x)=x\,h(\mathrm{tr}(x)) $$ is a permutation from the field $\Bbb{F}_{5^n}$ to itself.


Here's a proof of one of the implications: $u$ is a permutation $\implies$ $p$ is a permutation. I realized later that you were not asking for one, but I enjoyed working this part out, so I'm leaving it out as it may give others an idea what it entails.

So let's assume that $u:\Bbb{F}_q\to\Bbb{F}_q$ is a permutation.

We have $u(0)=0h(0)=0$, so because $u$ is a permutation we have $u(x)=xh(x)\neq0$ for all $x\neq0$. In particular $h(x)\neq0$ for all $x\in\Bbb{F}_q^*$. Taking into account the extra assumption $h(0)\neq0$ this implies that $h(x)\in\Bbb{F}_q^*$ for all $x\in\Bbb{F}_q$.

Because the field $\Bbb{F}_{q^n}$ is a finite set, it suffices to show that $p$ is injective. Assume that there exist two distinct elements $x,y\in \Bbb{F}_{q^n}$ such that $$ x\, h(\mathrm{tr}(x))=y\,h(\mathrm{tr}(y)).\qquad(*) $$ Above we saw that the values $h(\mathrm{tr}(x))$ and $h(\mathrm{tr}(y))$ are non-zero elements of the smaller field. Therefore for $\alpha=h(\mathrm{tr}(y))/h(\mathrm{tr}(x))\in\Bbb{F}_q^*$ equation $(*)$ takes the form $x=\alpha y$. A useful fact about the trace is that it is linear over the smaller field. Therefore $\mathrm{tr}(x)=\mathrm{tr}(\alpha y)=\alpha \mathrm{tr}(y)$. Thus $(*)$ reads $$ \alpha y\, h(\alpha \mathrm{tr}(y))=y\,h(\mathrm{tr}(y)).\qquad(**) $$ Here we clearly have $y\neq0$ as otherwise the r.h.s. of $(*)$ vanishes, so we would need to have $x=0$ as well. Therefore we can multiply $(**)$ by $\mathrm{tr}(y)/y$ and get $$ \alpha\mathrm{tr}(y)\, h(\alpha \mathrm{tr}(y))=\mathrm{tr}(y)\, h(\mathrm{tr}(y)). $$ But this states that $u(\alpha \mathrm{tr}(y))=u(\mathrm{tr}(y))$. Because $u$ was assumed to be permutation this is possible only if $\alpha=1$ or $\mathrm{tr}(y)=0$. In the former case we get $x=\alpha y=y$. In the latter case $(*)$ reads $x\,h(\alpha\cdot0)=x\,h(0)=y\,h(0)$, and again we can conclude that $x=y$ as $h(0)\neq0$. Q.E.D.

$\endgroup$
1
  • $\begingroup$ It is not too difficult to generate examples here. You just use the observation that any function from $\Bbb{F}_q$ to itself comes from a polynomial. So you can begin by fixing a permutation $u$ such that $u(0)=0$, and then that determines $h(x)$ whenever $x\neq0$. Make $h(0)$ anything you want, and then use Lagrange interpolation to find $h(x)$. When I did this it often lead to $h(x)$ having uncomfortably high degree, which didn't feel nice at all :-( $\endgroup$ Commented May 21, 2014 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .