# Number of polytopes formed by connecting points on a hypercube

Fix an integer $$d\geq 1$$, and let $$n\geq 1$$. Drawing hyperplanes between all the $$d$$-sets of lattice points on the boundary of the hypercube $$[0,n]^d\subseteq \mathbf{R}^d$$ defines a partition of $$[0,n]^d$$ into several distinct polytopes; let $$a(n,d)$$ denote the number of such polytopes. (Note that $$a(n,d)$$ is divisible by $$2^d$$.) For instance, $$a(1,2) = 4$$ and $$a(2,2) = 56$$. What can be said about the sequence $$a(n,d)$$ as $$n$$ and $$d$$ vary? (I'd originally asked about the generating function, but this seems way too hard. I would be interested in asymptotics with $$n$$ or $$d$$ fixed.)

• May I ask: How did you calculate $a(2,2)=56$? Apr 23, 2020 at 20:33
• @JosephO'Rourke I just drew it and counted! I don't know how to code this up, but it's probably possible to do so and compute more values. It'd be way more efficient than drawing and counting...
– skd
Apr 23, 2020 at 20:39
• There is a combinatorial formula for this, it gets cumbersome to generalize for higher dimension. Its easy for a(2,2), it also validates 56 as the answer. Its a double sum, inner sum over outer lattice points - 2, and outer sum over increasingly fewer lattice points as the starting point. Apr 24, 2020 at 6:07
• Just realized, the question needs a little more precision, when you say partition into several distinct polytopes....are you counting polytopes that are solids, facets, ridges, planes, lines....is there any restriction to the kind of polytopes? I've been making assumptions. Also, for some reason the phrasing with lines instead of hyperplanes made a lot more sense. Apr 24, 2020 at 7:12
• Joseph O'Rourke calculated that a(3,2) = 340. Searching the sequence 4, 56, 340 on the OEIS led to this: oeis.org/A255011. There doesn't seem to be a formula recorded there, though.
– skd
Apr 24, 2020 at 19:54

For d=2, use Euler's formula to compute these values programmatically. When ever you add a new line segment, count the edges it gets broken into, and the number of new vertices created. The end result is a planar graph whose edges you have tallied (be sure to add extra edges when creating a new vertex) and vertices, and then compute faces using the formula for a planar graph.

I imagine a similar approach is used for higher dimensions. I would ask Joseph O'Rourke about it.

Gerhard "Is This Really Computational Topology?" Paseman, 2020.04.23.

Here is $$a(3,2)$$, which confirms Gerhard's count of $$340$$ regions:

• Didn't your mother teach you to use symmetry? Really, I had higher hopes. Starting with half of the lower right square ( (3,3) in my indexing) I count 20 regions (more than half triangular) which gives 160 for all four corner squares. Picking half of an edge square ((1,2), say) I count 31 non central and four central regions, giving 264 for the edge squares. Take a triangular fourth of the central square and use symmetry to get 24 for the quarter and 96 for the square. 520 in all. Gerhard "Taught Himself Symmetry When Younger" Paseman, 2020.04.23. Apr 23, 2020 at 22:22
• Does anyone else experience the optical illusion of thin, white horizontal and vertical lines passing through the center of the square? For me they come and go depending on my visual focus... Apr 23, 2020 at 23:25
• yes, I'm seeing them as well Apr 23, 2020 at 23:43
• I think the pixellation makes a one pixel high contrast which suggests part of a horizontal line segment, and having several them at the same y ordinate reinforces the idea that there is a horizontal"ground line" occurring. I'm not seeing the vertical as much, possibly be sure of astigmatism. Gerhard "We Should Ask Scott Kim" Paseman, 2020.04.23. Apr 23, 2020 at 23:48
• I just noticed there are sixteen extra lines in the picture above, creating extra regions. (Dividing lines need to not stop at internal points.) Using symmetry, we see one line has ten segments and another has fourteen. Taking into account the (up to symmetry) two kinds of intersections involving only internal lines, we get 8*(10+14 - 1) - 4 .= 180 fewer regions, for a new total of 340. Gerhard "Surely That's Easier To Count?" Paseman, 2020.04.24. Apr 24, 2020 at 14:49

This is a counting problem, first we need to know a one thing:

1. How many lattice points exist on the boundary of our $$L=[0,n]^d$$ dimensional cube?

We only need count lattice points $$x \in [o,n]^d$$ such that a given coordinate $$x_j \in \{0,n\}$$, for some $$1 \le j \le d$$. This tells us $$x$$ lies on the boundary of $$S$$.

We count all lattice points and substract the internal points;

$$Q:=|\{ x \in L | \;\; x\in \text{ surface}\}| = (n+1)^d - (n-1)^d$$

The way to reason about that count is as follows,

1. Every $$x\in L$$ has the vector form $$(x_1,x_2,...,x_{d+1})$$.
2. For every coordinate we have $$n+1$$ choices of possible values.
3. Choices are independent, so we multiply by $$n+1$$ for every coordinate.
4. There are $$d$$ coordinates so we get $$(n+1)^d$$

The reasoning behind how many inner points there are so we can subtract them is almost exactly the same, only in step 2 we have $$(n+1) - 2$$ choices; that is, no coordinate is allowed to be $$n,0$$ as that would place the point on the surface of the lattice.

Let's say, $$L(n,d) := [0,n]^d$$, and $$\gamma( L(n,d) ) = |\{ A \in L(n,d) | A \text{ is a polytope as described in the question } \}|$$ then

$$\gamma(L(n,2))=\sum_{k=2}^{Q-1} \binom{Q-1}{k}= (2)^{(Q-1)}-(Q-1)-1$$. $$\gamma(L(n,3))=\sum_{k=3}^{Q-1} \binom{Q-1}{k}= (2)^{(Q-1)}-\frac{Q(Q-1)}{2}-(Q-1)-1$$. $$\cdots$$ $$\gamma(L(n,d))=\sum_{k=d}^{Q-1} \binom{Q-1}{k}= (2)^{(Q-1)}-\sum_{k=0}^{d-1} \binom{Q-1}{k}$$.

The origin is fixed, so we have $$Q-1$$ points to choose from, we may choose any number of these to form a polytope with some exceptions. For $$d=2$$, except 0 points, which leaves only the origin; or one point, which would make only lines. Similar for $$d=3$$, we may not choose just two points as this only makes a plane, and so on.

EDIT: The underlying assumption of this count is that the origin is a "corner" of every polytope.

• Thanks for the response. I'm not sure I fully understand; I don't parse the string "L(n,d) := [0,n]^d" and then the equations for L(n,d). Perhaps I've not calculated/understood your answer correctly, but it doesn't seem like any of the equations listed recover the sequence 4, 56, 340 for an n-by-n square in two dimensions.
– skd
Apr 24, 2020 at 19:56
• Fixed. Thanks! (Also, the 15 character comment length minimum is silly.) Apr 24, 2020 at 20:38
• Thanks. Again, apologies for possibly being silly, but it seems like the sequence γ(L(n,2)) goes 4, 120, 2036, ... It's not clear to me how this sequence relates to the question.
– skd
Apr 24, 2020 at 22:06
• I think we can easily see the first case is indeed 4: 3 triangles all with one corner at the origin and then the entire square. For $n=3$, that is the right count if you realize that polytopes need not be a triangle, you could choose 4 points including the origin and get a polypote with 4 sides where an edge would be part of the boundary, there are many such cases that only counting triangles leaves out.. Apr 24, 2020 at 22:39
• He is counting a different quantity, which may (or may not) bear some relation to your quantity. I suggested using Euler's formula for d=2. For higher d, one might start out with his formula to count related quantities. By the way, boundary is not clear yet in higher dimensions for me. I can see counting only lattice points on edges or on edges and faces as qualifying, but you might mean something more general. Gerhard "Not Used To High-Dimensional Combinatorics" Paseman, 2020.04.24. Apr 24, 2020 at 22:39