How many Boolean polynomials are irreducible?
Yaroslav Nikolaevich Shitov · International Journal of Algebra and Computation · 2014
We present a number of new results on the multiplicative structure of univariate polynomials over the Boolean and tropical semirings. We answer the question asked by Kim and Roush in 2005 by proving that almost all Boolean polynomials with nonzero constant term are irreducible. We also give a lower bound for the number of reducible polynomials, and we discuss the related issues for polynomials over tropical semiring.