# Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?

Consider the polynomial $p(x) = 1+x^5+x^{10}$ with binary coefficients. Consider the multiplicative group of $\mathbb{F}_{16}$, and let $p(x)$ be evaluated at each of these $15$ elements. The only possible evaluations are $0$ and $1$.

I am looking for more such polynomials which have binary coefficients, which when evaluated on the elements of an extension field (or its multiplicative group), gives only $0$ or $1$.

Is there an already established theory or terminology for such polynomials? I am unable to get anywhere with my googling.

Thanks!

#### Solutions Collecting From Web of "Which polynomials with binary coefficients evaluate only to 0 or 1 over an extension field?"

Just listing my first impressions on how to arrive at a description. This is surely known, but I cannot point you at a source right away.

The Question: Given a finite extension field $E=\Bbb{F}_{2^n}$ of $F=\Bbb{F}_2$ describe the set of polynomials $p(x)\in F[x]$ with the property that $p(\alpha)\in F$ for all $\alpha\in E$.

Clearly such polynomials form a subring $R$ of $F[x]$. If we abbreviate $N=2^n-1$, then the monomial $x^i\in R$ whenever $N\mid i$, because $\alpha^N=1$ for all $\alpha\in E, \alpha\neq0$. Furthermore, all the binomials $x^i+x^j$ with $i\equiv j\pmod N$ are in the ring $R$.

The above observations imply that it suffices to identify the set
$$R_N=\{p(x)\in F[x]\mid p(x)\in R, \deg p<N\}.$$
Namely, a polynomial $p(x)=\sum_i a_ix^i\in F[x]$ is in the ring $R$ if and only if its projection $p^N(x):=\sum_{j=0}^{N-1} b_jx^j$ with $b_j=\sum_{i\equiv j\pmod N}a_i$ is in the ring $R$.

This is a useful reduction, because when we restrict ourselves to the set $R_N$, no two polynomials give rise to the same evaluation function $E\to E$.

The trick is surely that we can identify whether an element of $E$ is in $F$ by checking that it is a fixed point of the Frobenius automorphism $\phi:E\to E, \phi(z)=z^2$.
So a polynomial $p(x)=\sum_{i=0}^{N-1}a_ix^i\in R_N$ if and only the functions $p:E\to E$
and $\phi\circ p:E\to E$ coincide. The function $\phi\circ p$ is gotten by evaluating the polynomial $q(x)=\sum_{i=0}^{N-1}a_ix^{2i}$ (recall that $\phi$ respects sums and fixes all the coefficients $a_i$. Comparing the coefficients of $p(x)$ and the projection $q^N(x)$ we see that

The Result: $p(x)\in R_N$ if and only if $a_i=a_j$ whenever $j\equiv 2i\pmod N$.

This leads us to the concept of a cyclotomic coset. The subset
$$C(i)=\{2^ji\in \Bbb{Z}_{N}\mid j\in\Bbb{N}\}\subseteq \Bbb{Z}_{N}$$
is called the cyclotomic coset of $i$ modulo $N$. The cyclotomic cosets form a partition of $\Bbb{Z}_{N}$ as they are the orbits of the action of the multiplicative group $G\le\Bbb{Z}_{N}^*$ generated by $\overline{2}$.

Corollary: The polynomial $p(x)=\sum_{i=0}^{N-1}a_ix^i\in R_N$ if and only if
$a_j=a_i$ whenever $j\in C(i)$.

Example: With $n=4, N=15$ we see that the cyclotomic cosets modulo $N$ are
\begin{aligned} C(0)&=\{0\},\\ C(1)&=\{1,2,4,8\},\\ C(3)&=\{3,6,9,12\},\\ C(5)&=\{5,10\},\\ C(7)&=\{7,11,13,14\}. \end{aligned}
Therefore the space of polynomias in $R_{15}$ is the linear span of
\begin{aligned} &1,\\ &x+x^2+x^4+x^8,\\ &x^3+x^6+x^9+x^{12},\\ &x^5+x^{10},\\ &x^7+x^{11}+x^{13}+x^{14}. \end{aligned}
You may recognize the polynomials with four terms as $tr(x)$, $tr(x^3)$ and $tr(x^7)$ respectively.