Seminars & Colloquia Calendar
Are factors of Sparse polynomials sparse?
Vishwas Bhargava, Rutgers
Location: Hill 705
Date & time: Monday, 25 February 2019 at 2:00PM - 3:00PM
|
Abstract: The main question we will discuss is, how number of terms of a polynomial(a.k.a Sparsity) relates to number of terms of its factors. This is a fundamental problem which lies at the intersection of Algebra and Combinatorics and attracted attention from several authors, including Erdös, Freud, Rényi, Schinzel and Verdenius. We show a quasi-polynomial sparsity bound for factors of sparse polynomials of bounded individual degree. In particular, we show if f is an s-sparse polynomial in n variables, with individual degrees of its variables bounded by d, then the sparsity of each factor of f is bounded by s^{O({d^2log{n}})}. This is the first nontrivial bound on factor sparsity for d >2. Our sparsity bound uses techniques from convex geometry, such as the theory of Newton polytopes and an approximate version of the classical Caratheodory's Theorem. Our work addresses and partially answers a question of von zur Gathen and Kaltofen (JCSS 1985) who asked whether a quasi-polynomial bound holds for the sparsity of factors of sparse polynomials. Joint work with Shubhangi Saraf and Ilya Volkovich. |
