The distance to an irreducible polynomial, II
Authors:
Michael Filaseta and Michael J. Mossinghoff
Journal:
Math. Comp. 81 (2012), 15711585
MSC (2010):
Primary 11C08; Secondary 11R09, 11Y40
Published electronically:
December 19, 2011
Fulltext PDF
Abstract 
References 
Similar Articles 
Additional Information
Abstract: P. Turán asked if there exists an absolute constant such that for every polynomial there exists an irreducible polynomial with and , where denotes the sum of the absolute values of the coefficients. We show that suffices for all integer polynomials of degree at most by investigating analogous questions in for small primes . We also prove that a positive proportion of the polynomials in have distance at least to an arbitrary irreducible polynomial.
 [1]
Pradipto
Banerjee and Michael
Filaseta, On a polynomial conjecture of Pál
Turán, Acta Arith. 143 (2010), no. 3,
239–255. MR 2652578
(2011g:11050), http://dx.doi.org/10.4064/aa14334
 [2]
A.
Bérczes and L.
Hajdu, Computational experiences on the
distances of polynomials to irreducible polynomials, Math. Comp. 66 (1997), no. 217, 391–398. MR 1377660
(97c:11035), http://dx.doi.org/10.1090/S0025571897008016
 [3]
A.
Bérczes and L.
Hajdu, On a problem of P. Turán concerning irreducible
polynomials, Number theory (Eger, 1996) de Gruyter, Berlin, 1998,
pp. 95–100. MR 1628834
(99f:11032)
 [4]
Kevin
Cattell, Frank
Ruskey, Joe
Sawada, Micaela
Serra, and C.
Robert Miers, Fast algorithms to generate necklaces, unlabeled
necklaces, and irreducible polynomials over 𝐺𝐹(2), J.
Algorithms 37 (2000), no. 2, 267–282. MR 1788836
(2002a:05006), http://dx.doi.org/10.1006/jagm.2000.1108
 [5]
Gilbert
Lee, Frank
Ruskey, and Aaron
Williams, Hamming distance from irreducible polynomials over
𝔽₂, 2007 Conference on Analysis of Algorithms, AofA 07,
Discrete Math. Theor. Comput. Sci. Proc., AH, Assoc. Discrete Math. Theor.
Comput. Sci., Nancy, 2007, pp. 169–180. MR 2509520
(2010i:94124)
 [6]
Michael
J. Mossinghoff, The distance to an irreducible polynomial,
Gems in experimental mathematics, Contemp. Math., vol. 517, Amer.
Math. Soc., Providence, RI, 2010, pp. 275–288. MR 2731083
(2012c:11069), http://dx.doi.org/10.1090/conm/517/10146
 [7]
A.
Schinzel, Reducibility of polynomials and covering systems of
congruences, Acta Arith. 13 (1967/1968),
91–101. MR
0219515 (36 #2596)
 [8]
A.
Schinzel, Reducibility of lacunary polynomials. II, Acta
Arith. 16 (1969/1970), 371–392. MR 0265323
(42 #233)
 [9]
V. Shoup, NTL: A library for doing number theory. www.shoup.net/ntl.
 [1]
 P. Banerjee and M. Filaseta, On a polynomial conjecture of Pál Turán, Acta Arith. 143 (2010), no. 3, 239255. MR 2652578
 [2]
 A. Bérczes and L. Hajdu, Computational experiences on the distances of polynomials to irreducible polynomials, Math. Comp. 66 (1997), no. 217, 391398. MR 1377660 (97c:11035)
 [3]
 A. Bérczes and L. Hajdu, On a problem of P. Turán concerning irreducible polynomials, Number Theory: Diophantine, Computational and Algebraic Aspects (Eger, Hungary, 1996) de Gruyter, Berlin, 1998, pp. 95100. MR 1628834 (99f:11032)
 [4]
 K. Cattell, F. Ruskey, J. Sawada, M. Serra, and C. R. Miers, Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over GF(2), J. Algorithms 37 (2000), no. 2, 267282. MR 1788836 (2002a:05006)
 [5]
 G. Lee, F. Ruskey, and A. Williams, Hamming distance from irreducible polynomials over , Discrete Math. Theor. Comput. Sci. Proc. AH (2008), 169180. MR 2509520 (2010i:94124)
 [6]
 M. J. Mossinghoff, The distance to an irreducible polynomial, Gems in Experimental Mathematics, Contemp. Math., vol. 517, Amer. Math. Soc., Providence, RI, 2010, pp. 275288. MR 2731083
 [7]
 A. Schinzel, Reducibility of polynomials and covering systems of congruences, Acta Arith. 13 (1967), 91101. MR 0219515 (36:2596)
 [8]
 A. Schinzel, Reducibility of lacunary polynomials, II, Acta Arith. 16 (1970), 371392. MR 0265323 (42:233)
 [9]
 V. Shoup, NTL: A library for doing number theory. www.shoup.net/ntl.
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC (2010):
11C08,
11R09,
11Y40
Retrieve articles in all journals
with MSC (2010):
11C08,
11R09,
11Y40
Additional Information
Michael Filaseta
Affiliation:
Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
Email:
filaseta@math.sc.edu
Michael J. Mossinghoff
Affiliation:
Department of Mathematics, Davidson College, Davidson, North Carolina 280356996
Email:
mimossinghoff@davidson.edu
DOI:
http://dx.doi.org/10.1090/S00255718201102555X
PII:
S 00255718(2011)02555X
Keywords:
Turán’s problem,
irreducible polynomial,
distance
Received by editor(s):
July 28, 2010
Received by editor(s) in revised form:
March 12, 2011
Published electronically:
December 19, 2011
Additional Notes:
Research of the second author supported in part by NSA grant number H982300810052.
Article copyright:
© Copyright 2011 American Mathematical Society
