IMI Interdisciplinary Mathematics InstituteCollege of Arts and Sciences

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


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

© Interdisciplinary Mathematics Institute | The University of South Carolina Board of Trustees | Webmaster