The Odlyzko-Poonen Conjecture on Irreducibility of Random Polynomials
The Odlyzko-Poonen conjecture asserts that a random monic polynomial with constant coefficient 1 and other coefficients uniform in {0,1} is irreducible over Q with probability tending to one as the degree grows. Previous proofs were conditional on GRH or covered only other coefficient distributions.
Any factorization P=AB yields a twin polynomial Q=AB* in the same family satisfying QQ*=PP*. The core step bounds the probability of a nontrivial twin congruence QQ* ≡ PP* mod 4. It works over F_2 and conditions on sums of opposite coefficients, revealing coefficients one at a time. Reciprocal non-cyclotomic factors are controlled with a separation argument adapted from Breuillard-Varjú. The full proof and the required prior results are formalized in Lean.
The conjecture is proved unconditionally, with P(reducible) = sqrt(2/(πn)) + O(n^{-1}). The Breuillard-Varjú decomposition result is also made unconditional, with the probability strengthened to an almost exponential bound.
