Are the corner hypercubera polytopes self-dual?

Question

• Motivation: The polyhedron whose vertices are seven of the vertices of a cube (four on the bottom and three on top) - called a cubera - is self-dual. Does an analogous construction produce a self-dual polytope in higher dimensions?
• V-definition of a corner hypercubera: A $d$-hypercubera can be described as a $(d-1)$-simplex placed on top of a $(d-1)$-hypercube. In particular, the combinatorial type called corner hypercubera of dimension $d$ is represented by the convex hull of:
  • the unit $(d-1)$-hypercube, (i.e., including vertices with all $2^{d-1}$ arrangements of $0$ and $1$ in coordinate positions $x_2$ through $x_d$), lying in the hyperplane $x_1 = 0$, and
  • a translation of the origin and each of its $(d-1)$ adjoining hypercube vertices to the hyperplane $x_1 = 1$.
  • Therefore, the corner hypercubera of dimension $d$ has $2^{d-1} + d$ vertices.
  • For brevity, we'll drop the adjective 'corner' - it will be implied.
• Is each member of the infinite family (i.e., of dimension $d \ge 3$) of hypercuberas (with the v-definition given above) self-dual?

Answer 1

The proof that the d-hypercubera is self-dual will organized into nine parts:

1. Executive summary

• Given the vertex set, we'll first state a set of $2^{d-1} + d$ linear equations, then show that they are the equations of facets of the hypercubera, and that there are no other facets. Due to the requirements of this step, the proof will be structured as a math induction.
• We will then derive a $(2^{d-1} + d) \times (2^{d-1} + d$) facet-vertex incidence matrix, and show that it's symmetric, implying that the polytope is self-dual.

2. Discussion of homogeneous coordinates

• We'll follow the protocol of $polymake$ 1,1 (which I have used in researching this Q&A) of using homogeneous coordinates, with $x_0 = 1$ throughout. Because of the homogenous coordinates, we can and will represent each facet $f$ as the array of its coefficients. As a result, the facet equations will be written so that:
  • there will be no constant term in the facet equations $f$;
  • the vertex $x$ lies in the facet $f$ if and only if $f$ $\cdot$ $x$ = $0$; and
  • For all $x$ and $f$, you have $f$ $\cdot$ $x$ $\ge$ $0$.
• With the initial $x_0 = 1$ term added, the vertices of the hypercubera of dimension $d$ have coordinates $0$ through $d$ and are:
  • $2^{d-1}$ vertices with initial $x_0$ and $x_1$ coordinates $1,0$, then all possible arrangements of $0$'s and $1$'s; and
  • A vertex $(1,1,0,...0)$ and $d-1$ vertices with initial coordinates $1,1$, and having exactly one $1$ among the final $d-1$ coordinates, the rest $0$.

3. Statement to be proven by math induction

To be proven by math induction: the facets of a $d$-hypercubera are listed in four groups as follows:

1. A facet $f_1$ with coefficients $(0,1,0,...0)$, which is the $(d-1)$-hypercube in the hyperplane $x_1 = 0$.

2. A facet $f_2$ with coefficients $(1,-1,0,...0)$, which is the $(d-1)$-simplex in the hyperplane $x_1 = 1$. $f_1$ and $f_2$ are clearly complementary facets of the hypercubera (i.e., $f_1$ and $f_2$ are disjoint, and between them, contain all the vertices).

3. For $i = 1, ... d-1$, ${d-1 \choose i}$ facets whose first two coefficients are $i$ and $-(i-1)$, and whose remaining $d-1$ coefficients are $i$ occurrences of $-1$, and $d-1-i$ occurrences of $0$ (representing all possible such orderings of this many $-1$'s and $0$'s). The number of these facets is thus $2^{d-1} - 1$.

Furthermore, the combinatorial type of each facet described in Group $3$ is an $i$-fold pyramid over a hypercube of dimension $d-1-i$. (For the purpose of this description, a hypercube of dimension $0,1,2,$ and $3$ is a point, an edge, a square, and a cube, respectively. Therefore, the facets described in Group $3$ beginning with coefficients $d-1$ and $d-2$ are $(d-1)$-simplexes.)

4. $d-1$ facets whose first two coefficients are $0,0$, and all of the remaining $d-1$ coefficients $0$, except one coefficient of $1$ (so that $1$ appears as a coefficient in each of the $d-1$ final positions among these facets).

Also, the combinatorial type of each facet described in Group $4$ is a hypercubera of dimension $d-1$.

4. Proof of base case

