The distance to an irreducible polynomial, II
HTML articles powered by AMS MathViewer
- by Michael Filaseta and Michael J. Mossinghoff PDF
- Math. Comp. 81 (2012), 1571-1585 Request permission
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
- Pradipto Banerjee and Michael Filaseta, On a polynomial conjecture of Pál Turán, Acta Arith. 143 (2010), no. 3, 239–255. MR 2652578, DOI 10.4064/aa143-3-4
- 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, DOI 10.1090/S0025-5718-97-00801-6
- 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
- Kevin Cattell, Frank Ruskey, Joe Sawada, Micaela Serra, and C. Robert Miers, Fast algorithms to generate necklaces, unlabeled necklaces, and irreducible polynomials over $\textrm {GF}(2)$, J. Algorithms 37 (2000), no. 2, 267–282. MR 1788836, DOI 10.1006/jagm.2000.1108
- Gilbert Lee, Frank Ruskey, and Aaron Williams, Hamming distance from irreducible polynomials over $\Bbb F_2$, 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
- 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, DOI 10.1090/conm/517/10146
- A. Schinzel, Reducibility of polynomials and covering systems of congruences, Acta Arith. 13 (1967/68), 91–101. MR 219515, DOI 10.4064/aa-13-1-91-101
- A. Schinzel, Reducibility of lacunary polynomials. II, Acta Arith. 16 (1969/70), 371–392. MR 265323, DOI 10.4064/aa-16-4-371-392
- V. Shoup, NTL: A library for doing number theory. www.shoup.net/ntl.
Additional Information
- Michael Filaseta
- Affiliation: Department of Mathematics, University of South Carolina, Columbia, South Carolina 29208
- MR Author ID: 66800
- Email: filaseta@math.sc.edu
- Michael J. Mossinghoff
- Affiliation: Department of Mathematics, Davidson College, Davidson, North Carolina 28035-6996
- MR Author ID: 630072
- ORCID: 0000-0002-7983-5427
- Email: mimossinghoff@davidson.edu
- 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.
- © Copyright 2011 American Mathematical Society
- 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
- MathSciNet review: 2904591