$\newcommand\KK{\mathbb{K}}$Let $\KK$ be any field and $f\in\KK[x_1,\dotsc,x_n]$ be a polynomial. Its support $S_f$ is the set $\{(e_1,\dotsc, e_n) : x_1^{e_1}\dotsb x_n^{e_n}$ has a nonzero coefficient in $f\}$, and its Newton polytope $P_f$ is the convex hull of its support.

Ostrowski [1] proved that if there exist $g,h\in\KK[x_1,\dotsc,x_n]$ such that $f=g\cdot h$, then $P_f=P_g+P_h$, where $+$ represents the Minkowski sum.

It happens that the support, hence the Newton polytope, of a polynomial is not changed when the nonzero coefficients of the polynomial are modified, as soon as none of them is set to zero.

Question. Suppose that the Newton polytope $P_f$ of some polynomial $f$ can be written as $Q+R$ where $Q$ and $R$ are convex polytopes with integral coordinates. Are there polynomials $\tilde f$, $g$, $h\in\KK[x_1,\dotsc,x_n]$ such that $\tilde f=g\cdot h$, $P_{\tilde f}=P_f$, $P_g=Q$ and $P_h=R$?


  1. The question may be asked by allowing $\tilde f$, $g$ and $h$ to actually live in $\bar\KK[x_1,\dotsc,x_n]$ where $\bar\KK$ is an algebraic closure of $\KK$.
  2. One can state Ostrowski's result a bit more precisely: Let $S_f$, $S_g$ and $S_h$ be the respective supports of $f$, $g$ and $h$, and assume that $f=g\cdot h$. Then $S_f \subseteq S_g+S_h$, and the missing points in $S_f$ are not vertices of the convex hull of $S_g+S_h$. This yields the following new question: Given sets of points $Q$ and $R$, such that $S_f\subseteq Q+R$ and the missing points are not vertices of the convex hull of $Q+R$, can we find $\tilde f$, $g$ and $h$ such that $\tilde f=g\cdot h$, $S_{\tilde f}=S_f$, $S_g=Q$ and $S_h=R$?

[EDIT] Gjergji Zaimi answered my two questions. Based on his answers, I realize that what I had in mind is stronger that what I described in my questions. Let me formulate the stronger question:

Stronger question. Given a set of points $P\in\mathbb N^n$, let us say that it is decomposable if there exist $Q,R\in\mathbb N^n$ such that $P\subseteq Q+R$ where the missing points are not vertices of the convex hull of $Q+R$. Given a decomposable $P$, is there at least one such decomposition $P\subseteq Q+R$ such that there exist $g,h\in\KK[x_1,\dotsc,x_n]$, such that $P=P_{g\cdot h}$, $Q=P_g$ and $R=P_h$? Again, the question may depend on $\KK$ and I am interested in the dependence on $\KK$ if there is such a dependence.

[1] A. M. Ostrowski, "On multiplication and factorization of polynomials, I. Lexicographic ordering and extreme aggregates of terms", Aequationes Math. 13 (1975), 201-228.

  • $\begingroup$ I would comment but not enough reputation. The stronger question actually says that if the Newton polytope $P_f$ of a polynomial $f$ is decomposable then the polynomial can be factored. This is the reverse of Ostrowski's theorem which is not true. I do not have an example now but I am sure that there exist irreducible polynomials that their Newton polytopes are decomposable. Maybe here the field you choose is important. $\endgroup$ – Harry May 25 '16 at 13:32
  • $\begingroup$ With two or more variables and an infinite field, almost all polynomials are irreducible (in a sense that can be made more explicit, but consider the reals or the rationals). $\endgroup$ – David Handelman May 25 '16 at 13:47

If I've understood your first question correctly then you can take $g$ and $h$ to be the sum of monomials corresponding to the vertices of $Q$ and $R$ respectively. Then $\tilde{f}=gh$ does the job.

For your follow up question, the answer is negative. Consider $S_g=\{(0,0),(1,0)\}$ and $S_h=\{(0,0),(0,1),(0,2)\}$ and $S_f=\{(0,0),(1,0),(0,2),(1,2)\}$. Since $g=a+bx$ and $h=c+dy+ey^2$ for non-zero $a,b,c,d,e$ the coefficient of $y$ in $gh$ is $ad\neq 0$ but $(0,1)\notin S_f$.

The answer to the stronger question in the edit is also negative. Consider $$P=\{(0,0),(0,1),(0,2),(1,0),(1,2),(2,0),(2,1),(2,2)\}$$ which is decomposable for example by taking $Q=\{(0,0),(1,0),(2,0)\}$ and $R=\{(0,0),(0,1),(0,2)\}$. The idea is that this is the only choice of $Q,R$ that can decompose $P$ and this is not hard to check by hand. However $P$ is missing $(1,1)$ from $Q+R$ so we cant have $P=Q+R$. This example works over any field.

| cite | improve this answer | |
  • $\begingroup$ This answers my questions indeed. For the second question, I had something a bit different in mind: Is it true that if $S_f$ can be written as a sum, then for at least one of these sums, one can find $\tilde f$, $g$ and $h$ such that [...]? $\endgroup$ – Bruno Mar 2 '15 at 12:52
  • $\begingroup$ @Bruno, the stronger question has a negative answer, too. I added an example to the answer. $\endgroup$ – Gjergji Zaimi Mar 2 '15 at 21:51
  • $\begingroup$ Your example does not work: You can decompose $P$ as $R+R$ where $R=\{(0,0),(0,1),(1,0),(1,1)\}$ and indeed, if you take $g=1-x-y-xy$, $P$ is the support of $g^2$. $\endgroup$ – Bruno Mar 3 '15 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.