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



At 05:15 AM 7/16/00 -0600, Jim Green wrote:

What is a "Hypercube" and what is its importance?

1) As to what it is... You could look it up:
http://www.m-w.com/cgi-bin/dictionary?book=Dictionary&va=hypercube

And in this case the dictionary agrees with common usage in the research
lab: A hypercube is just like a cube, but in an arbitrary number of
dimensions (D) (whereas a plain cube has D=3).

The cases where D<=3 are not excluded; a cube is a type of hypercube.

The particular case of D=4 is called a tesseract:
http://www.m-w.com/cgi-bin/dictionary?book=Dictionary&va=tesseract

Similarly, a hypersphere is just like a sphere, but in an arbitrary number
of dimensions.

Also note that amongst people who work with such things a lot, the "hyper-"
prefix gets dropped, and the things are called "cubes" or "spheres" no
matter what the dimensionality. When necessary, the term "3-sphere" is
used to designate the special case of D=3.

====================

As to the importance of considering dimensionalities other than D=3, the
list is endless. Here are some examples:

1) In the technology of error-correcting codes, without which the modem(s)
you are using right now could not function, the codewords are conveniently
represented by points in a high-dimensional space (D=128 for
example). Roughly speaking, the task of arranging suitable codewords can
be viewed as the task of arranging "circles" (actually hyperspheres of
dimension D-1) on the surface of a "sphere" (actually a hypersphere of
dimension D). It's called the "sphere packing problem" for short.

An accessible introduction to this topic is John R. Pierce, _Symbols,
Signals, and Noise_.

2) In physics of phase transitions and critical phenomena, it turns out
that many phenomena that are very complex in our D=3 world are trivial in a
D=4 world. It has been fruitful to solve some such problems in dimensionality
D = 4 - epsilon
where epsilon is a "small" number, and then extrapolate to epsilon=1 to
describe D=3. This is called "the epsilon expansion".

3) In pattern recognition, the patterns can be represented as vectors in a
high-dimensional space. Having a good intuition about how things behave in
high dimensions is indispensable if one wants to work in this field. One
deals with concepts like "sphere hardening" and "the curse of dimensionality".

A good reference is
Duda, R.D. and P.E. Hart, _Pattern Classification and Scene Analysis_ (1973)
There is also a second edition by Duda, Hart, and Stork.

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. For many applications,
this design is a sweet spot, because it is
-- cheaper to build than anything with more connectivity, and
-- easier to program than anything with less connectivity.

5) In the world wide web, hyperlinks are called hyperlinks for the
following reason: Just as the corners of a hypercube can have more than 3
nearest neighbors, a web page can have more than 3 other pages that are
nearest neighbors in the sense that they are only one click away.

Because of this, the web will never have a user interface that allows
people to navigate using a spatial metaphor such as moving up/down,
east/west, and north/south. I am quite sure of that, because there is a
theorem (which I call the flower-pressing theorem) that states that you
cannot change dimensionality in a way that is one-to-one and
continuous. Reference: Pierce, op. cit.

*) Other list members can submit their hyper-favorites.

=====================

Note that drawing a projection of a D=4 tesseract on D=2 paper is not much
trickier than drawing a projection of a D=3 cube on D=2 paper.
-- To draw a cube: make two squares and connect corresponding corners.
-- To draw a tesseract: make two cubes and connect corresponding corners.

=====================

Here's a puzzle for everybody: Derive the formula for the volume of a
hypersphere of radius R in dimensionality D. Here are the answers for the
lowest three D values:

D=1 V=2R i.e. a line segment extending for a distance
R in both directions from the center
D=2 V=pi R^2 i.e. the area of a circle

D=3 V=4/3 pi R^3 i.e. the volume of a 3-sphere.

Useless hint: The answer can be written in an elegant, compact form.

Warning: Even though the puzzle is easy to state, I don't know of a simple
way to derive the answer. If anybody has a simple derivation, please let
me know!!!!!!!!