Random polynomials with 0-1 coefficients are irreducible
Let $p_n$ be the probability that $1 + a_1 x + \dots + a_{n-1} x^{n-1} + x^n$ is irreducible, the $a_i$ being independent and uniform on $\{0, 1\}$. Unconditionally Konyagin showed $p_n \gg 1/\log n$; Breuillard and Varjú proved $p_n \to 1$ assuming the generalised Riemann hypothesis; and Bary-Soroker, Koukoulopoulos and Kozma proved the analogue for coefficients uniform on $\{0, 1, \dots, M\}$ with $M \ge 34$.
Problem. Does $p_n \to 1$?
Source: A. M. Odlyzko and B. Poonen, Zeros of polynomials with 0, 1 coefficients, Enseign. Math. 39 (1993). Listed as Problem 93 in B. Green, 100 open problems (version of January 2026).
Imported from people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf.
Classification
- Primary
- NT — Number Theory
- Secondary
- PR
- Keywords
- 0-1 polynomials, irreducibility, Odlyzko–Poonen conjecture, random polynomials
References
@article{odlyzko1993zeros,
author = {Odlyzko, Andrew M. and Poonen, Bjorn},
title = {Zeros of polynomials with $0,1$ coefficients},
journal = {L'Enseignement Math{\'e}matique (2)},
volume = {39},
number = {3-4},
pages = {317--348},
year = {1993}
}
@article{konyagin1999irreducible,
author = {Konyagin, Sergei V.},
title = {On the number of irreducible polynomials with $0,1$ coefficients},
journal = {Acta Arithmetica},
volume = {88},
number = {4},
pages = {333--350},
year = {1999},
doi = {10.4064/aa-88-4-333-350}
}
@article{breuillard2019varju,
author = {Breuillard, Emmanuel and Varj{\'u}, P{\'e}ter P.},
title = {Irreducibility of random polynomials of large degree},
journal = {Acta Mathematica},
volume = {223},
number = {2},
pages = {195--249},
year = {2019},
doi = {10.4310/ACTA.2019.v223.n2.a1}
}
@article{barysoroker2023general,
author = {Bary-Soroker, Lior and Koukoulopoulos, Dimitris and Kozma, Gady},
title = {Irreducibility of random polynomials: general measures},
journal = {Inventiones Mathematicae},
volume = {233},
number = {3},
pages = {1041--1120},
year = {2023},
doi = {10.1007/s00222-023-01193-6}
}
@misc{kogler2026odlyzko,
author = {Kogler, Constantin},
title = {The {O}dlyzko--{P}oonen conjecture on irreducibility of random polynomials},
year = {2026},
eprint = {2609.26771},
archivePrefix = {arXiv}
}
@misc{green100open,
author = {Green, Ben},
title = {100 open problems},
howpublished = {\url{https://people.maths.ox.ac.uk/greenbj/papers/open-problems.pdf}},
note = {Problem 93; version of January 2026, most recent update December 2025},
year = {2026}
}
Resolution claims
The Odlyzko-Poonen conjecture states that a monic polynomial of constant coefficient $1$ and with remaining coefficients chosen independently and uniformly from $\{0,1 \}$ is irreducible over the rational numbers with probability tending to one as the degree tends to infinity. We prove the Odlyzko-Poonen conjecture unconditionally.
Status history
| When | Change | By | Reason |
|---|---|---|---|
| 2026-10-29 | Needs verification → Solution claimed | — | Recorded here: arXiv:2609.26771v2. |
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-01045, "Random polynomials with 0-1 coefficients are irreducible", clopen.solutions.