Correlation between Binary and N-dimensional simplexes

Question

I found an interesting correlation between binary numbers and $n$-dimensional simplexes and I'm trying to find where I can find more information on the subject.

I noticed that binary representations of numbers index the elements of an $n$-dimensional simplex in perfect order of construction. For example take a tetrahedron. $n=3$ as it is three dimensions. It has the elements:

1 cell
4 faces
6 edges
4 points

That is a total of $2^{n+1}-1$ elements equalling 15. If you take all binary numbers between from 1 - 15 and count the sum of the digits for each you get:

1 - 1
10 - 1
11 - 2
100 - 1
101 - 2
110 - 2
111 - 3
1000 - 1
1001 - 2
1010 - 2
1011 - 3
1100 - 2
1101 - 3
1110 - 3
1111 - 4

Now count the numbers of times each sum amount appears.

sum - count
4 - 1
3 - 4
2 - 6
1 - 4

The counts are the same as the number of each element in the tetrahedron, therefore any binary number whose digits sum 2 for example, can be used to represent an edge, 3 for faces, 1 for points, 4 for cells etc.

Not only do the sum counts match the number of elements in the simplex but surprisingly the order in which they appear, by counting by 1 binary number at a time, matches the logical order of the simplexes construction.

1 - 1 - point
10 - 1 - point
11 - 2 - edge
100 - 1 - point
101 - 2 - edge
110 - 2 - edge
111 - 3 - face
1000 - 1 - point
1001 - 2 - edge
1010 - 2 - edge
1011 - 3 - face

Notice how no edges appear until there are two free points to connect, no faces until three edges to fill etc.

Can somebody explain to me what applications this has or where I can find material on this subject?

Answer 1

It seems the following.

Let $n$ be a natural number, $X=\{x_0,x_1,\dots, x_n\}$ be a set of vertices of an $n$-dimensional simplex and $B$ be the set of binary sequences of length $n+1$. Then $|B|=2^{n+1}$. For each sequence $b=(b_0,\dots, b_n)$ let $c(b)=\operatorname{conv}\{x_i: b_i=1\}$ be a convex hull of a set $\{x_i: b_i=1\}$ of vertices of the simplex $S$. Then the map $c$ enumerates vertices, edges, faces, cells, etc. of the simplex $S$. In particular, a total number of faces of the simplex $S$ is equal to $2^{n}$ (here we count the empty set as a unique $(-1)$-dimensional face of the simplex $S$) and a number of $d$-dimensional faces of the simplex $S$ is equal to the number of binary sequences in $B$ with sum $d+1$ of the digits and is equal to ${n+1 \choose d+1}$. Moreover, the set $B$ has two orders. The first of them if the usual order $”\le”$ of binary naturals. The second order $”\subset”$ is a majorization. For each sequences $b,b’$ from $B$ we put $b\subset b’$ provided $b_i\le b_i’$ for each $i=0,1,\dots,n$. Clearly, $b\subset b’$ iff $c(b)\subset c(b’)$. Moreover, $b\subset b’$ implies $b\le b’$, which explains your last observation.

Answer 2

Write an $n+1$-digit binary number using leading zeros (so there are always $n+1$ digits). Let each digit correspond to a vertex of an $n$-dimensional simplex. The binary number then represents a subset of the vertices of the simplex: if the value of a digit is $1$ then the corresponding vertex is a member of the subset, and if the digit is $0$ then the corresponding vertex is not a member of the subset.

Now identify the entire simplex with the set of all vertices. Identify each of the $(n-1)$-dimensional "faces" of the simplex by the $n$ vertices that lie on that "face"; identify each $(n-2)$-dimensional "faces" of the simplex by the $n-1$ vertices that lie on that "face"; and so forth. Sooner or later you get down to subsets of $3$ points each, which you identify with the $2$-dimensional faces on which those points lie, then subsets of $2$ points each, which you identify with the edges of which the points are endpoints, and finally subsets of $1$ point each, each of which you simply identify with a vertex.

And of course the binary number corresponding to any particular subset of $k+1$ elements has exactly $k+1$ digits whose values are $1$ (and the remaining digits are zeros).

Now to make the numbers look more like "normal" binary numbers, simply don't write the leading zeros. Any subset of vertices of an $n$-dimensional simplex then can be identified with a binary number of up to $n+1$ digits.

So not only can you put the "faces" of dimension $k$ in the $n$-dimensional simplex into correspondence with the set of binary numbers up to $n+1$ digits (excluding the number $0$), but there is a simple, straightforward way to make the correspondence.

As you count these binary numbers in numeric sequence from $1$ to $2^{n+1},$ you can "construct" the corresponding objects within the simplex. A number with $k+1$ digits that are $1$ will be greater than any number that has only a subset of those digits set to $1$ (and zeros in all other digits), so you can be assured that no edge will be constructed until both its endpoints have been constructed, no $2$-dimensional face will be constructed until all the edges that bound it have been constructed, and so forth.

Since both the elements of the simplex and the binary numbers up to $n+1$ digits correspond to subsets of a set of $n+1$ elements, we can use well-known results on sets to enumerate them. The number of $(k+1)$-element subsets is $\binom{n+1}{k+1}$ for $0 \leq k \leq n,$ so that is also the number of $k$-dimensional "faces" of the simplex and the number of binary numbers (up to $n+1$ digits) in which $k+1$ digits have value $1$.