A Parameterization of Newton Polytope of a Polynomial with All Positive Coefficients

Consider a polynomial p=IaIxIp=\sum_{I} a_I x^I with aI0a_I\geq 0 for all II , where xI=i=1NxiniI, x^I=\prod_{i=1}^N x_i^{n^I_i}, its Newton polytope N(p)N(p) is defined as the convex hull of vectors {nI=(n1I,,nNI)}\{\mathbf{n}^I=(n^I_1,\dots,n^I_N)\} .

Now consider the `scattering map’ X(x)=logplogx, \mathbf X(x)=\frac{\partial \log p}{\partial \log \mathbf x}, where xi(0,)x_i\in (0,\infty) for all ii . We claim that X\mathbf{X} is an one-to-one map between (0,)N(0,\infty)^N and the interior of N(p)N(p) .

Firstly, suppose the matrix (niI)(n_i^I) does not have full rank, i.e. there exists s0\mathbf s\neq 0 such that snI=0\mathbf s \cdot \mathbf n^I=0 for all II . In this case, sX=slogplogx=0. \mathbf s\cdot\mathbf X=\mathbf s\cdot\frac{\partial \log p}{\partial \log \mathbf x}=0. Therefore, one can project im(X)\operatorname{im}(\mathbf X) by setting some xi=1x_i=1 so that there’s no more vector s\mathbf s such that snI=0\mathbf s\cdot \mathbf n^I=0 for all II . Conversely, one can recover the original image by solving these equations sX=0\mathbf s\cdot\mathbf X=0 . Therefore, we can assume that the matrix (niI)(n_i^I) has full rank, then dim(N(p))=N\dim (N(p))=N .

Next we show that interior points of N(p)N(p) are in the im(X)\operatorname{im}(\mathbf{X}) . Let Λ\mathbf{\Lambda} be a interior point in N(p)N(p) defined by Λ=IλInI=logxIλIlogxI \mathbf \Lambda=\sum_{I}\lambda_I\mathbf n^I =\frac{\partial}{\partial \log \mathbf x}\sum_{I}\lambda_I \log x^I where IλI=1\sum_I \lambda_I=1 and λI>0\lambda_I > 0 . Equations X(x)=Λ\mathbf X(x)=\mathbf \Lambda are 0=logx(logpIλIlogxI)=logx(logF(x))=1F(x)F(x)logx \begin{aligned} 0=\frac{\partial }{\partial \log \mathbf x}\left( \log p-\sum_{I}\lambda_I \log x^I \right)=\frac{\partial }{\partial \log \mathbf x}\left( \log F(\mathbf x) \right)=\frac{1}{F(\mathbf x)}\frac{\partial F(\mathbf x)}{\partial \log \mathbf x} \end{aligned} where F(x)=IaIxIJ(xJ)λJ. F(\mathbf x)=\sum_I a_I x^I\prod_J (x^{-J})^{\lambda_J}. Let y=logx\mathbf y=\log \mathbf x , and then F(y)=IaIexp(y(nIΛ)) \begin{aligned} F(\mathbf y) &=\sum_I a_I \exp\left(\mathbf{y}\cdot \left(\mathbf{n}^I-\mathbf{\Lambda}\right)\right) \end{aligned} so we only need to show that F(y)F(\mathbf y) has saddle points in RN\mathbb R^N because F>0F>0 for all y\mathbf y .

To see it, we firstly notice that F(y)F(\mathbf y) is a strict convex function of y\mathbf y . In fact, the Hessian of F(y)F(\mathbf y) is Hij(y)=2yiyjF(y)=IaIexp(y(nIΛ))(nIΛ)i(nIΛ)j. H_{ij}(\mathbf y)=\frac{\partial^2}{\partial y_i\partial y_j}F(\mathbf y)=\sum_I a_I \exp\left(\mathbf{y}\cdot \left(\mathbf{n}^I-\mathbf{\Lambda}\right)\right)\left(\mathbf{n}^I-\mathbf{\Lambda}\right)_i\left(\mathbf{n}^I-\mathbf{\Lambda}\right)_j. For any v0\mathbf v\neq 0 , i,jvivjHij=IaIexp(y(nIΛ))(v(nIΛ))2>0. \sum_{i,j}v_iv_jH_{ij}=\sum_I a_I \exp\left(\mathbf{y}\cdot \left(\mathbf{n}^I-\mathbf{\Lambda}\right)\right) \left(\mathbf v\cdot (\mathbf{n}^I-\mathbf{\Lambda})\right)^2 >0. It cannot vanish because that it only happens when v(nIΛ)=0\mathbf v\cdot (\mathbf{n}^I-\mathbf{\Lambda})=0 for all II , but we have assumed {nI}\{\mathbf n^I\} has full rank.

For a strict convex function F(y)F(\mathbf y) on RN\mathbb R^N , it has a unique minimal in RN\mathbb R^N iff it does not take its minimal when y\mathbf{y} goes to infinity along any direction. In our case, we only need that for any y0\mathbf{y}\neq 0 and Λ(N(p))\mathbf\Lambda \in (N(p))^\circ , there exist some II such that y(nIΛ)>0 \mathbf{y}\cdot (\mathbf{n}^I-\mathbf{\Lambda})>0 and if Λ∉N(p)\mathbf\Lambda \not\in N(p) , there exist some y0\mathbf{y}\neq 0 such that the exponentials are all negative, then F(ty)0F(t\mathbf y)\to 0 when tt\to \infty .

In fact, if Λ(N(p))\mathbf\Lambda \in (N(p))^\circ , for a given y0\mathbf y\neq 0 , the hyperplain LL with normal vector y\mathbf y crossing Λ\mathbf \Lambda divides the space RN\mathbb R^N into semi-spaces L+L^+ and LL^- , then nI\mathbf{n}^I in L+L^+ are what we are looking for. Conversely, if Λ∉N(p)\mathbf\Lambda \not\in N(p) , one can find a hyperplain LL such that N(p)LN(p)\subset L^- , then the normal vector of LL gives the wanted direction. These are direct results of convexity of N(p)N(p) .

Therefore, we have proven that F(y)F(\mathbf y) has a unique minimal in RN\mathbb R^N when Λ(N(p))\mathbf \Lambda \in (N(p))^\circ and no minimal in RN\mathbb R^N when Λ∉N(p)\mathbf \Lambda \not\in N(p) . Hence, X(x)=logplogx, \mathbf X(x)=\frac{\partial \log p}{\partial \log \mathbf x}, is an one-to-one map between (0,)N(0,\infty)^N and the interior of N(p)N(p) .

Generally, let Λ\mathbf{\Lambda} be a interior point in Minkowski sum pαpN(p)\sum_p \alpha_p N(p) corresponding to P=ppαpP=\prod_p p^{\alpha_p} defined by Λ=pαpΛp=pαpIpλIpnIp=logxpαpIpλIplogxIp \mathbf{\Lambda} =\sum_p \alpha_p \mathbf{\Lambda}_p =\sum_p \alpha_p \sum_{I_p}\lambda_{I_p}\mathbf{n}^{I_p} =\frac{\partial}{\partial \log \mathbf{x}}\sum_{p}\alpha_p\sum_{I_p}\lambda_{I_p} \log x^{I_p} where IpλIp=1\sum_{I_p} \lambda_{I_p}=1 and λIp>0\lambda_{I_p} > 0 . Equations X(x)=Λ\mathbf{X}(x)=\mathbf{\Lambda} are 0=logx(logPpαpIpλIplogxIp)=logx(log(pFpαp)), \begin{aligned} 0=\frac{\partial }{\partial \log \mathbf{x}}\left( \log P-\sum_{p}\alpha_p\sum_{I_p}\lambda_{I_p} \log x^{I_p} \right)&=\frac{\partial }{\partial \log \mathbf{x}}\left( \log \left(\prod_p F_p^{\alpha_p}\right) \right), \end{aligned} where Fp(y)=IpaIpexp(y(nIpΛp)). \begin{aligned} F_p(\mathbf y)&=\sum_{I_p} a_{I_p} \exp\left(\mathbf{y}\cdot \left(\mathbf{n}^{I_p}-\mathbf{\Lambda}_p\right)\right). \end{aligned} Write F(y)=pFp(y)αp, F(\mathbf y)=\prod_p F_p(y)^{\alpha_p}, we only need to show that F(y)F(y) has a unique saddle point in RN\mathbb R^N .

We assume that αp>0\alpha_p>0 for all pp . Here, F(y)F(\mathbf y) is no longer a strict convex function. However, take a positive number α0\alpha_0 such that α0<αp\alpha_0< \alpha_p for all pp , consider a new function F(y)1/α0=pFp(y)αp/α0, F(y)^{1/\alpha_0}=\prod_p F_p(y)^{\alpha_p/\alpha_0}, since FpF_p are convex functions and αp/α0>1\alpha_p/\alpha_0>1 , Fp(y)αp/α0F_p(y)^{\alpha_p/\alpha_0} are convex functions, so is their product. Since F(y)1/α0F(y)^{1/\alpha_0} has the same minimums as F(y)F(y) , so we can further assume that αp>1\alpha_p>1 for all pp .

Finally, we claim that F(y)F(y) does not take minimum when y\mathbf{y} goes to infinity along any direction. It is because that for a given y\mathbf{y} and each pp , Fp(ty)F_p(t\mathbf{y})\to \infty when tt\to \infty , so does F(ty)=pFp(ty)αpF(t\mathbf{y})=\prod_p F_p(t\mathbf{y})^{\alpha_p} . Therefore, equation X(x)=Λ\mathbf{X}(x)=\mathbf{\Lambda} has a unique solution.

Buwai Lee

Buwai Lee