×

Double roots of random Littlewood polynomials. (English) Zbl 1456.60129

Summary: 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 \(\frac{8\sqrt 3}{\pi n^2}\) 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 \(1/\sqrt 3\). 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.

MSC:

60G99 Stochastic processes
05E05 Symmetric functions and generalizations
11C08 Polynomials in number theory

Software:

MathOverflow

References:

[1] L. V. Ahlfors, Complex Analysis, third edition, McGraw-Hill Book Co., New York, 1978.
[2] P. E. Blanksby and H. L. Montgomery, Algebraic integers near the unit circle, Acta Arithmetica 18 (1971), 355-369. · Zbl 0221.12003
[3] M.-C. Chang, private communication, October 27, 2014.
[4] E. Dobrowolski, On a question of Lehmer and the number of irreducible factors of a polynomial, Acta Arithmetica 34 (1979), 391-401. · Zbl 0416.12001
[5] O. N. Feldheim and A. Sen, Double roots of random polynomials with integer coefficients, (2016), arXiv:1603.03811. · Zbl 1395.60011
[6] M. Filaseta and S. Konyagin, Squarefree values of polynomials all of whose coefficients are 0 and 1, Acta Arithmetica 74 (1996), 191-205. · Zbl 0854.11015
[7] 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. · Zbl 0958.94041 · doi:10.1109/18.782100
[8] 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. · ERAM 053.1389cj · doi:10.1515/crll.1857.53.173
[9] 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. · Zbl 1286.60027
[10] S. V. Konyagin, On the number of irreducible polynomials with 0, 1 coefficients, Acta Arithmetica 88 (1999), 333-350. · Zbl 0931.11007
[11] G. Kozma and O. Zeitouni, On common roots of random Bernoulli polynomials, International Mathematics Research Notices 18 (2013), 4334-4347. · Zbl 1316.26016
[12] D. H. Lehmer, Factorization of certain cyclotomic functions, Annals of Mathematics 34 (1933), 461-479. · Zbl 0007.19904 · doi:10.2307/1968172
[13] P. Morandi, Field and Galois Theory, Graduate Texts in Mathematics, Vol. 167, Springer-Verlag, New York, 1996. · Zbl 0865.12001
[14] M. J. Mossinghoff, Polynomials with restricted coefficients and prescribed noncyclotomic factors, LMS Journal of Computation and Mathematics 6 (2003), 314-325. · Zbl 1134.11319 · doi:10.1112/S1461157000000474
[15] Mathoverflow discussion, http://mathoverflow.net/questions/7969/irreduciblepolynomials-with-constrained-coefficients.
[16] 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. · Zbl 1142.11001
[17] A. M. Odlyzko and B. Poonen, Zeros of polynomials with 0, 1 coefficients, L’Enseignement Mathématique 39 (1993), 317-348. · Zbl 0814.30006
[18] A. Sárközi and E. Szemerédi, Über ein Problem von Erdős und Moser, Acta Arithmetica 11 (1965), 205-208. · Zbl 0134.27801
[19] 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. · Zbl 0396.12002
[20] N. R. Saxena and J. P. Robinson, Accumulator compression testing, IEEE Transactions on Computers C-35 (1986), 317-321. · doi:10.1109/TC.1986.1676764
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.