Testing degenerate polynomials (Q429757)

In this paper two algorithms are given for deciding whether a given integer polynomial \(P(X)\) has a pair of distinct roots \(\alpha,\beta\) such that \(\alpha/\beta\) is a root of unity. If this happens the polynomial is called \textit{degenerate}. The first algorithm consists of computing the resultant \(Q(X)=\text{Res}_Y(P(XY),P(Y))\) , and then factoring \(Q\) ( over \(\mathbb Q\)? -- presumably to see whether it has any cyclotomic factors \(\neq X-1\).) How these factors are to be detected is not specified, although in an example at the end of Section 5.1 this is done by computing the gcd of a polynomial \(A\) and its reciprocal \(A^*\). Of course this method works only if all (self)-reciprocal factors of \(A\) are cyclotomic. (It does not distinguish between cyclotomic factors and reciprocal noncyclotomic factors.) A second method computes \(P_k(X)=\text{Res}_Y(P(Y),Y^k-X)\) for \(k\) up to a bound guaranteed to find \(\alpha,\beta\) such that \(\alpha/\beta\) is a \(k\)th root of unity, if there is such a \(k\). In this case \(P_k\) will have repeated roots, detected by computing \(\gcd(P_k,P_k')\).