May 25, 2007

Visualizing the fourth dimension, Part 2

Part 1 here. To construct a 4-D hypercube, we first need to make a slight detour into graph theory. All proofs are secluded in an Appendix at the end, for the math nerds -- and for my own benefit, since I need to get back into the habit of writing proofs. We're going to use Hasse diagrams, which can be seen below.


What these two diagrams show is a set of elements and a relationship among the elements. To pick a familiar example, I chose some natural numbers {1, 2, 3, 6}, and the "divides" relation. We say "a divides b" and write a | b if and only if b = a*n, for some integer n. For example, 2 | 6 because 6 = 2*3. To show a | b in the graph, we draw an edge between a and b, with an arrow going from a to b. We get the graph on the left. For all a, a | a since a = a*1, so this relation is reflexive. For all a and b, if a | b and b | a, this implies that a = b (see Appendix), so this relation is antisymmetric. And for all a, b, and c, if a | b and b | c, this implies that a | c (see Appendix), so the relation is transitive. So, the "divides" relation is a partial order on the set of natural numbers.

Anytime the relation is a partial order of the set of elements, then a lot of the detail in the graph is superfluous. We don't need the self-loops, which only state what's true by definition, namely that a | a. We also don't need the arrows, since we can orient the graph so that we understand that the arrows always point upward -- they can never point back downward since that would imply a | b and b | a for distinct a and b, a violation of the antisymmetry property. And we don't need the extra edges that demonstrate transitivity, such as the edge going from 1 to 6 -- we could go from 1 to 6 indirectly through either 2 or 3. The result is a Hasse diagram, shown on the right in the picture above. Much cleaner. To cut to the chase, I chose 1 as the "origin" since 1 divides any natural number, and I chose 2 and 3 as the first numbers to branch out from the origin since they are co-prime -- they don't have any common factors aside from 1. This makes their axes go in different directions. Then, 2 and 3 bend into their least common multiple, 2*3 = 6. This is also the "terminal" point.

To move into 3-D, we need another axis that will be relatively prime to the two we already have -- the simplest way is to pick the next prime number for each new axis. So that would be 5, and our 3-D cube is the Hasse diagram below. We start with the same origin, 1, and we now have 3 co-prime axes which hit 2, 3, and 5 in the first step of branching. Then, 2 and 3 bend into their lcm = 6, 3 and 5 bend into their lcm = 15, and 2 and 5 bend into their lcm = 10. Each pair of "intermediate points" -- 6 and 10, 15 and 10, and 6 and 15 -- bend into the same lcm = 30, which terminates the branching and bending.


Now, this 2-D picture only allows us to see a single cube within all of 3-D space. If we wanted to improve our vision beyond extreme myopia, we'd need to allow each prime axis to continue infinitely, rather than stop after the first multiple of 2, 3, and 5. It's tedious to draw lots of these cubes, so I just drew one more cube in our 3-D space that we can visualize in our 2-D picture:


Because we went two steps instead of just one along the 2-axis, we can see one cube further in that direction. If you have nothing better to do, you can draw out what the cubes would be if we went one more step in along the 3-axis and the 5-axis, giving you four cubes in total (the original plus one new one in each direction). If you were really bored, you could then fill in the remaining four cubes to see a 2-by-2-by-2 cube. (As a guide for the bored, the axes would branch to 4, 9, and 25, and the terminal point of the entire cube would be their lcm = 900).

As an aside, what if we relabled the vertices logarithmically, so that each coordinate along the n-axis was just the exponent to which n is raised in the prime factorization of that vertex? For example, 4 = (2^2)*(3^0)*(5^0), and we'd re-label 4 as (2, 0, 0), where the 1st coordinate is the power of 2, the 2nd is that of 3, and the 3rd is that of 5. In the same way, 15 = (2^0)*(3^1)*(5^1), and we'd label 15 as (0, 1, 1). If we treat a vertex as a vector that starts at the origin and ends at that vertex, we could take the dot product of 4 and 15 = (2, 0, 0) x (0, 1, 1) = 2*0 + 0*1 + 0*1 = 0 + 0 + 0 = 0, implying that 4 and 15 are "perpendicular" or orthogonal. That is, the angle from 4 to 1 to 15 is a right angle. In our graph, being co-prime implies being orthogonal and vice versa (see Appendix).

In the next part of this series, we'll analogize these ideas to draw a Hasse diagram of a 4-D hypercube. I'm going to wait a bit since this post itself has eaten up enough of my time today, and since readers may want to see if they can do it on their own first. It's also worth taking time to let everything sink in.

Appendix. To prove the transitivity of "divides," assume a | b and b | c. Then b = a*n and c = b*m, where n and m are natural numbers. Replacing b with a*n, the second equation says c = (a*n)*m, and since multiplication is associative for natural numbers, we can write c = a*(n*m). Because the natural numbers are closed under multiplication, (n*m) is also a natural number; call it q. Then we have c = a*q, which we can rewrite as a | c, as required. (_)(_)

