# On a reciprocal of Ostrowski theorem on Newton polytopes and factorization

$\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$?

Remarks.

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.

• 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. – Harry May 25 '16 at 13:32
• 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). – 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.
• 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 [...]? – Bruno Mar 2 '15 at 12:52
• 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$. – Bruno Mar 3 '15 at 9:45