Skip to Main content Skip to Navigation

A tau-conjecture for Newton polygons

Abstract : One can associate to any bivariate polynomial P(X,Y) its Newton polygon. This is the convex hull of the points (i,j) such that the monomial X^i Y^j appears in P with a nonzero coefficient. We conjecture that when P is expressed as a sum of products of sparse polynomials, the number of edges of its Newton polygon is polynomially bounded in the size of such an expression. We show that this ''tau-conjecture for Newton polygons,'' even in a weak form, implies that the permanent polynomial is not computable by polynomial size arithmetic circuits. We make the same observation for a weak version of an earlier ''real tau-conjecture.'' Finally, we make some progress toward the tau-conjecture for Newton polygons using recent results from combinatorial geometry.
Document type :
Complete list of metadatas
Contributor : Pascal Koiran <>
Submitted on : Friday, August 9, 2013 - 4:53:14 PM
Last modification on : Tuesday, January 21, 2020 - 2:04:12 PM
Document(s) archivé(s) le : Sunday, November 10, 2013 - 3:00:15 AM


Files produced by the author(s)


  • HAL Id : ensl-00850791, version 1
  • ARXIV : 1308.2286


Pascal Koiran, Natacha Portier, Sébastien Tavenas, Stéphan Thomassé. A tau-conjecture for Newton polygons. 2013, pp.13. ⟨ensl-00850791v1⟩



Record views


Files downloads