# Polynomial over characteristic two finite field of odd degree with certain image

I am trying to construct a polynomial $f \in \mathbb{F}_{2^k}$ of odd degree, such that $\forall x \in \mathbb{F}_{2^k} \exists \alpha \in \mathbb{F}_{2^k}$ such that $f(x)=\alpha ^2 -\alpha$.

Working with some normal basis $\{ \alpha ^{2^i} | 0 \le i \le k-1 \}$, the image of $x \to x^2 -x$ is $\{ \sum c_i \alpha ^{2^i} | \sum c_i = 0, c_i \in \mathbb{F}_{2} \}$. In other words, we require $f(\mathbb{F}_{2^k}) \subseteq Im(t^2-t)$, and this image is a subspace of dimension $k-1$ of the field.

It is easy to construct such $f$ of even degree: $f(x)=x^{2^{i+1}} - x^{2^i}$, for any $i$.

EDIT: I managed to find an example, but I don't like it much: taking $f(x) = x^{2^k + 1} - x$. For every $x \in \mathbb{F}_{2^k}$, $f(x)=x^2-x$.

-
You're correct, I've fixed it. – Ofir Jul 7 '12 at 11:30
Perhaps you should use $\,X\,$ for indeterminates and $\,x\,$ for specific values (as in your edit), otherwise things get confusing: as polynomials, obviously $\,X^{2^k+1}-X\neq X^2-X\,$ , yet as $\,\Bbb F-\,$ valued functions, $\,f(t):= t^{2^k+1}-t=t^2-t=:g(t)\,$ – DonAntonio Jul 7 '12 at 11:35
Another option is $f(x) = x^{2^{k}+1} - x^{2}$, which is constant on $\mathbb{F}_{2^k}$: it equals $0$, which is trivially in the subspace. It is also of odd degree. – Ofir Jul 7 '12 at 11:37
@anon , you should write down your comment as answer: good! +1 – DonAntonio Jul 7 '12 at 11:38
It should probably be $x^2-x^{2^k+1}$ in your edit. – tomasz Jul 7 '12 at 11:50

Another way to state your condition is that, for every $\beta \in \mathbf{F}_{2^k}$, $f(\beta)$ has trace 0 over $\mathbf{F}_2$.

For $k=5$, an example is $f(x) = x^9 - x^5$. To see that this has trace 0 for any $\beta \in \mathbf{F}_{32}$:

\begin{align*} \mathop{Tr}(\beta^9 - \beta^5) &= \mathop{Tr}(\beta^9) - \mathop{Tr}(\beta^5) \\&= (\beta^9 + \beta^{18} + \beta^{36} + \beta^{72} + \beta^{144}) - (\beta^5 + \beta^{10} + \beta^{20} + \beta^{40} + \beta^{80}) \\&= (\beta^9 + \beta^{18} + \beta^{5} + \beta^{10} + \beta^{20}) - (\beta^5 + \beta^{10} + \beta^{20} + \beta^{9} + \beta^{18}) \\&= 0 \end{align*}

In general, the condition means that

$$f(\beta) + f(\beta)^2 + \cdots + f(\beta)^{2^{k-1}} = 0$$

for every $\beta \in \mathbf{F}_{2^k}$, or equivalently,

$$f(x) + f^\sigma(x^2) + f^{\sigma^2}(x^4) + \cdots + f^{\sigma^{k-1}}(x^{2^{k-1}}) \equiv 0 \pmod{ x^{2^k} - x}$$

where $f^\sigma$ is the polynomial formed by conjugating each coefficient of $f$ by the action $u \mapsto u^2$.

We can split the powers of $x$ into orbits under the action $x \mapsto x^2 \pmod{x^{2^k} - x}$ -- i.e. writing

$$f(x) = u + h(x) (x^{2^k} - x) + \sum_m g_m(x^m)$$

where $u$ is a constant with trace 0, and each $g$ has the form

$$g(x) = \sum_{j=0}^{k-1} c_j x^{2^j}.$$

Each $g(x)$ must satisfy the constraint, and any choice of valid $g's$ gives a valid $f$. So,

$$0 \equiv \sum_{i=0}^{k-1} g^{\sigma^i}(x^{2^i}) \equiv \sum_{i=0}^{k-1} \sum_{j=0}^{k-1} c_j^{2^i} x^{2^{i+j}} = \sum_{j=0}^{k-1} x^{2^{j}} \sum_{i=0}^{k-1} c_{j-i}^{2^{i}} \pmod{x^{2^k} - x}$$

