## Irreducible testing of lacunary 0,1-polynomials

**A 2001 Preprint by
M. Filaseta and
D. Meade
**

- 2001:06
For $w(x)\in{C}[x]$ with $w(x)\not\equiv0$, define the reciprocal of $w(x)$ to be the polynomial

$$\tilde{w}(x)=x^{\deg{w}}w(\frac{1}{x}).$$

We refer to $w(x)$ as being reciprocal if $w(x)=\pm\tilde{w}(x)$ and as being non-reciprocal otherwise. Irreducibility will refer to irreducibility over the integers (so that, in particular, $\pm1$ are neither reducible nor irreducible). We define the non-reciprocal part of a monic polynomial $w(x)$ in $Z[x]$ to be $w(x)$ with its monic reciprocal irreducible factors removed. The purpose of this paper is to establish the following result:

There is an algorithm for determining whether the non-reciprocal part of $f(x)=\sum^r _ {j=0}x^{d _ j}$, with $0=d _ 0<d _ 1<d _ 2<\cdots<d _ r=n,r\geq2$, and $n\geq2$, is irreducible that runs in time $\ll2^rr\log{r}\log{n}$. Furthermore, if the non-reciprocal part of $f(x)$ is reducible, then the algorithm determines a non-trivial factor of $f(x)$ expressed in the form $\gcd(f(x),w(x))$ where $w(x)=\sum^r _ {j=0}x^{k _ j}\in{Z}[x]$ for some integers $k _ j$ satisfying $0=k _ 0<k _ 1<k _ 2<\cdots<k _ r=n$.