Chronology Current Month Current Thread Current Date
[Year List] [Month List (current year)] [Date Index] [Thread Index] [Thread Prev] [Thread Next] [Date Prev] [Date Next]

Re: Hypercube



David Bowman wrote:

Regarding John D.'s comment about the vertices of a hypercube:
...
4) In computer architecture, it is common to connect multiprocessors using
a the topology of a hypercube. Note that a plain old 3-cube has 8 corners,
each of which is connected to 3 neighbors; in a hypercube there are 2^D
nodes each of which is connected to D neighbors. ...

This has inspired me to propose problem/puzzle about how various
dimensionality hypercubes are put together in terms of lower dimensional
hypercubes. Let's first define a *single point* (such as a vertex or
corner that lies at the ends of various line segments or edges in a
higher dimensional hypercube as a 0-dimensional hypercube (or 0-cube for
short). We define a *line segment* that defines a common edge of some
squares that bound a higher dimensional hypercube as a hypercube of
dimension 1 (or 1-cube for short). In this case we consider the line
segment/edge/1-cube as an open set that does *not* include its end
points. We define a *square* that forms common faces on the boundary of
a higher dimensional hypercube as a 2-dimensional hypercube (or 2-cube
for short). In his case we consider the 2-cube to *only* include the
open set interior of the square *not* including its outer boundary edges.
We iterate these constructive definitions in higher dimensions as needed
to discuss the boundary of some given hypercube. In each case the
definition of a given boundary hypercube is supposed to only include its
*interior* points as an open set and *not* include any of its own
boundary. So in general a D-cube will be bounded by a collection of
(D-1)-cubes. Each of these will, in turn, be bounded at common joints by
a collection of (D-2)-cubes. These, in turn will be bound and joined
together by a collection of (D-3)-cubes. This continues until we go all
the way down to the 0-cube vertices or corners of the original hypercube.

