# Can we always find such an irreducible polynomial of degree n where degree(p(x)-x^n)<= n/2?

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$)?

• For large $n$, about $1/n$ of all degree-$n$ polynomials are irreducible, so one expects that $\deg p$ need be no larger than $O(\log(n))$. But actually proving such a result must be very hard; even a much weaker bound like $\deg p < \theta n$ for some $\theta < 1$ might be out of reach. – Noam D. Elkies Nov 23 '11 at 16:39
• I believe the best bound is expected to be $O(\log n)$. Do you care about existence, or also a way of constructing such polynomials? – Gjergji Zaimi Nov 23 '11 at 16:42
• (All polynomials of degree $n$ over $GF(2)$ are unitary, except for the zero polynomial!) – Mariano Suárez-Álvarez Nov 23 '11 at 17:13
• – Felipe Voloch Nov 23 '11 at 18:13
• As noted in W.Zudilin's answer, the polynomial $1+x^2+x^5+x^{400}$ is manifestly reducible over the 2-element field, because it vanishes at $x=1$. F.Voloch guesses in his comment to that answer that there's a missing term, and that seems correct because $1+x^2+x^3+x^5+x^{400}$ is irreducible and is the unique example for $n=400$ and $\deg(p)<8$ (for degree $8$ there's also $1 + x^2 + x^3 + x^6 + x^7 + x^8 + x^{400}$). – Noam D. Elkies Nov 24 '11 at 6:05

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

• S. Cohen's result are the best available but they do not prove what the OP wants, but it gets close, something like $m < n/2 + O(\log n)$. As mentioned in the comments, on probabilistic grounds one expects much better results, but even the OP's question is open. See mathoverflow.net/questions/39100/… – Felipe Voloch Nov 23 '11 at 18:00
• Well, correct me if I am wrong, but if, for example, $2^n-1$ has few divisors, then you get the $O(\log n)$ bound. Now, no one knows that there is an infinity of Mercenne primes, but maybe it IS known that there is an infinity of numbers of the form $2^n-1$ with $o(2^n)$ divisors? – Igor Rivin Nov 23 '11 at 18:08
• If you only want the irreducible polynomials for infinitely many degrees, then $x^{2\cdot3^k}+x^{3^k}+1$ does the job. – Emil Jeřábek Nov 23 '11 at 18:17
• @Igor: (This is a well-known fact.) 2 is a generator of $(\mathbb Z/(9))^\*$, hence of every $(\mathbb Z/(3^{k+1}))^\*$. It follows that the primitive $3^{k+1}$th root of unity is in $\mathbb F_{2^d}$ only when $2\cdot3^k\mid d$, hence its minimal polynomial has degree $\varphi(3^{k+1})$. In other words, the cyclotomic polynomial $\Phi_{3^{k+1}}$ is irreducible over $\mathbb F_2$. – Emil Jeřábek Nov 23 '11 at 18:50
• Not to insist on this on principle or make the answer look bad, but it might be confusing for somebody: this can not contrary to what is suggested in the answer, no matter how few divisors 2^n - 1 has!, yield what the OP asked for (except perhaps for finitely many small n), let alone the stronger versions mentioned by NE and GZ. (Sorry for the comment noise; my earlier similar comment did actually not say what I wanted to say though the intent might have been clear). – user9072 Nov 24 '11 at 21:09

I suppose this question is the F_2[t] analogue of the question "does the interval [N, N^^{1/2}] always contain a prime?" After all, you are asking about the set of polynomials at infinity-adic distance less than 2^{n/2} from a fixed polynomial of size 2^n; this is the polynomial version of an "interval."

This is pretty close to Legendre's conjecture, which is still open. On the other hand, Cramer proved under RH (which you have in F_2[t] case) that there is always a prime between N and cN^{1/2} log N; so I would see if you can adapt his proof to get the bound you want with the bound n/2 replaced by n/2 + log n.

I leave my earlier post below where I mistakenly understood the original problem because of a bad illustrative example given there. Here I only indicate the explicit formula for the number $N_ m(p)$ of monic polynomials of exact degree $m$ irreducible over $GF(p)$: $$N_m(p)=\frac1m\sum_{d\mid m}\mu(d)p^{m/d}.$$ This formula is again from Prasolov's Polynomials, and it seems to be absent in other posts and comments.

I assume that the irreducibility is discussed over $\mathbb Z$, otherwise $x^{400}+x^5+x^2+1$ has zero $x=1$ in $GF(2)$.

Victor Prasolov in Section 8 of his book Polynomials discusses the irreducibility of trinomials and quadrinomials, mostly based on the work [W. Ljunggren, On the irreducibility of certain trinomials and quadrinomials, Math. Scand. 8 (1960), 65--70]. One of the results from there is as follows.

Theorem. Let $n\ge2m$, $d=\text{gcd}(n,m)$, $n_1=n/d$ and $m_1=m/d$. Then the polynomial $$g(x)=x^n+\epsilon x^m+\epsilon', \quad\text{where}\ \epsilon,\epsilon'\in\lbrace\pm1\rbrace,$$ is irreducible except for the following cases in which $n_1+m_1\equiv0\pmod3$:

(a) $n_1$ and $m_1$ are odd and $\epsilon=1$;

(b) $n_1$ is even and $\epsilon'=1$;

(c) $m_1$ is even and $\epsilon=\epsilon'$.

In all three cases (a)--(c), $g(x)$ is a product of a certain irreducible polynomial and $x^{2d}+\epsilon^m{\epsilon'}^nx^d+1$.

Corollary. If $n\not\equiv2\pmod3$, then $x^n+x+1$ is irreducible.

If $n\equiv2\pmod3$, then $x^n+x^2+1$ is irreducible.

In other words, there is an irreducible degree $n$ polynomial $g(x)$ of the wanted form such that $\deg(g(x)-x^n)\le2$, and this bound cannot be further improved.

• I think the discussion above is all over $GF(2)$ and the polynomial of degree 400 is probably missing a term. – Felipe Voloch Nov 24 '11 at 0:10
• Your guess seems to be correct: there's a unique choice of $p$ with $\deg(p)<8$ that yields an irreducible $x^{400}+p$ over the 2-element field, and that is $1 + x^2 + x^3 + x^5$, so apparently there's an $x^3$ term missing. – Noam D. Elkies Nov 24 '11 at 6:06
• @Felipe @Elkies Yes, sorry about this. I definitively meant to write $1+x^2+x^3+x^5+x^{400}$. My bad. I fixed the statement. – lemire Nov 24 '11 at 16:02