What does it mean polynomials share Newton polytope?

Question

I have trouble understanding the connection between polynomials and Newton polytopes. I will try to make a short introduction to my problem and hope you will catch on. In the end I will ask questions.

I have a game with n players: $1,2,...,n$.
The $i^{\text{th}}$ player has $d_i$ strategies and he allocates probabilities to them which we denote by $(p_1^{(i)},...,p_{d_i}^{(i)})$. So, it holds $\forall i,j : p_j^{(i)} \geq 0 \quad$ and $\quad \forall i : p_1^{(i)} + p_2^{(i)} + \cdots + p_{d_i}^{(i)} = 1 $.
We use $p_{d_i}^{(i)} = 1 - \sum_{j=1}^{d_i-1} p_j^{(i)}$.
The $i^{\text{th}}$ player has a payoff matrix $X^{(i)}$, which is an $n$-dimensional array of size $d_1 \times ... \times d_n$ and whose entries are rational numbers.

I have following polynomials:

$$\sum_{j_1=1}^{d_1} \cdots \sum_{j_{i-1}=1}^{d_{i-1}} \sum_{j_{i+1}=1}^{d_{i+1}} \cdots \sum_{j_n=1}^{d_n} \Big( X_{j_1 ... j_{i-1} k j_{i+1} j_n}^{(i)} - X_{j_1...j_{i-1}1j_{i+1}...j_n}^{(i)} \Big) \cdot p_{j_1}^{(1)} \cdots p_{j_{i-1}}^{(i-1)} p_{j_{i+1}}^{(i+1)} \cdots p_{j_n}^{(n)} $$

where $i=1,2,...n$ and $k=2,3,...,d_i$.

Consider the $d_i−1$ polynomials for a fixed upper index i. They share the same Newton polytope, namely, the product of simplices $$ \Delta^{(i)} = \Delta_{d_1 - 1} \times \cdots \Delta_{d_{i-1}-1} \times \{0\} \times \Delta_{d_{i+1}-1} \times \cdots \times \Delta_{d_n-1}. $$ Here $\Delta_{d_i-1}$ is the convex hull of the unit vectors and the origin in ${\mathbb R}^{d_i-1}$. Hence the Newton polytope $\Delta^{(i)}$ is a polytope of dimension $\delta - d_i + 1$, where $\delta=d_1+ \cdots + d_n - n$.

My questions are:

1. What does it mean that this polynomials share Newton polytope, what does it even mean that a polynomial is supported ( or whatever is the word) by Newton polytope?
2. And in this case why is $\Delta_{d_i-1} \subset {\mathbb R}^{d_i-1}$. Should it not be subset of ${\mathbb R}^{d_i}$ because $(p_1^{(i)},...,p_{d_i}^{(i)})$ is a point in that polytope.
3. Why is the dimension if $\Delta^{(i)}$ $\delta-d_i+1$. I thought it is:

$$(d_1-1)+ \cdots + (d_{i-1}-1) + 1 + (d_{i+1}-1) + \cdots + (d_n-1) $$ \begin{align} &= (d_1 + \cdots + d_n) - d_i - (n-1)+1 \\ &=(d_1+ \cdots + d_n - n) - d_i + 2 \\ &= \delta - d_i + 2. \end{align} Thanks for your answers.

Answer 1

Newton polytopes and the polynomials they support

We will use the standard notion $\mathbf{x}^{\mathbf{a}} := \prod_{i=1}^{n} x_i^{a_i}$ to represent monomials in a multivariate (Laurent) polynomial ring.

The Newton polytope of a polynomial is the convex hull of its exponent vectors. We say that a polytope $P$ supports a polynomial $p$ if $P$ is the Newton polytope of $p$.

Example 1: The polytope $\mathrm{conv} \{[0,0]^\top\}$ supports all constant polynomials over any bivariate polynomial ring. More generally, a lattice point $\mathbf{a} \in \mathbb{Z}^d$ supports every polynomial of the form $c_\mathbf{a}\mathbf{x}^\mathbf{a}$ where $c_\mathbf{a}$ is an element of an arbitrary ring.

Example 2: The Newton polytopes of the polynomials \begin{align} p &= 2 + 3x^2 - 2y + \frac{1}{2}xy \in \mathbb{Q}[x,y,z] \text{ and }\\ q &= -1 + 8x - x^2 + 5y + xy \in \mathbb{Z}_9[x,y,z] \end{align} both have vertices $V = \{[0,0,0]^\top, [2,0,0]^\top, [0,1,0]^\top, [1,1,0]^\top\}$ and hence coincide.

In general we have the following: Fix a (convex) lattice polytope $P \in \mathbb{R}^d$. Then $P$ is the Newton polytope of a polynomial $p$ if and only if $p$ is of the form $\sum_{\mathbf{a} \in P \cap \mathbb{Z}^d} c_\mathbf{a}\mathbf{x}^\mathbf{a}$ such that $c_\mathbf{a} \neq 0$ whenever $\mathbf{a}$ is a vertex of $P$.

A note on standard simplices

There are two geometric objects typically associated with the term standard $(d-1)$-dimensional simplex: one is the full-dimensional polytope in $\mathbb{R}^{d-1}$ whose vertices consist of the origin together with the $d-1$ standard unit vectors; the other is a codimension one polytope in $\mathbb{R}^d$ whose vertices are the $d$ standard unit vectors. Since there is a natural map between these two polytopes that preserves typically relevant polyhedral data, the choice of which definition to use is usually motivated by the problem at hand.

In the OP the probability vectors are naturally associated to points in $\mathbb{R}^d$ whose coordinates sum to $1$, so taking the second view of the standard simplex (as suggested in the OP) seems more natural.

The dimension of the product of simplices

First we collect some basic facts. The dimension of a polytope is the dimension of its affine span. In particular, the dimension of (the convex hull of) a point is zero. The dimension of a product of polytopes is just the sum of dimensions of the factors.

Now, in the computation of the dimension of $\Delta^{(i)}$ in the OP the dimension of $\{0\}$ is $0$ and not $1$. So the dimension of $\Delta^{(i)}$ is $\delta -d_i + 1$, as expected.