Consider unitary polynomials of degree $n$ over $GF(2)$. That is, polynomials of the form $p(x) = \sum_{i=0}^n a_i x^i$ where $a_i\in GF(2)$ and $a_n=1$.
Can we always find such an irreducible polynomial $p(x)$ of degree $n$ where $\textrm{degree}(p(x)-x^n)\leq n/2$?
Example: $p(x)=1+x^2+x^3+x^5+x^{400}$ is an irreducible polynomial where $\textrm{degree}(p(x)-x^n)=5\leq 400/2$.
Further question: If I assume that $n$ is sufficiently large, say $n\geq 32$, is a tighter bound possible (e.g., $\textrm{degree}(p(x)-x^n)\leq n/4$)?
Best Answer
I think (but I could easily be wrong), that this follows, at least for many degrees (in the stronger form also conjectured by Noam and Gjergji) from the results of S. D. Cohen as in MR2092633 (2005g:11245) Cohen, Stephen D.(4-GLAS) Primitive polynomials over small fields. Finite fields and applications, 197–214, Lecture Notes in Comput. Sci., 2948, Springer, Berlin, 2004. 11T06 (11T30 11T71)
If you look at the math review, you will see that he shows that we can find a "primitive" polynomial over $F_q$ (primitive = irreducible AND every root is a primitive root in the appropriate $F_{q^k}.$) with the first $m$ coefficients prescribed if \
$q^{n/2-m} > m W(q^n-1),$ where $W(j)$ denotes the number of square-free divisors of the integer $j.$