We show that if f(x1,...,xn) is a polynomial with s monomials and g(x1,...,xn) divides f then g has at most max(s^O(log s log log s), d^O(log d)) monomials, where d is a bound on the individual degrees of f. This answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds in this case. The proof works over any field and uses a new constructing of a polytope in R^k that is described by a hyperplane mod p and has >> 2^k vertices.
(Joint work with Rafael Oliveira)
Copyright. All Rights Reserved.