To prove the antisymmetry of "divides," assume a | b and b | a. Then b = a*n and a = b*m, where n and m are natural numbers. Replacing b with a*n, the second equation says a = (a*n)*m, which by associativity implies a = a*(n*m). Since a = a*1, we can rewrite this as a*1 = a*(n*m), which by cancellation implies that 1 = n*m. Since 1 is the identity element for multiplication in natural numbers, and since the natural numbers don't have multiplicative inverses except in the case of 1, whose inverse is 1, this implies that n*m = 1*1, or n = 1 and m = 1. Substituting into the original equations, we get b = a*1 and a = b*1, or a = b, as required. (_)(_)

To prove that co-prime numbers are orthogonal (and vice versa) in our Hasse diagram with logarithmically scaled axes, assume we have a n-dimensional cube, infinite in dimension since there are infinitely many prime numbers. Assume two natural numbers a and b are co-prime: by definition they have no factors other than 1 in common. That implies that they cannot both have a non-zero coordinate along the n-th axis (otherwise they would share prime factor n). So, if a = (a_1, a_2, ... , a_n) and b = (b_1, b_2, ..., b_n), then for all a_n and b_n, either a_n = 0 and b_n =/= 0, or a_n =/= 0 and b_n = 0, or both a_n = 0 and b_n = 0. No matter which case we have, (a_n)*(b_n) = 0 for all a_n and b_n in the respective vectors, so that the dot product a x b = 0 + 0 + ... + 0 = 0, indicating that a and b are indeed orthogonal.

Conversely, assume that a and b are orthogonal, which means their dot product a x b = 0. Expanding the dot product, we have (a_1)*(b_1) + (a_2)*(b_2) + ... + (a_n)*(b_n) = 0. Because the vertices in our graph are natural numbers, and because the vertices along a given axis represent multiples of a (prime) natural number, none of the a_n or b_n can be negative. Let's see why not. The a_n (or b_n) can be 0 if the prime factorization of a (or b) includes a 0-th power along the n-axis. But if we assume that a negative power were allowed, then along this n-th axis, we would have n^(-m), for m a positive integer, in the prime factorization of a (or b). Since n^(-m) = 1/(n^m), somewhere within the rest of the product of the prime factorization there would have to be a positive integer multiple of (n^m) in order for the entire product to multiply to an integer, rather than a non-integer rational number. But we have already accounted for the power along the n-th axis when we stipulated that it was (-m), and since all axes are mutually co-prime (they are distinct prime numbers), there is no axis along which we can retrieve more powers of n. Our prime factorization would then be a non-integer, contradicting our choice that it represented a natural number; so, all of the a_n and b_n are non-negative integers.

Now, if the sum of products of pairs of non-negative integers adds up to 0, it is not possible for the elements of a given pair (a_n)*(b_n) to both be positive. Assume it were possible, i.e., that both (a_n) and (b_n) in the term (a_n)*(b_n) were positive. Then for the entire sum to add up to 0, somewhere in the rest of the sum there would have to be elements (a_m) and (b_m) such that (a_m)*(b_m) = -1*(a_n)*(b_n). Both sides of this equation are negative under our assumption, implying that either (a_m) is negative or (b_m) is negative (but not both). However, we've already shown that negative values for the a_n and b_n are impossible, making a contradiction. Therefore, we have that both elements of a product must be non-negative, and that at most one of them may be positive, implying that either a_n = 0 and b_n =/= 0, or a_n =/= 0 and b_n = 0, or both a_n = 0 and b_n = 0. Since these represent powers of the prime number along the n-th axis, this implies that a and b have no factors in common other than 1 -- that is, they are co-prime. Combining this with our previous result, we have proved that natural numbers a and b are co-prime if and only if they are orthogonal in our suitably scaled Hasse diagram. (_)(_)

I've seen Hasse diagrams using prime number axes and the "divides" relation before, but I don't know of any comment on co-prime-ness and orthogonality implying each other when the axes are scaled logarithmically -- just drawing the axes perpendicularly doesn't make them so. I searched Google but didn't find anything to this effect, so I hope I'm the first person to prove this observation. Realistically, it's not that hard to see if you were paid to think about this stuff all day, so I'm sure some professional mathemitician somewhere has figured it out, and that the results are in an article or book chapter that didn't show up on a Google search.

Addendum 6/19: I just realized I probably got myself into trouble by introducing infinite vector spaces (one dimension for each prime number), as I haven't finished an analysis course yet. So let me water down the model to one where the vector space is finite in dimension, though as large as you want it to be. Good enough for the present purposes.

1 comment:

  1. Regarding Addendum 6/19: [...] introducing infinite vector spaces (one dimension for each prime number)

    I've had a similar idea and I'm curious if there already are articles on this topic (that's how I found this one). I can't seem to find much on the net, but then again maybe I'm just using the wrong keywords.

    ReplyDelete

You MUST enter a nickname with the "Name/URL" option if you're not signed in. We can't follow who is saying what if everyone is "Anonymous."