Journal of Integer Sequences, Vol. 9 (2006), Article 06.3.3

Sequences of Reducible {0,1}-Polynomials Modulo a Prime

Judith Canner
Department of Statistics
North Carolina State University
Raleigh, North Carolina 27695-8203

Lenny Jones and Joseph Purdom
Department of Mathematics
Shippensburg University
Shippensburg, Pennsylvania 17257

Abstract: Construct a recursive sequence of polynomials, staring with 1, in the following way. Each new term in the sequence is determined by adding the smallest power of x larger than the degree of the previous term, such that the new polynomial is reducible over the rationals. Filaseta, Finch and Nicol have shown that this sequence is finite. In this paper we investigate variations of this problem over a finite field. In particular, we allow the starting polynomial to be any {0,1}-polynomial with nonzero constant term, and we allow the exponent on the power of x added at each step to be chosen from the set of multiples of a fixed positive integer k. Among our results, we show that these sequences are always infinite. We develop necessary and sufficient conditions on k and the characteristic p of the field, so that the sequence starting with 1 uses every multiple of k as an exponent in its construction. In addition, we prove for k=1 and p >=5 that there exists a {0,1}-polynomial f such that the sequence starting with f uses every positive integer larger than the degree of f as an exponent in its construction.

Full version:  pdf,    dvi,    ps,    latex    

Received December 19 2005; revised version received July 19 2006. Published in Journal of Integer Sequences July 19 2006.

Return to Journal of Integer Sequences home page