$ \phi~:~ \mathbb{F_{2^n}} \rightarrow D, ~\phi(X)= X+X^2+...+X^{2^{(n-1)}}$

Show that $D=\{0,1\}$ for any n and $\phi(X)=0$ exactly for half of the $X \in \mathbb{F_{2^n}}$.


got a bit rusty with number theory. My idea: $D=\{0,1\}$ implies $\phi^2(X)=\phi(X)$ $$\mathbb{F_{2^n}}=\{0,1,...,2^n-1\}$$

So $$\phi^2(X)-\phi(X)=\phi(X)(\phi(X)-1)$$ it feels like i have use some number theory things here, but i dont know which.

For the second statement, knowing $D=\{0,1\}$, I got the hint ,consider $\phi(X),~\phi(X)+1$.

It feels like I should be able to consdier the whole equation $\pmod 2$ at some point. Thank you for your help.


  • 1
    $\begingroup$ Tips: $(X-1)\phi(X)=X(X^{2^{(n-1)}}-1)$ $\endgroup$
    – Censi LI
    Jun 22 '16 at 15:46
  • $\begingroup$ @CensiLi That depends on how you interpret the question. Is the sequence of exponents $1,2,3,4,\ldots,2^{n-1}$ or is it $1,2,4,8,\ldots,2^{n-1}$? I don't believe the second half is true under your interpretation, so I would think it's the second interpretation. $\endgroup$
    – Erick Wong
    Jun 23 '16 at 3:19

Because we are in characteristic $2$ we have $$\phi(X)^2=\left(\sum_{k=0}^{n-1}X^{2^k}\right)^2=\sum_{k=0}^{n-1}(X^{2^k})^2=\sum_{k=1}^nX^{2^k}=\phi(X)+(X^{2^n}-X).$$ As we have $x^{2^n}-x=0$ for all $x\in\Bbb{F}_{2^n}$ it follows that $\phi(x)^2=\phi(x)$ holds for all $x\in\Bbb{F}_{2^n}$, and hence $\phi(x)\in\Bbb{F}_2\subset\Bbb{F}_{2^n}$. For the second part you could check that $\phi$ is a group homomorphism.

  • $\begingroup$ Thank you very much, nice application of "Freschmens dream". If $\phi$ is group homorphism, $phi(XY)=\phi(X)\phi(Y)$, i could say all even elments forming the kernel and it follows? $\endgroup$
    – user160069
    Jun 22 '16 at 19:25
  • $\begingroup$ It is an additive group homomorphism, not a multiplicative one. Then you can say the kernel and its coset are the same size. $\endgroup$
    – Servaes
    Jun 22 '16 at 22:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.