We'll begin the first part of the math induction by applying the definition of hypercubera to dimensions $1, 2$, and $3$:

• The hypercubera of dimension $1$ is the line segment with vertices $(1,0)$ and $(1,1)$; it has facets $f_1$ - with coefficients $(0,1)$ (a $0$-hypercube) and $f_2$ - with coefficients $(1,-1)$ (a $0$-simplex), and thus it meets the criteria to be proved ($0$ facets are described in Groups $3$ and $4$).
• The hypercubera of dimension $2$ is the square with vertices $(1,0,0)$, $(1,0,1)$, $(1,1,0)$, and $(1,1,1)$; it has facets with coefficients $(0,1,0)$ (i.e., $f_1$) (a $1$-hypercube), $(1,-1,0)$ ($f_2$) (a $1$-simplex), $(1,0,-1)$ (a $1$-simplex), and $(0,0,1)$ (a $1$-hypercubera), and thus it meets the criteria to be proved.
• The hypercubera of dimension $3$ has:
• Vertices: $(1,0,0,0)$, $(1,0,0,1)$, $(1,0,1,0)$, $(1,0,1,1)$, $(1,1,0,0)$, $(1,1,0,1)$, and $(1,1,1,0)$
• Facets: $f_1$:$(0,1,0,0)$ (a square), $f_2$:$(1,-1,0,0)$ (a $2$-simplex), $(1,0,-1,0)$ (a $2$-simplex), $(1,0,0,-1)$ (a $2$-simplex), $(2,-1,-1,-1)$ (a $2$-simplex), $(0,0,0,1)$ (a $2$-hypercubera), and $(0,0,1,0)$ (a $2$-hypercubera).
• Thus, the $3$-hypercubera meets the criteria to be proved.

We'll point out that the cubera (i.e., $3$-hypercubera) has a symmetric facet-vertex incidence table as shown below, and is thus self-dual. Also, the hypercuberas of dimensions $1$ and $2$ (line segment and square) are also self-dual.

5. Induction step: Sufficient condition for facets

For the math induction step, assume that the criteria to be proved have been met for dimensions $1$ through $d$, $d \ge 3$. We'll show the criteria are met for dimension $d + 1$.

The vertices of the hypercubera $H_{d+1}$ have coordinates $0$ through $d+1$ and are:

• $2^{d}$ vertices with initial $x_0$ and $x_1$ coordinates $1,0$, then all possible arrangements of $0$'s and $1$'s; and
• A vertex $(1,1,0,...0)$ and $d$ vertices with initial coordinates $1,1$, and having exactly one $1$ among the final $d$ coordinates, the rest $0$.

We'll first show that for all vertices $x$ and $f$ to be proven as facets, $f$ $\cdot$ $x$ $\ge$ $0$. The coordinates of the vertices $x$ are all non-negative, and all the coefficients in Groups $1$ and $4$ are non-negative, so for $f$ in these groups, $f$ $\cdot$ $x$ $\ge$ $0$. For Group $2$, $f$ $\cdot$ $x$ = $1$ for $x_1 = 0$, and $f$ $\cdot$ $x$ = $0$ for $x_1 = 1$. For group $3$:

• for $x_1 = 0$, you have initial coefficient $f_0 = i$ ($1 \le i \le d$), and among the final $d$ coefficients $f_2$ through $f_{d+1}$, $i$ of them equal $-1$, and the rest equal $0$; hence, the minimum value of $f$ $\cdot$ $x$ is $0$, achieved if the $x$-coordinate is $1$ for all of the $i$ positions of the $-1$'s after $f_1$ in $f$.
• for $x_1 = 1$, $f_0x_0 + f_1x_1 = i - (i-1) = 1$, and only one of the $x$ coordinates after $x_1$ equals $1$ (the rest $0$); hence, the minimum value of $f$ $\cdot$ $x$ is $0$, achieved if the $1$ coordinate of $x$ after $x_1$ coincides with a $-1$ coefficient in $f$.

Therefore, if we show that the vertices of $H_{d+1}$ satisfying $f \cdot x = 0$ are the vertices of a $d$-polytope, we can conclude that polytope to be a facet.

Group $1$ (i.e, facet $f_1$): $f_1 \cdot x = 0$ for all the vertices with $x_1 = 0$; i.e., a d-hypercube, which is therefore a facet.

Group $2$ (i.e., facet $f_2$): $f_1 \cdot x = 0$ for all the vertices with $x_1 = 1$; i.e., a d-simplex, which is therefore a facet.

