|
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
Posted:
December 19, 2011
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.
References
- [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/aa143-3-4
- [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/S0025-5718-97-00801-6
- [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)
- [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.
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 28035-6996
Email:
mimossinghoff@davidson.edu
DOI:
http://dx.doi.org/10.1090/S0025-5718-2011-02555-X
PII:
S 0025-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
Posted:
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
|