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



Regarding where Ken wrote:

Excellent. It is only necessary to know that

point x n-cube = n-cube
line segment x n-cube = (n+1)-cube
etc.

In fact, that n-cube x m-cube = (nm)-cube
^^

Right idea, but not quite. I think you mean:
"n-cube x m-cube = (n+m)-cube" here.

...
Now the number of n-tetrahedra in a D-tetrahedron is given by C(D,n).
The generating function is (x+1)^D. But what does it mean
heuristically?

I think you have the wrong generating function here. I think the
generating function for a D-simplex including all of the lower
dimensional simplices on its boundary is: ((1 + x)^(D+1) - 1)/x .

An outline of some hintful comments may be in order for the heuristic
interpretation.

First, you can think of 1 + x as being the generating function for a line
segment that includes only *one* of its end points (i.e. its a 1-ended
segment).

Second, a direct product of a 1-ended segment with a generic
D-dimensional object is a (D+1)-dimensional hypercylinder whose "height"
is the length of the segment and whose "cross section" is a copy of
the original D-dimensional set, and whose "base" is present, but whose
"top" (i.e. the end opposite to the base) is missing.

Third, if we scale the cylinder's "cross section" above by a
height-dependent factor the cylinder will have a height-dependent
(D-dimensional) 'cross-sectional width' but it will not change its
topology.

If we scale the cylinder's "cross section" at a given height by a
factor that continuously and linearly changes with height from a
factor which is unity at the base to a factor which is zero at the
"top" the cylinder becomes more "squeezed" with height all the
way down to a point at the top. IOW, by making this height-dependent
compression of the "cross section" we have turned the "cylinder" into a
"cone" or "pyramid". (Let me call it a "cone" since it is easier to
write than the longer word "pyramid".) This cone, though, is missing
its apex point because the original cylinder was missing its "top".
(IOW, if we consider z as the "height" of some "cross section" of the
cylinder where 0 <= z < L with L being the "height" of the cylinder, we
then multiply the "cross section" there by a factor of 1 - z/L to get a
"cone" whose "base" and "height" are the same as those of the cylinder
but whose apex point is missing.)

Suppose we add in a single point to the apex of the "cone". We then get
a completely closed-in cone in dimension D+1.

Now we map our discussion above to the generating functions for our sets.
Let B(x) be the generating function for the original D-dimensional object
making up the "cross section" of our cylinder & cone. Then the
generating function of the 1-open ended cylinder is (1 + x)*B(x).
(Recall the generating function of the 1-ended segment is 1 + x and we
took a direct product.) Now multiplying the cylinder by a scale factor
to make a peakless "cone" has no effect on the generating function since
the topology is the same. (It's just now very narrow on "top"). Since
the generating function of a single point is the number "1" we can get
the generating function for our fully enclosed cone by adding 1 to the
previous expression. Thus if C(x) denotes the generating function for
our "cone" then C(x) = (1 + x)*B(x) + 1 .

Now notice that a (D+1)-simplex is really a "cone" whose "cross section"
is a D-simplex and whose height extends into the (D+1)st dimension. Now
let Z(D,x) be the generating function for a D-simplex. Then our above
argument implies that:

Z(D,x) = (1 + x)*Z(D-1,x) + 1.

This is the recursion relation for our generating functions from one
dimension to the next higher one. Since we know that Z(0,x) = 1 and
Z(1,x) = 2 + x we have no problem starting up our recursion relation.

It is straightforward to solve this simple affine recursion relation
(we could use induction is so desired) to get:

Z(D,x) = ((1 + x)^(D+1) - 1)/x .

Now that we have our generating function we expand it in powers of x
(again using the Binomial Theorem, but then subtracting 1 and dividing by
x) to read off our values for C(D,n).

The final result is: C(D,n) = (D+1)!/((n+1)!*(D-n)!) .

The total number of parts for our D-simplex and its complete boundary
is S(D) = 2^(D+1) - 1 .

Neat huh?

David Bowman
David_Bowman@georgetowncollege.edu