Let $f=(f_0,\ldots f_n)$ be a vector in $\Bbb N^{n+1}$. Let $X$ be the set of all (ordered) $f_0$-tuples in $\Bbb R^n$ whose convex hull has $f$ as its $f$-vector. Assume that $X$ is non-empty. Is anything known about $X$? For instance, is it algebraic? Semi-algebraic?

Edit: By “is $X$ algebraic”, I mean: Is $X$ locally closed, or maybe just constructible, in the Zariski topology on $\Bbb R^{f_0 n}$?


It is semi-algebraic. Let $x$ be an $f_0$-tuple of points in $R^n$. Take any subset of $n$ points from $x$, and find a hyperplane through these points. This involves only rational operations on the coordinates. Select from these hyperplanes those for which all points in $x$ are on one side. This involves checking some inequalities. So we obtain equations of faces. Solving linear equations obtain intersections of faces, and check which of them are really the facets. All this involves only rational operations and checking inequalities between rational functions of $x$. Therefore the set is semi-algebraic.

It is not algebraic, as seen on the simplest example for $n=1$.

  • $\begingroup$ What is a rational operation in this context? I am not very familiar with real algebraic geometry. $\endgroup$ – Avi Steiner Oct 23 '18 at 15:15
  • $\begingroup$ Also, although the $n=1$ case (with $f=(2,1)$) isn’t algebraic in the sense of an algebraic subset, it is a real algebraic variety as it is exactly the set of $\Bbb R$-valued points of the (quasiaffine) complex algebraic variety $\Bbb C^2 \setminus V(x-y)$. $\endgroup$ – Avi Steiner Oct 23 '18 at 15:31
  • $\begingroup$ @Avi Steiner: rational operation is what you obtain by performing the 4 arithmetic operations on numbers and variables. 4 arithmetic operations are addition, subtraction, multiplication and division. Solving systems of linear equations involves only these operations. $\endgroup$ – Alexandre Eremenko Oct 23 '18 at 18:25
  • $\begingroup$ I'm also a little bit confused by this argument - is it possible to make it a little bit more rigorous? $\endgroup$ – Jonathan Frink Oct 23 '18 at 22:10

Hopefully this answer to my question is correct despite my minimal knowledge of semi-algebraic things.

$X$ is not in general algebraic: Consider the case of a square, i.e. $f=(4,4)$ (using the notation from my post, this should actually be $(4,4,1)$, but it seems that the number of $n$-dimensional faces of an n-dimensional polytope is usually left out since it’s always one). Then $X$ is exactly the set of 4-tuples $(x_1,\ldots,x_4)$ of points in $\Bbb R^2$ such that $x_4$ is not in the convex hull of $\{x_1,\ldots,x_3\}$. Suppose $X$ is algebraic, and fix $x_1,\ldots,x_3$. Then so is the set of all $x_4$ not in the convex hull of $\{x_1,\ldots,x_3\}$. But this set is $\Bbb R^2$ minus a (solid) triangle, and such a set is not algebraic.

$X$ is semi-algebraic: By the definition of “face”, $X$ is exactly the set of tuples $(x_1,\ldots,x_{f_0})$ of points in $\Bbb R^n$ satisfying the following (lines are numbered and indented for clarity):

  1. For all $k\in\{0,\ldots,n-1\}$,
  2. $\quad$there exist exactly $f_k$ subsets $I\subseteq \{1,\ldots, f_0\}$ such that
  3. $\quad\quad$there exists an affine linear functional $g\colon \Bbb R^n\to \Bbb R$ such that
  4. $\quad\quad\quad g(x_i)\geq0$ for all $i\in \{1,\ldots, f_0\}$
  5. $\quad\quad\quad$and $g(x_i)=0$ for all $i\in I$.

Lines 3-5 describe a semi-algebraic set when $I$ and $k$ are fixed. Since there are only finitely many possible $I$ and $k$, we get that $X$ is indeed semi-algebraic.


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.