Group $3$: Begin with $f$ from Group $3$ with $1 \le i \lt d$.

• The intersection of $f$ and $f_1$ is the $(d-i)$-hypercube with the $i$ positions of $x_j$ = $1$ (corresponding to the $i$ coefficients of $f$ from $2$ to $d+1$ equal to $-1$), because the zeroth coefficient of $f$ is $i$ and the $x_1$ coordinate of $x$ in $f_1$ is $0$.
• The intersection of $f$ and $f_2$ is the $(i-1)$-simplex having the $i$ vertices which have one of the $x_j$ = $1$ (corresponding to the $i$ coefficients of $f$ from $2$ to $d+1$ equal to $-1$), because the zeroth & first coefficients of $f$ are $i$ and $i-1$, and the $x_0$ and $x_1$ coordinates of $x$ in $f_2$ are $1$ and $1$.
• It follows that $f$ is an $i$-fold pyramid over a $(d-i)$-hypercube; a $d$-polytope, and thus a facet.

For $f$ from Group $3$ with $i$ = $d$ (i.e., $f$ = $(d, d-1, -1, ..., -1)$), $f$ contains the single vertex $(1, 0, 1, ..., 1)$ from $f_1$, and all but $(1, 1, 0, ..., 0)$ ($d$ vertices) from $f_2$ - hence, $f$ is a $d$-simplex and a facet.

Group $4$: For $f$ from Group $4$ with coefficient $i$ = $1$ ($2 \le i \le d+1$):

• $f$ intersects with $f_1$ at the $(d-1)$-hypercube $x_i$ = $0$;
• $f$ intersects with $f_2$ at the $(d-1)$-simplex $x_i$ = $0$;
• Therefore, $f$ is a $d$-hypercubera and a facet.

Thus, the $2^d + d + 1$ coefficient sets in groups $1$ through $4$ represent facets of $H_{d+1}$.

6. Necessary condition for facets

To show that there are no other facets, we'll derive the set of ridges from all the known facets of $H_{d+1}$, and show that each ridge corresponds to a facet of two known $H_{d+1}$ facets. As a result, there can be no other $H_{d+1}$ facets, as there are no available ridges for them to intersect at.

In the following, we'll refer to the Group $3$ subgroup with zeroth coefficient $f_0 = i$ as Subgroup $3.i$ (which are $i$-fold pyramids over $(d-i)$-hypercubes).

The $d$-hypercube $f_1$ has $2d$ facets, intersecting with:

• Each of the $d$ Group $4$ $d$-hypercuberas at their $(d-1)$-hypercube facet $x_1 = 0$; and

• Each of the $d$ Subgroup $3.1$ facets (with $i = 1$) (which are pyramids over $(d-1)$-hypercubes) at their $(d-1)$-hypercube facet $x_1 = 0$.

The $d$-simplex $f_2$ has $d+1$ facets, intersecting with:

• Each of the $d$ Group $4$ $d$-hypercuberas at their $(d-1)$-simplex facet $x_1 = 1$; and

• The Subgroup $3.d$ facet (a $d$-simplex) at its $(d-1)$-simplex facet $x_1 = 1$.

Turning to Group $3$: Recall that an $i$-fold pyramid over a $(d-i)$-hypercube has $2d-i$ facets; $2(d-i)$ $i$-fold pyramids over a $(d-i-1)$-hypercube, and $i$ $(i-1)$-fold pyramids over a $(d-i)$ hypercube.

Each facet in Subgroup $3.1$ has:

• $(d-1)$ facets intersecting each of the Subgroup $3.2$ facets (having their two $-1$ coordinates (among the final $d$ coordinates) at the same position as the Subgroup $3.1$ facet, plus at one other position) at a pyramid over a $(d-2)$-hypercube;

• $1$ facet intersecting with $f_1$ at its facet $x_1 = 0$ - a $(d-1)$-hypercube; and