For instance, if we considered the set made up of a single 1-cube and its
boundary this set would consist of 2 0-cubes at the ends of the 1-cube
*and* would include the 1-cube itself. (IOW, the closed line segment is
made of the segment's interior and its two end points.)

If we considered the closed set made up of a single 2-cube *and* its
complete boundary set, that set would be made of 4 0-cubes (i.e.
vertices), 4 1-cubes (i.e. edges), and 1 2-cube (interior of the square).

If we considered the closed set of an ordinary cube including all of its
boundary that set would consist of 8 0-cubes (vertices), 12 1-cubes
(edges), 6 2-cubes (faces), and 1 3-cube (interior of the cube).

Now consider a generic D-cube (i.e. D-dimensional hypercube) whose
boundary is made up of various lower dimensional hypercubes. Let N(D,n)
be the total number of n-cubes that are included in the set comprising
the original D-cube *and* all of its boundary pieces.

Question A: What is the closed form formula for N(D,n)?

Question B: What is the closed form sum total number S(D) of 'parts' that
make up the complete closed set of the D-cube *and* all of
its boundary pieces? IOW, S(D) = SUM{n = 0 to D, N(D,n)}.
Find S(D) in closed form.

Hints: From our above discussion we know that:

N(0,0) = 1
N(1,0) = 2 N(1,1) = 1
N(2,0) = 4 N(2,1) = 4 N(2,2) = 1
N(3,0) = 8 N(3,1) = 12 N(3,2) = 6 N(3,3) = 1

I worked the first part of this out to my own satisfaction a few years
ago, when I was trying to explain some ideas regarding dimensions >3 to
a class of non-science students. First, note that I built the table
above by the following rules:

1. N(D,D) = 1.
The D-cube contains exactly one example of a D-cube.

2. N(D+1,0) = 2 N(D,0), for D>=0.
As you increment the dimension D, you double the number of
vertices/points.

3. N(D+1,n) = N(D,n-1) + 2 N(D,n).
As you increment the dimension D, you double the number of dimension
n-sub-cubes you had before, plus every dimension (n-1)-subcube which you
had before is extended to become a new n-cube.

Example: Move a square through the third dimension: we had 4 lines in
the initial square, there are also 4 lines in the "final square" (where
we stopped extending into the 3rd dimension), so we doubled the number
of lines. But each _point_ in the initial square extrudes a new line as
we move into the 3rd dimension, so the number of lines is 2(4) + 4 =
12. Similarly, all entries in the interior of the table above can be
formed by doubling the number above and adding its neighbor on the
left. For instance, the next row is:

N(4,0) = 2(8) = 16. [By rule 2.]
N(4,1) = 2(12) + 8 = 32. [By rule 3.]
N(4,2) = 2(6) + 12 = 24. "
N(4,3) = 2(1) + 6 = 8. "
N(4,4) = 1. [By rule 1.]

Now, find the formula that describes the table:

N(0,0) = 1
N(1,0) = 2 N(1,1) = 1
N(2,0) = 4 N(2,1) = 4 N(2,2) = 1
N(3,0) = 8 N(3,1) = 12 N(3,2) = 6 N(3,3) = 1
N(4,0) = 16 N(4,1) = 32 N(4,2) = 24 N(4,3) = 8 N(4,4) = 1

Clearly there are lots of powers of 2 here, more in the first column
than in the second, etc. Try dividing through by 2^(D-n):

N(0,0)/2^(0-0) = 1
N(1,0)/2^(1-0) = 1 N(1,1)/2^(1-1) = 1
N(2,0)/2^(2-0) = 1 N(2,1)/2^(2-1) = 2 N(2,2)/2^(2-2) = 1
N(3,0)/2^(3-0) = 1 N(3,1)/2^(3-1) = 3 N(3,2)/2^(3-2) = 3
N(3,3)/2^(3-3) = 1
N(4,0)/2^(4-0) = 1 N(4,1)/2^(4-1) = 4 N(4,2)/2^(4-2) = 6
N(4,3)/2^(4-3) = 4 N(4,4)/2^(4-4) = 1

Pretty. So:

Answer to Question A:

N(D,n) = 2^(D-n) C(D,n) = 2^(D-n) D! / [n! (D-n)!]

For Question B, adding entries in the first few rows points us to the
surprising conclusion that S(D) = 3^D. How fun! To prove this, let's
fall back on the rules I gave above to derive the entries in the D-th
row. I'll reorganize/rewrite them to make it easier:

2'. N(D,0) = 2^D. This can easily be proven from 2 [N(D+1,0) = 2
N(D,0), for D>=0] by induction.
3'. N(D,n) = N(D-1,n-1) + 2 N(D-1,n), for 0<n<=D. This is just a
reindexing of 3.
1'. N(D,D) = 1. (reindexing of 1)

Now,
S(D) = SUM{n = 0 to D, N(D,n)}
= N(D,0) + SUM{n = 1 to D-1, N(D,n)} + N(D,D)
= 2^D + SUM{n = 1 to D-1, N(D,n)} + 1
= 2^D + SUM{n = 1 to D-1, N(D-1,n-1) + 2 N(D-1,n)} + 1
= 2^D + SUM{n = 1 to D-1, N(D-1,n-1)} + SUM{n = 1 to D-1, 2
N(D-1,n)} + 1
= 2^D + SUM{n = 0 to D-2, N(D-1,n)} + 2 SUM{n = 1 to D-1, N(D-1,n)}
+ 1
= 2^D + [SUM{n = 0 to D-1, N(D-1,n)} - N(D-1,D-1)] + 2 [SUM{n = 0
to D-1, N(D-1,n)} - N(D-1,0)] + 1
= 2^D + [S(D-1) - 1] + 2 [S(D-1) - 2^(D-1)] + 1
= 2^D + S(D-1) - 1 + 2 S(D-1) - 2^D + 1
= 3 S(D-1).

This gives the recurrence relation that the sum of each row is 3 times
that of the previous row. Now proceed by mathematical induction to show
that S(D) = 3^D:

<> S(0) = 3^0 = 1. (True, checked by adding all the elements on the
first row.)
<> Assume that for some d >= 0, S(d) = 3^d.
<> Show that S(d+1) = 3^(d+1):
S(d+1) = 3 S(d) (from above work)
= 3 (3^d) (by induction hypothesis)
= 3^(d+1).

Thus,

Answer to Question 2:

For all D>=0, S(D) = 3^D.


Have fun!

David Bowman
David_Bowman@georgetowncollege.edu

Thanks, I did!

Ken