The distance to an irreducible polynomial, II

Authors:
Michael Filaseta and Michael J. Mossinghoff

Journal:
Math. Comp. **81** (2012), 1571-1585

MSC (2010):
Primary 11C08; Secondary 11R09, 11Y40

DOI:
https://doi.org/10.1090/S0025-5718-2011-02555-X

Published electronically:
December 19, 2011

MathSciNet review:
2904591

Full-text 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]**P. Banerjee and M. Filaseta,*On a polynomial conjecture of Pál Turán*, Acta Arith.**143**(2010), no. 3, 239-255. 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, 391-398. 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. 95-100. 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, 267-282. 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), 169-180. 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. 275-288. MR**2731083****[7]**A. Schinzel,*Reducibility of polynomials and covering systems of congruences*, Acta Arith.**13**(1967), 91-101. MR**0219515 (36:2596)****[8]**A. Schinzel,*Reducibility of lacunary polynomials, II*, Acta Arith.**16**(1970), 371-392. MR**0265323 (42:233)****[9]**V. Shoup,*NTL: A library for doing number theory*. www.shoup.net/ntl.

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 28035-6996

Email:
mimossinghoff@davidson.edu

DOI:
https://doi.org/10.1090/S0025-5718-2011-02555-X

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 H98230-08-1-0052.

Article copyright:
© Copyright 2011
American Mathematical Society