Test for Divisibility by

Cyclotomic Polynomials

Places to go on this page:

Information About This Page

This interactive page has been made possible by the consent of Waterloo Maple. The current version of the program are written using Maple 8 and are being run on a SUN Ultra 1 workstation (using solaris 2.5.1) in the Mathematics Department at the University of South Carolina. We express our gratitude to the staff of Waterloo Maple who graciously aided in improvements to the interface.

A Maplet interface to the algorithms is currently under development. A prototype will soon be available via our MapleNet server at the URL http://maple.math.sc.edu/maplenet/meade/Cyclotomic.html. If you experience any problems with this Maplet, please send e-mail to Doug Meade.

This page can be used to determine whether a given polynomial with integer coefficients has a cyclotomic divisor. To begin the program, choose one of the options "user-specified" or "randomly-selected" below. If you choose "user-specified," type in a user-defined polynomial to replace the example indicated. If you choose the "randomly-selected" option, indicate a bound for the number of non-zero terms, a bound for the degree, and a bound for the absolute value of the coefficients. These will be used to select a random polynomial (based on MAPLE's built-in randpoly command) with non-zero constant term. The value of the polynomial will be displayed in the output and not on this page. To determine if the polynomial (user-specified or randomly-selected) has a cyclotomic factor, click on the "Perform Test" button and wait for the output.

How does one interpret the output? The value "true" will be returned if the polynomial, say f(x), does have a cyclotomic factor. The value "false" will be returned otherwise. In the case of a true value, a statement will be given indicating an integer m such that f(x) is divisible by the mth cyclotomic polynomial. If f(x) is divisible by more than one cyclotomic polynomial, only one such m is given; it will NOT necessarily be the least such m.

What kind of polynomial can the algorithm handle? The program will work for any polynomial f(x) with integer coefficients. As indicated in the example below, f(x) can have large degree. In general, the greater the degree of f(x) is, the longer the running time will be; however, the degree does not affect the running time much (whatever that means). Similarly, the size of the coefficients of f(x) will affect the running time only slightly. The greatest contribution to the running time comes from the number of non-zero terms in f(x). The algorithm can easily handle polynomials with 100 non-zero terms and say degree 1000000 and coefficients with absolute value bounded by 1000000 (this typically takes between 2 and 2.5 MAPLE CPU minutes).

The Program

How the polynomial is created:
User-defined polynomial:
Bound on number of non-zero terms:
(for randomly-selected polynomials)
Bound on degree:
(for randomly-selected polynomials)
Bound on coefficients:
(for randomly-selected polynomials)

Background For This Page

This interactive page was developed by Michael Filaseta and Douglas Meade. The algorithm used here is based on work in progress by Filaseta and Schinzel [1] where it is shown how to determine whether a polynomial with integer coefficients has a cyclotomic factor. The algorithm described in [1] is itself based largely on a paper of Mann [2]. Though a running version of the program apparently exists, further improvements are being pursued prior to public release of the code. We anticipate making the code available at this location shortly. As we are using the MAPLE language, access to MAPLE will be necessary to run the downloaded programs.

References and Downloads

The following includes references and current downloadable programs. Presently there are no downloads. More will be listed as it becomes available (and complete).

[1] M. Filaseta and A. Schinzel, On testing the divisibility of lacunary polynomials by cyclotomic polynomials, in preparation.

[2] H. B. Mann, On linear relations between roots of unity, Mathematika, 12 (1965), 107-117.

Another Interactive Page: Test the Irreducibility of 0-1 Polynomials

Please send comments to: filaseta@math.sc.edu or meade@math.sc.edu.
Last Modified: 30 Jan 2004