The Tropical Division Problem and the Minkowski Factorization of Generalized Permutahedra

Given two tropical polynomials f, g on ℝn, we provide a characterization for the existence of a factorization f= h odot g and the construction of h. As a ramification of this result we obtain a parallel result for the Minkowski factorization of polytopes. Using our construction we show that for any given polytopal fan there is a polytope factorization basis, i.e. a finite set of polytopes with respect to which any polytope whose normal fan is refined by the original fan can be uniquely written as a signed Minkowski sum. We explicitly study the factorization of polymatroids and their generalizations, Coxeter matroid polytopes, and give a hyperplane description of the cone of deformations for this class of polytopes.