• $(d-1)$ facets intersecting at each of the Group $4$ facets (having their $1$ coordinates (among the final $d$ coordinates) at a different position than the position of the $-1$ coordinate in the Subgroup $3.1$ facet at a pyramid over a $(d-2)$-hypercube.

For $2 \le i \lt d$, each facet in Subgroup $3.i$ has:

• $(d-i)$ facets intersecting each of the Subgroup $3.(i+1)$ facets (having their $i$ $-1$ coordinates (among the final $d$ coordinates) at the same positions as the Subgroup $3.i$ facet, plus at one other position) at a $i$-fold pyramid over a $(d-i-1)$-hypercube;

• $i$ facets intersecting each of the Subgroup $3.(i-1)$ facets (having their $(i-1)$ $-1$ coordinates (among the final $d$ coordinates) at the same positions as the Subgroup $3.i$ facet, except for one position) at a $(i-1)$-fold pyramid over a $(d-i)$-hypercube; and

• $(d-i)$ facets intersecting at each of the Group $4$ facets (having their $1$ coordinates (among the final $d$ coordinates) at a different position than the positions of the $-1$ coordinates in the Subgroup $3.i$ facet at a $(i-1)$-fold pyramid over a $(d-i-1)$-hypercube.

The Subgroup $3.d$ facet has:

• $d$ facets intersecting each of the Subgroup $3.(d-1)$ facets (having $(d-1)$ $-1$ coordinates (among the final $d$ coordinates) at a $(d-1)$-simplex;

• $1$ facet intersecting with $f_2$ at its facet $x_1 = 1$ - a $(d-1)$-simplex.

Turning to Group $4$, we know by the induction hypothesis that each of these $d$-hypercubera facets have $2^{d-1}+d$ facets in four groups as described in the 'to be proved by math induction' statement. Say $g$ is a group $4$ facet, and the position of the lone $1$ coefficient of $g$ (among positions $2$ through $d+1$) is $k$.

1. $g$ has a $(d-1)$-hypercube facet $x_1 = x_k = 0$ at the intersection with $f_1$.
2. $g$ has a $(d-1)$-simplex facet ($x_1 = 1$, $x_k = 0$) at the intersection with $f_2$.
3. $g$ intersects each of the ${d-1 \choose i}$ $3.i$ facets, $1 \le i \le d-1$, that have a $0$ coefficient in position $k$ at an $i$-fold pyramid over a $(d-1-i)$-hypercube. ($g$ contains all $i$ apices of the $3.i$ facet, and the $x_k = 0$ facet of its $(d-i)$-hypercube base.)
4. $g$ has $(d-1)$ $(d-1)$-hypercubera facets at the intersections with each of the other Group $4$ facets.

Thus, all facets of all known $H_{d+1}$ facets coincide with facets of other known facets (forming ridges). Thus, there are no additional $H_{d+1}$ facets. This completes the math induction portion of the proof.

7. Construct facet-vertex incidence matrix

Finally, we will construct a facet-vertex incidence matrix for $H_d$ and show that it is symmetric. Begin by assigning columns to the $2^{d-1} + d$ vertices listed in lexicographical order. So, the first $2^{d-1}$ columns are vertices of the $(d-1)$-hypercube with $x_1 = 0$, and the last $d$ columns are in the $(d-1)$-simplex with $x_1 = 1$.

The rows will begin with Group $3$ facets listed in lexicographical order with respect to coefficients $2$ through $d$. So, the first row is assigned to the Subgroup $3.(d-1)$ facet $(d-1,-(d-2),-1,...,-1)$. For row $i$ within the first $2^{d-1}$ rows, (within positions $2$ through $d$), the $-1$ coefficient positions correspond with the $0$ coordinate positions in the column $i$ vertex, and the $0$ coefficient positions correspond with the $1$ coordinate positions in the column $i$ vertex.

Row $2^{d-1}$ is assigned to the Group $1$ facet (i.e.,the $(d-1)$-hypercube with $x_1 = 0$, or $(0,1,0,...0)$), and row $2^{d-1}+1$ is assigned to the Group $2$ facet (i.e., the $(d-1)$-simplex with $x_1 = 1$, or $(1,-1,0,...0)$). The last $(d-1)$ rows are assigned to the Group $4$ facets in lexicographical order.

8. Show that incidence matrix is symmetric

Resetting the naming convention, for $1 \le i, j \le 2^{d-1}+d$, we'll now call the incidence matrix row $i$ facet $f_i$ and the column $j$ vertex $x_j$. Recall that the facet-vertex matrix of $H_d$ has a (i,j) entry equal to $1$ if $f_i$ $\cdot$ $x_j$ = $0$, and a (i,j) entry equal to $0$ if $f_i$ $\cdot$ $x_j$ $\gt$ $0$. We'll show that if $f_i$ $\cdot$ $x_j$ = $0$, then $f_j$ $\cdot$ $x_i$ = $0$, implying that the incidence matrix is symmetric.

Case: $1 \le i, j \lt 2^{d-1}$: Say $f_i$ has position $0$ and $1$ coefficients $k$, $-(k-1)$, and there are $k$ coefficients equal to $-1$ among the final $(d-1)$ coefficients (and $(d-1-k)$ coefficients equal to $0$) in positions $2$ through $d$. For $f_i$ $\cdot$ $x_j$ to equal $0$, the $k$ coordinates of $x_j$ corresponding to the positions of the $-1$ coefficients in $f_i$ must all equal $1$. Thus, the $0$ coordinates of $x_j$ (among the final $(d-1)$ coordinates) are in positions which are a subset of positions of the $0$ coefficients of $f_i$ (among the final $(d-1)$ coefficients). This implies that the $-1$ coefficients of $f_j$ (among the final $(d-1)$ coefficients) are in positions which are a subset of positions of the $1$ coordinates of $x_i$ (among the final $(d-1)$ coordinates). As a result, $f_j$ $\cdot$ $x_i$ = $0$, because the first coefficient of $f_j$ equals the number of $-1$ coefficients among the final $(d-1)$ coefficients.

Case: $i$ = $2^{d-1}$ or $j$ = $2^{d-1}$: The row $2^{d-1}$ facet is $(0,1,0,...0)$ - the first $2^{d-1}$ vertices are in this facet, and the last $d$ are not. The column $2^{d-1}$ vertex is $(1,0,1,...1)$ - the first $2^{d-1}$ facets contain this vertex, and the last $d$ facets do not.

Case: $i$ = $2^{d-1}+1$ or $j$ = $2^{d-1}+1$: The row $2^{d-1}+1$ facet is $(1,-1,0,...0)$ - the first $2^{d-1}$ vertices are not in this facet, and the last $d$ are. The column $2^{d-1}+1$ vertex is $(1,1,0,...0)$ - the first $2^{d-1}$ facets do not contain this vertex, and the last $d$ facets do contain this vertex.

Case: $1 \le i \lt 2^{d-1}$, $2^{d-1}+2 \le j \le 2^{d-1}+d$:

• With $f_i$ and $x_j$: The first two coefficients of $f_i$ are $k$ and $-(k-1)$ and the first two coordinates of $x_j$ are $1$ and $1$. So, $f_i$ $\cdot$ $x_j$ = $0$ if and only if a $-1$ coefficient of $f_i$ is in the same position as the $1$ coordinate (among the final $(d-1)$) in $x_j$. This implies that the $1$ coefficient in $f_j$ (which is in that same position) corresponds with a $0$ coordinate in $x_i$, so $f_j$ $\cdot$ $x_i$ = $0$.

• With $f_j$ and $x_i$: $f_j$ $\cdot$ $x_i$ = $0$ if and only if the sole $1$ coefficient of $f_j$ is in the same position as a $0$ coordinate (among the final $(d-1)$) in $x_i$. This implies that the $1$ coordinate in $x_j$ (which is in that same position) corresponds with a $-1$ coordinate in $f_i$. As the first two coefficients of $f_i$ are $k$ and $-(k-1)$ and the first two coordinates of $x_j$ are $1$ and $1$, $f_i$ $\cdot$ $x_j$ = $0$.

Case: $2^{d-1}+2 \le i, j \le 2^{d-1}+d$: For $i = j$, you have $f_i$ $\cdot$ $x_i$ = $1$, so $x_i$ is not in the facet $f_i$. Otherwise, for $i$ $\ne$ $j$, $f_i$ $\cdot$ $x_j$ = $0$, as the $1$ coefficient of $f_i$ is in a different position than the $1$ coordinate of $x_j$ (among the last $(d-1)$ positions).

Having covered all cases, conclude that the $H_d$ facet-vertex incidence matrix is symmetric, so $H_d$ is self-dual.

9. Final remark

An interesting aspect of the $H_d$ facet-vertex incidence matrix is that the upper left hand $2^{d-1}$ $\times$ $2^{d-1}$ sub-matrix apparently contains a Sierpinski triangle pattern, as is shown for the case $d = 7$ below: 1 Ewgenij Gawrilow and Michael Joswig. polymake: a framework for analyzing convex polytopes. Polytopes—combinatorics and computation (Oberwolfach, 1997), 43–73, DMV Sem., 29, Birkhäuser, Basel, 2000. MR1785292 (2001f:52033).

1 Benjamin Assarf, Ewgenij Gawrilow, Katrin Herr, Michael Joswig, Benjamin Lorenz, Andreas Paffenholz and Thomas Rehn. Computing convex hulls and counting integer points with polymake. Math. Program. Comput. 9 (2017), no. 1, 1-38. MR3613012