(there was a change of variable $j \mapsto j-i$) where the index on $c$ is taken modulo $k$. Each coefficient gives the same condition:

$$\sum_{i=0}^{k-1} c_{k-1-i}^{2^i} = 0$$

Now, how can we use this to find a polynomial of small, odd degree? Consider $k=5$. One of the orbits of powers of x is:

$$x^5, x^{10}, x^{20}, x^{40} \equiv x^9, x^{80} \equiv x^{18}$$

By setting the coefficients on $x^9$ and a smaller term to $1$ and the rest to $0$ will satisfy the equation. This is the example at the top of my answer.

-
+1: Yes, this is a standard use of the trace function in finite fields of characteristic two. Well done! – Jyrki Lahtonen Jul 7 '12 at 12:28

This answer is to supplement Hurkyl's answer. I give examples of such polynomials for all the finite fields of characteristic two. I need the basic result, brought up by Hurkyl, stating that $\ker\, tr=\mathrm{Im}(x^2-x)$. This follows from rank-nullity, because the mappings $$tr:\mathbb{F}_{2^k}\rightarrow \mathbb{F}_2,x\mapsto\sum_{i=0}^{k-1}x^{2^i}$$ and $$f:\mathbb{F}_{2^k}\rightarrow\mathbb{F}_{2^k},x\mapsto x^2-x$$ are both linear over the prime field, satisfy $tr(x)=tr(x^2)$, for all $x$, $tr\circ f=0$, $tr\not\equiv0$ and that $\ker f=\{0,1\}$ is one-dimensional (if you didn't know this I HIGHLY recommend proving these facts as exercises).

1. If $k$ is even, say $k=2\ell$, then the monomial $f(x)=x^{2^\ell+1}$ works. This is because this polynomial is the relative norm map $N:\mathbb{F}_{2^k}\rightarrow\mathbb{F}_{2^\ell}$. We also see directly that $f(x)\in \mathbb{F}_{2^\ell}$ for all $x\in \mathbb{F}_{2^k}$ from the calculation $$f(x)^{2^\ell}=x^{2^\ell(2^\ell+1)}=x^{2^{2\ell}+2^\ell}=x^{2^k}\cdot x^{2^\ell}= x\cdot x^{2^\ell}=f(x),$$ and the claim follows because this intermediate field consists precisely of the solutions of $y^{2^\ell}=y$. Using this identity we also get the claim as $$tr(f(x))=\sum_{i=0}^{2\ell}f(x)^{2^i}=\sum_{i=0}^{\ell}(f(x)^{2^i}+f(x)^{2^{i+\ell}}) =\sum_{i=0}^{\ell}(f(x)+f(x)^{2^\ell})^{2^i}=\sum_{i=0}^\ell0=0.$$

2. If $k=2\ell+1$ is odd, then $$2^\ell(2^{\ell+1}+1)=2^{2\ell+1}+2^\ell\equiv 1+2^\ell\pmod{2^k-1},$$ so $2^{\ell+1}+1$ and $2^{\ell}+1$ are in the same cyclotomic coset, and by the theory described by Hurkyl we get by choosing $f(x):=x^{2^{\ell+1}+1}+x^{2^\ell+1}$ that $$tr(f(x))=tr(x^{2^{\ell+1}+1})+tr(x^{2^\ell+1})=2\cdot tr(x^{2^\ell+1})=0,$$ for all $x\in\mathbb{F}_{2^k}$.

These are (at least nearly) the "best possible" in the sense that the degree of a polynomial $f(x)$ satisfying this condition must have degree $>\sqrt{2^k}$. If $\chi(x):=(-1)^{tr(x)}$ is the natural additive character, the (somewhat deep but well known) result known as Carlitz-Uchiyama bound says that for a polynomial $f(x)$ of an odd degree $d$ we have $$\left\vert\sum_{x\in\mathbb{F}_{2^k}}\chi(f(x)\right\vert\le(d-1)\sqrt{2^k}.$$ The condition set by OP to the polynomial $f$ imply that we have $\chi(f(x)=1$ for all $x$, so the sum is equal to $2^k$. Carlitz-Uchiyama bound then implies that $d-1\ge\sqrt{2^k}$.

-
Even if you don't want to study the trace function you can see using a normal basis representation that the values of these polynomials have digit sums equal to zero. In the first case the vector of coordinates must have equal halves (because the values are in the subfield). In the second case the values of the two monomials are conjugates of each other (apply Frobenius $\ell$ times), and again there sum must have an even number of non-zero coordinates. – Jyrki Lahtonen Jul 10 '12 at 10:54