Polynomial size embeddings of toric varieties from polytopes?

Question

Background: Let $P$ be a integral polytope, and $X_P$ the toric variety associated to the normal fan.

$X_P$ is always projective, because the collection of characters corresponding to the points $\mathbb{Z}^n \cap P$ together give an embedding of $X_P$ into projective space.

However, the dimension of this embedding is the number of integer points, which is generally exponentially large in a reasonable description of $P$.

Questions:

• Suppose that $P$ is given by $Ax \leq b$ in $\mathbb{Q}^n$, with $A \in M_{n \times m} (\mathbb{Q})$ and $b \in \mathbb{Q}^n$, and that we are promised that $P$ is integral. Is there a projective embedding of $X_P$ which only requires $POLY( |A|, |b|)$ bits to specify?
• Is there a family $A_n, b_n$ such that the minimal dimension of an embedding grows exponentially in $|A|, |b|$?
• Are there some parameters of the polytope (in the sense of parametrized complexity) that control the size of a minimal (and efficiently computable) embedding?

I am being purposefully vague about whether the encoding of $A$ is in binary or unary; both polynomial or pseudopolynomial size embeddings would be interesting to me.

Motivation: I am curious about whether there are polytope parameters that become apparent through simple embeddings of the corresponding toric variety, and which could help with computational problems on the polytope side.

For example, if we know that $X_P$ is a smooth complete intersection and we have the equations cutting it out, we can compute its Euler characteristic using the formula on page 146 of "On the Chern Classes and the Euler Characteristic for Nonsingular Complete Intersections" by Vicente Navarro Aznar. This would count the number of vertices of $P$, which is generally a $\#P $ hard problem. Of course, most polytopes won't give a smooth toric variety or a complete intersection, and very likely computing the embedding is hard, so this observation is of limited use.

Alternatively, one could use this formula relating $F_p$ point counts to the fan in order to count the number of vertices, provided that the variety was such that counting $F_p$ points at sufficiently many (or sufficiently) large Galois fields was computationally tractable.

Anyhow, I'm curious about whether we can measure the complexity of the polytoe by the complexity of the toric variety as a projective variety. The basic question is whether or not we can efficiently find small embeddings in general, hence this question.

Answer 1

I think I found an a example of a family of toric varieties whose minimal embedding dimension is exponential in their dimension. The idea is to produce a singular point with a high dimensional tangent space.

It suffices to construct an affine toric variety with this property, since it is the case that for any strongly convex cone it is possible to find a polytope of the same dimension with that cone in its normal fan. This is done by taking the vertex figure of the dual cone. In more detail, if the the cone $C$ is generated by $v_1, \ldots, v_n$, we consider the cone that is the intersection of $\langle v_i , \_ \rangle \leq 0$, and take a vertex figure. The cone corresponding to the vertex at the original in the normal fan is the cone $C$.

Given a cone $\sigma$, the dimension of the tangent space of the affine toric variety $A_{\sigma}$ at the torus fixed point is the number of nonzero lattice points in $\sigma^{\vee}$ that are not the sum of two lattice points in $\sigma^{\vee}$. By choosing our cone appropriately, we can make this exponentially large.

In particular, we will design $\sigma^{\vee}$ with this property. We do this by requiring $\sigma^{\vee}$ to be generated by $v_1 = (1,0,\ldots, 0),v_2 = (1,m,0,0,\ldots,0), v_3 = (1,m,m,0,0,\ldots, 0),\ldots ,v_n =(1,m,m,\ldots, m)$.

These vectors are independent, and are the first lattice point along the ray that they span. The points $(a_1, a_2, \ldots, a_n)$ in this cone can be described by the equations $m a_1 \geq a_2 \geq a_3 \geq \ldots a_n \geq 0$. Of such lattice points with $a_1 = 1$, none of the lattice points are sums of any other lattice points in the cone, since adding two together makes the $a_1$ coordinate too large. Setting $a_1 = 0$ gives only the zero vector.

The number of non-increasing sequences of $n-1$ non-negative integers that are at most $m$ is number of monomials of degree $n-1$ in $m+1$ variables, which is ${ m + n \choose n - 1}$. If we take $m = n$, this grows exponentially quickly in $n$, for example we have (roughly) $\Omega( 2^n/n)$.

Thus, we have a family of $n$ dimensional toric varieties given by a polytope with $n +1$ defining equations*, which have a singular point with tangent space of dimension $\Omega(2^n / n)$. These toric varieties cannot be embedded into projective space of dimension bounded by some polynomial in $n$.

*Using the vertex figure description above.

Comments:

• The description of the matrix is polynomial in the dimension, regardless of whether we encode numbers in unary or binary.
• These seems like it should be typical behavior. Since the number of lattice points in a polytope ``should'' grown exponentially with the dimension, it seems like most of the time the tangent space at the distinguished point should be large. Maybe bounding the dimension of the tangent space at singular points is a reasonable parameter?