# Values of Polynomial in $\mathbb{F_{2^n}}$

$\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}}$.

Hi,

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.

Greetings.

• Tips: $(X-1)\phi(X)=X(X^{2^{(n-1)}}-1)$ Jun 22 '16 at 15:46
• @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. 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.
• 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? Jun 22 '16 at 19:25