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. The current version can be accessed via our MapleNet server at the URL http://maple.math.sc.edu/maplenet/meade/Irreduc.html. If you experience any problems with this Maplet, please send e-mail to Doug Meade.
This page is set-up to test the irreducibility of polynomials f(x) having each coefficient 0 or 1. To use this page, begin by selecting one of the following three tests under "Test to be conducted". (Click and drag to your choice of tests.)
irreduc01: This is the main program on the page. It determines whether a given 0-1 polynomial f(x) is irreducible. The program works best for lacunary polynomials. In particular, the more non-zero terms the polynomial has, the slower the performance. On the other hand, the degree of f(x) can be somewhat large. The program can easily handle a 0-1 polynomial of degree 20000 having say 50 non-zero terms (this typically takes between 2 and 2.5 MAPLE CPU minutes).
irreduc and irreduc01: The program irreduc is MAPLE's built-in irreducibility test, and this selection does as it suggests. It checks the irreducibility of f(x) using both algorithms, outputs the results, and indicates the time it took to do each computation. Due to the use of irreduc, this test is only feasible to use when f(x) has relatively small degree; you will probably not want to wait for the results if f(x) has degree 1000 or so. This option is included for comparison purposes. To clarify, however, we emphasize that MAPLE's irreduc is an irreducibility test for general polynomials f(x); irreduc01 is written specifically to handle 0-1 polynomials and nothing more.
irreduc01NR: This is the main subprogram of irreduc01. It does not test the irreducibility of f(x) but instead tests the irreducibility of the non-reciprocal part of f(x). The non-reciprocal part of f(x) is defined as follows. A polynomial f(x) having coefficients 0 and 1 is said to be reciprocal if f(x) = xdeg f f(1/x). The non-reciprocal part of f(x) is f(x) with its reciprocal irreducible factors having positive leading coefficient removed. For typical polynomials, one can expect that f(x) and its non-reciprocal part are the same (this, however, is not really the case when one considers 0-1 polynomials with a limited number of non-zero terms). This program runs exceptionally well for lacunary polynomials with not too many non-zero terms. One can even try f(x) of degree 10100 if one wants here, though the program does take slightly longer as the degree of f(x) increases.
After selecting the test to be conducted, you have an option of typing in a polynomial of your choice or testing a random polynomial. For the former, choose the "user-specified" option and type in the polynomial following the example indicated . For the latter, choose the "randomly-selected" option and indicate the number of non-zero terms and a bound on the degree. The random polynomial will appear after the program is run in the displayed output. To clarify, the random polynomial will have constant term 1 (if you want to test the irreducibility of polynomials divisible by x, you will have to use the user-specified option) and the remaining exponents will be determined randomly less than or equal to the bound given for the degree. If two identical exponents are selected at random, the random polynomial will have fewer non-zero terms than you have indicated (only one term for each exponent is used). The random polynomial options will not affect the field containing the user-defined polynomial. After making the above choices, choose "Perform Test" and wait for the results or choose "Reset Form" and start again.
The main theorem of Schinzel in [4] (also see [2]) implies that it is possible to determine whether the non-reciprocal part (see definition above) of a polynomial f(x) is irreducible in running time that depends only logarithmically on the degree of f(x). For this result, f(x) can have arbitrary integer coefficients. The running time of such an algorithm may however depend poorly on the Euclidean norm of f(x) or the number of non-zero terms of f(x). The programs irreduc01 and irreduc01NR represent joint work by Michael Filaseta and Douglas Meade (see [1]). The algorithms are partially based on work in [2] (which itself is based on work of Ljunggren [3] and the forementioned work of Schinzel [4]) and will be described in further detail in a forthcoming paper that will be made available at this site. Though running versions of the programs apparently exist, further improvements are being pursued prior to public release of the code. We are also in the process of altering the code so that if the proper infolevel is set in the downloaded version, then a non-trivial factor is given for any reducible f(x). When the programs are complete, we will make them available to download at this location. As we are using the MAPLE language, access to MAPLE will be necessary to run the downloaded programs.
The following includes the current references and downloadable programs. Presently there are no downloads. More will be listed as it becomes available (and complete).
[1] M. Filaseta and Douglas Meade, Irreducibility testing of lacunary 0,1-polynomials, preprint. [2] M. Filaseta, On the Factorization of Polynomials with Small Euclidean Norm, preprint. [3] W. Ljunggren, On the irreducibility of certain trinomials and quadrinomials, Math. Scand., 8 (1960), 65-70. [4] A. Schinzel, Reducibility of lacunary polynomials I, Acta Arith., 16 (1969/70), 123-159.
Another Interactive Page: Determine if a Polynomial has a Cyclotomic Factor