Algebraic degrees of pseudo-Anosov stretch factors

The motivation for this paper is to justify a remark of Thurston that the algebraic degree of stretch factors of pseudo-Anosov maps on a surface $S$ can be as high as the dimension of the Teichm"uller space of $S$. In addition to proving this, we completely determine the set of possible algebraic degrees of pseudo-Anosov stretch factors on almost all finite type surfaces. As a corollary, we find the possible degrees of the number fields that arise as trace fields of Veech groups of flat surfaces homeomorphic to closed orientable surfaces. Our construction also gives an algorithm for finding a pseudo-Anosov map on a given surface whose stretch factor has a prescribed degree. One ingredient of the proofs is a novel asymptotic irreducibility criterion for polynomials.