Abstract
We consider random polynomials whose coefficients are independent and uniform on {-1, 1}. We prove that the probability that such a polynomial of degree n has a double root is o(n -2) when n+1 is not divisible by 4 and asymptotic to \(1/\sqrt 3 \) otherwise. This result is a corollary of a more general theorem that we prove concerning random polynomials with independent, identically distributed coefficients having a distribution which is supported on {-1, 0, 1} and whose largest atom is strictly less than \(\frac{{8\sqrt 3 }}{{\pi {n^2}}}\). In this general case, we prove that the probability of having a double root equals the probability that either -1, 0 or 1 are double roots up to an o(n -2) factor and we find the asymptotics of the latter probability.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
L. V. Ahlfors, Complex Analysis, third edition, McGraw-Hill Book Co., New York, 1978.
P. E. Blanksby and H. L. Montgomery, Algebraic integers near the unit circle, Acta Arithmetica 18 (1971), 355–369.
M.-C. Chang, private communication, October 27, 2014.
E. Dobrowolski, On a question of Lehmer and the number of irreducible factors of a polynomial, Acta Arithmetica 34 (1979), 391–401.
O. N. Feldheim and A. Sen, Double roots of random polynomials with integer coefficients, (2016), arXiv:1603.03811.
M. Filaseta and S. Konyagin, Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arithmetica 74 (1996), 191–205.
G. Freiman and S. Litsyn, Asymptotically exact bounds on the size of high-order spectral-null codes, Institute of Electrical and Electronics Engineers. Transactions on Information Theory 45 (1999), 1798–1807.
L. Kronecker, Zwei sätse über Gleichungen mit ganzzahligen Coefficienten, Journal für die Reine und Angewandte Mathematik 53 (1857), 173–175. See also Leopold Kronecker’s Werke, Vol. 1, Chelsea Publishing Co., New York, 1968, pp. 103–108.
G. Kuperberg, Sh. Lovett and R. Peled, Probabilistic existence of regular combinatorial structures, in STOC’ 12—Proceedings of the 2012 ACM Symposium on Theory of Computing, ACM, New York, 2012, pp. 1091–1106.
S. V. Konyagin, On the number of irreducible polynomials with 0, 1 coefficients, Acta Arithmetica 88 (1999), 333–350.
G. Kozma and O. Zeitouni, On common roots of random Bernoulli polynomials, International Mathematics Research Notices 18 (2013), 4334–4347.
D. H. Lehmer, Factorization of certain cyclotomic functions, Annals of Mathematics 34 (1933), 461–479.
P. Morandi, Field and Galois Theory, Graduate Texts in Mathematics, Vol. 167, Springer-Verlag, New York, 1996.
M. J. Mossinghoff, Polynomials with restricted coefficients and prescribed noncyclotomic factors, LMS Journal of Computation and Mathematics 6 (2003), 314–325.
Mathoverflow discussion, http://mathoverflow.net/questions/7969/irreduciblepolynomials-with-constrained-coefficients.
H. L. Montgomery and R. C. Vaughan, Multiplicative Number Theory. I. Classical Theory, Cambridge Studies in Advanced Mathematics, Vol. 97, Cambridge University Press, Cambridge, 2007.
A. M. Odlyzko and B. Poonen, Zeros of polynomials with 0, 1 coefficients, L’Enseignement Mathématique 39 (1993), 317–348.
A. Sárközi and E. Szemerédi, Über ein Problem von Erdős und Moser, Acta Arithmetica 11 (1965), 205–208.
C. L. Stewart, Algebraic integers whose conjugates lie near the unit circle, Bulletin de la Société Mathématique de France 106 (1978), 169–176.
N. R. Saxena and J. P. Robinson, Accumulator compression testing, IEEE Transactions on Computers C-35 (1986), 317–321.
Author information
Authors and Affiliations
Corresponding author
Additional information
Supported by an ISF grant and an IRG grant.
Supported by NSF grant 1406247.
Supported by an ISF grant and by the Herman P. Taubman professorial chair of Mathematics at WIS.
Rights and permissions
About this article
Cite this article
Peled, R., Sen, A. & Zeitouni, O. Double roots of random littlewood polynomials. Isr. J. Math. 213, 55–77 (2016). https://doi.org/10.1007/s11856-016-1328-3
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11856-016-1328-3