Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



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
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 $ C$ such that for every polynomial $ f\in \mathbb{Z}[x]$ there exists an irreducible polynomial $ g\in \mathbb{Z}[x]$ with $ \deg (g)\leq \deg (f)$ and $ L(f-g)\leq C$, where $ L(\cdot )$ denotes the sum of the absolute values of the coefficients. We show that $ C=5$ suffices for all integer polynomials of degree at most $ 40$ by investigating analogous questions in $ \mathbb{F}_p[x]$ for small primes $ p$. We also prove that a positive proportion of the polynomials in $ \mathbb{F}_2[x]$ have distance at least $ 4$ to an arbitrary irreducible polynomial.

References [Enhancements On Off] (What's this?)

  • [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 $ \mathbb{F}_2$, 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.

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

Michael J. Mossinghoff
Affiliation: Department of Mathematics, Davidson College, Davidson, North Carolina 28035-6996

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

American Mathematical Society