Archive

Archive for the ‘Math’ Category

RGB Cipher

Like my first haiku,
It came to me in a dream.
I saw its colors.

(Note: This will only make sense if you know a thing or two about ciphers. For the rest of you, I’m afraid this won’t be very interesting.)

Last night I had a dream that I was trying to break a cipher. But this was no ordinary cipher: instead of using numbers, it used colors. Ciphers were suddenly even more beautiful than they had been before.

When I woke up, I was dismayed to realize that it is mathematically impossible for an encryption algorithm to use colors. Nonetheless, I was infatuated with the idea.

What would it mean to have a colorful cipher? I realized that the rounds could be colored. There are three core rounds (red, green and blue) that each represent a different operation. For instance, the red round could be a data rotation, and the green round could be a substitution-box permutation.

The encryption would move through a six-round cycle as the algorithm flows through the color wheel: red, yellow, green, cyan, blue, magenta. Each secondary color represents the combination of two primary colors: yellow is a red round plus a green round, cyan is a green round plus a blue round, and similarly for magenta. Then there are the black and white rounds. The black round is no operation (maybe just adding the key to the text) and the white round is all operations. These eight colors could be arranged to paint a picture—the world’s first cryptographically-secure picture.

How exactly these colors would be arranged to create a secure algorithm, I do not know. All I know is that this is what I saw in my dream, and it was beautiful.

Categories: Cryptography, Math

Our World of Lists

The world we live in is quite an interesting place. Its structure, and especially the way that we perceive its structure, is worth observing.

When we read or write, we do so linearly. We only read one word at a time, and when we’re done, we go on to the next word. Sentences are treated as lists, where only one element at a time can be read. Our inability to comprehend anything other than lists is remarkable.

You may object to this. Sure, we read linearly, but we can also read non-linear graphs, flow charts, and even just clusters of words. While it is true that we can read such structures, we always convert them into lists, taking in one word at a time. Because time is linear, we can only perceive one thing at once before moving on to the next one. Sometimes we are able to package multiple things together and perceive them as one thing, but we cannot truly perceive more than one item at once.

Although we perceive things as lists, it is difficult to imagine things being any other way. How else could we perceive things? Perhaps in a data structure other than lists, for example binary trees, language would be more versatile. Language, of course, is not the only instance of our list perception — it is simply a very common one. What would language be like if we perceived it as a binary tree?

Well, it would be a lot less linear, that’s for sure. The whole idea of language would be a lot different, and perhaps more expressive. It’s difficult to imagine, though, just because our minds are so fundamentally grounded in lists.

The world outside of lists is an interesting one to speculate about. Where might this speculation lead?

Categories: Language, Math

Hostage Situations

May 12, 2010 1 comment

A hostage situation is a pretty common scenario (at least in movies). I often find myself questioning the actions of those involved. So I was wondering, what is the right decision in a hostage situation?

The captor is holding a single hostage, and demands something in exchange for release of the hostage. For the sake of simplicity, let’s say it is a million dollars. The negotiator has the money, and is negotiating with the captor.

The simplest set of possibilities is this. It’s very similar to the prisoner’s dilemma. Both players (captor and negotiator) can either cooperate or defect.

1. Both cooperate: Captor gets the money, hands over the hostage and escapes. Everybody wins.
2. Both defect: Negotiator doesn’t pay the captor, and the captor doesn’t hand over the hostage. The situation is the same as before.
3. Cooperate/defect: Captor hands over the hostage, but isn’t paid. Captor loses.
4. Defect/cooperate: Captor is paid, but doesn’t hand over the hostages. Negotiator loses.

In a single play, the only smart strategy is to defect. But in an iterated game, other strategies prevail.

This alone is not very interesting in itself, because it is identical to the prisoner’s dilemma. But things start to get more interesting once complications are added.

Complication 1: Killing

The captor may at any point kill the hostage. This is very bad for the negotiator, but ensures that the captor will not receive payment. Also, there is the possibility that the captor will be arrested.

At this layer, the captor should not threaten to kill the hostage. Rather, he should threaten to keep the hostage captive until the money is paid. If the hostage is killed, the captor loses all bargaining power and both parties lose.

Complication 2: Unequal Values

There is also the fact that the hostage’s life and the million dollars are not equally valued. It is possible that if the captor kills the hostage, even if he loses his million dollars, then the loss of the negotiator is a good deal greater. Since the negotiator is trying to maximize her own needs regardless of what the captor gets (at least theoretically), she will not risk the captor being killed. If the pays the million dollars but the captor still refuses to give up the hostage, this is still better for the negotiator than if the hostage were killed. But even if the captor loses the million dollars by killing the hostage, this is no better or worse than if the negotiator refused to pay the million dollars — the money is lost either way. So the negotiator has a much stronger incentive to keep the hostage alive.

Complication 3: Arrest

If the captor still has the hostage, then he is safe from arrest because he can use the hostage as leverage. But if he kills the hostage, then he can be arrested — he has lost his leverage. He cares more about his own life than the negotiators care about that of the hostage, so he has the strongest incentive yet to keep the hostage alive. The negotiator knows that a fail to pay could in result in the killing of the hostage followed by the arrest of the captor, which is even worse for the captor. It would seem that the captor no longer has an incentive to kill the hostage, which means that the negotiator no longer has an incentive to pay.

But this is not so. Remember that neither side cares if the other loses, only if they themselves win. If the captor assumes that he will be arrested if he kills the hostage, then he has no reason to kill the hostage — even if the negotiator tries to arrest him while he still has the hostage. He goes to prison either way. He no longer has an incentive not to kill the hostage, which means that the negotiator can’t expect him not to.

Despite these complications, the best way to try to maximize one’s own gain is still to defect. The captor has no incentive to release the hostage after being paid, because if he does he may be arrested. Therefore, the negotiator has no incentive to pay the money. Therefore, the captor has no incentive not to kill the hostage. Therefore, the negotiator has no incentive not to arrest the captor. Everybody loses.

This all changes, of course, in iterated hostage situations and in multiple hostage situations.

Notice that this is all just speculation; there are plenty of other options one could include in the scenario. Although I find it fascinating, I don’t know much about game theory, so I may be wrong about this reasoning.

How do other factors change the situation? Is there any way to ensure that everyone gets what they want? Discuss.

Categories: Math

Background for My Critique of “Imagining the Tenth Dimension”

In my critique of Imagining the Tenth Dimension, I referenced a couple of concepts that you may not understand very well: The Mandelbrot Set and Aleph One. This is an attempt at explaining what you need to know about those concepts in order to understand what I was talking about.

First is the Mandelbrot set. It was proposed by Beniot Mandelbrot, who effectively invented fractal geometry and is one of the most brilliant mathematicians alive today. The Mandelbrot set is a type of fractal. What is a fractal? Well, a fractal is a type of object that has self-similarity. If you zoom in on the object, it looks similar to the object as a whole. This is very useful for modeling real-life systems. Look at rocks, for example. Have you ever noticed that a small rock looks a lot like a boulder? That, if you look up close at one part of a boulder, it looks like it itself could be a boulder? Trees exhibit the same behavior: a twig with leaves on it looks like a smaller version of a tree. This is true for many types of objects.

As explained by a song:

Take a point called z on the complex plane. Let z1 be z squared plus c. Let z2 be z1 squared plus c. Let z3 be z2 squared plus c. And so on. If the series of z’s will always stay close to z and never trend away, that point is in the Mandelbrot set.

So when you do this, you end up with a graph that looks rather complicated, but exhibits self-similar properties: if you zoom in on some spots, it looks the same as the whole picture.

How does this relate to dimensions? Well, traditionally the Mandelbrot set appears on a two-dimensional graph. There is one axis for the real numbers and one for the imaginary numbers. But the set is actually three-dimensional; the third dimension is simply not represented using a spatial dimension. Instead, it is represented using color.

What is this third dimension? Well, some areas of the graph are black. A black point is part of the Mandelbrot set. But if the point is not part of the Mandelbrot set, then it is given a color, where this color represents how long it takes for the point to diverge. This is a pretty useful example of representing a dimension using something other than space.

Aleph One

This concept takes much more explanation, so try to bear with me.

Infinity was not a particularly well-understood concept until the invention of Set Theory by Georg Cantor, around the end of the 19th century. Cantor was considered to be insane by many of his contemporaries, but that’s not really the point. The point is that he effectively defined how to look at different infinities.

Cantor defined infinity in terms of infinite sets. For any finite set with N elements, the infinite set has more elements than that. The simplest example here is the set of all natural numbers. This set contains the number 1, the number 2, the numbers 3, 4, 5, 6, and so on. Any natural number you can possibly think of is contained within this set.

There are also other infinite sets of the same size. (When two sets have the same number of elements, we say that they have the same cardinality.) To prove that two sets have the same cardinality, see if you can match all their elements in a one-to-one correspondence. If you can match every element in set A to an element in set B, then the sets have the same cardinality. This can be used to prove that two infinite sets are the same size.

From this we can infer that any set of numbers that can be listed out (even if it takes forever to finish) has a one-to-one correspondence with the natural numbers; that is, the sets have the same cardinality.

Look at the set of all integers (both positive and negative whole numbers). You could try listing 1, 2, 3, etc, and when you’re done you can list 0, -1, -2, -3, etc. But the problem is, you’re never done so you’ll never get to list the negative numbers.

But there is a solution. You can list out every integer by alternating: 0, 1, -1, 2, -2, 3, -3, etc. If you continue this process, it’s impossible to name an integer that won’t be contained within this set.

It’s also possible to list every fraction and mixed number; the actual process is rather difficult to explain in a blog format, so see this page for a fun explanation. (Edit: It looks like that site is down. See this one instead.)

What about the real numbers? Surely there must be some way to list them out. To make it simple, let’s just list every number from 0 to 1. Here is such a list, in no particular order.


0.018374020....
0.487384738....
0.297998172....
0.693729348....
0.382749207....
....

Since we are talking about all the real numbers (both rational and irrational), most of these numbers will have an infinite decimal expansion.

Now we can prove that there are more real numbers than naturals by showing that it is impossible to list every real number, even given an infinite amount of time. Move down the list in a diagonal path and change every digit to something else. For example, in the first number change that 0 to a 1, in the second number change the 8 to a 9, then change 7 to 8, 7 to 8, and 4 to 5. Use these changed digits to create a new number: 0.19885…. Once you go through the entire list, you’ll have a new number. Since this number is different from every other number by at least one digit, you now have a number that you did not include on your list. But your list was infinitely long; how is this possible?

What this means is that it is actually impossible to list out every real number. Therefore, there are actually more real numbers than there are natural numbers.

Sets of infinity are named using Aleph numbers. The first infinity, that of the natural numbers, is called aleph naught. The second infinity, the infinity of the reals, is called aleph one.

This should give you a good enough understanding of the concepts to understand their relevance to my original post. If I didn’t explain it well enough, or if you want to know more, you can find plenty of information on the World Wide Web.

Categories: Math

Four Dimensions: Objection, Refutation, Objection, Refutation, Confusion

April 24, 2010 3 comments

This is a complication of a refutation of an objection to a refutation of an objection to my proof that all combinations of space and time can be represented in four dimensions. I apologize for not posting much recently, but I think that this behemoth of a post more than makes up for it.

A note on etymology: When I refer to “the universe”, I do not mean the actual physical universe that we live in. Rather, I refer to a more theoretical universe that has infinitely many points in space (it is argued by some that our universe is discrete, rather than continuous) and expands infinitely in all directions. Our physical universe is actually a subset of this much broader infinite universe. When we are talking about dimensions in a theoretical way, it makes more sense to refer to “the universe” as being infinitely large, because dimensions extend infinitely in either direction.

The objector concedes that any combination of space-time points is possible in four dimensional space. However, not every combination of space-times points is possible because the points are not all touching each other. In order to be able to move through every possible space-time, there must be a line connecting every combination of points. In mere four-dimensional space, there is no such line.

If we take space-time and drag it through a fourth spacial dimension, then each point of space will be capable of occupying infinitely many things. But this still limits each point of space to being able to move to the previous value or to the next value; it cannot move to just any value. So we need to drag space-time through a fifth spacial dimension to be able to represent every possible timeline in the universe — that is, a total of six dimensions.

If you are satisfied with this objection, please continue reading as I carry it to its absurd conclusion.

Unfortunately, six dimensions are not sufficient. If we drag 4d space-time through two more dimensions, it is still dragged as a whole unit. The different zero-dimensional points cannot move independently of each other. This may not be obvious, so allow me to use an analogy. Imagine that you have two red points. You can drag them through the first spatial dimension, and hit every possible shade of red. But what if you want the first point to darken twice as fast as the second point? Now you need a new direction. What if you want the first to darken three times faster? Now you need still another direction. It’s not hard to see that you need infinitely many directions. All these directions cannot be contained in one spatial dimension, but they can be contained in two.

But what if you want to add a third point? That one has to be able to change, too. So now you need three spatial dimensions.

What about a fourth point? You guessed it: four spatial dimensions.

Now let’s return to our six-dimensional space. For two points to be able to change brightness independently of each other, we need seven dimensions (one point can change along the sixth axis, while the other point changes along the seventh axis). For three points to be able to change independently of each other, we need eight dimensions. For four points, nine dimensions. So since there are more than infinite points, we need more than infinite dimensions. (If you’re confused, see this site for a fun explanation of how something can be bigger than infinity.)

But this itself is incorrect: it assumes that, to move through our dimensions, we must move in a straight line. Why can we not jump from point to point? We don’t jump from point to point in physical space, but there is no reason to assume that we cannot do it in other dimensions. Physically, that sort of jumping is impossible; but if we think of space not as something physical but rather as a model, then we can most certainly jump from point to point. In that case, to represent all possible brightnesses of the color red, we only need one additional dimension. Since we were just using color as an analogy, we might as well remove that dimension altogether — for now. (I’ll talk more about it later.) Additionally, the fifth and six dimensions were only added because we were assuming that we had to more in a line. Sure, a line is a convenient construct for some sorts of practical applications, but why limit ourselves to it? If we can jump around, then let’s remember that every possible point in space and time is represented within four dimensions. In that case, we can pick and choose which points we want, creating any possible timeline for any possible universe.

So now we’re back down to four dimensions. But I’ll bet I can add in some more.

You may remember that I said that color has a dimension, that saltiness has a dimension. Well, the universe contains color and saltiness. It also contains many other things. Any possible thing that can be measured independently could be considered another dimension, which means that then universe hardly requires four dimensions — it requires infinitely many. I addressed this point in my original critique.

But this objection can also be refuted, and considerably more easily. Remember that the four dimensions contain every possible point in space and time, but only space and time. Color or saltiness might be contained within space, but it’s not necessarily space. So if we are talking strictly about space and time, then there are only four dimensions.

Why, then, do we live in a universe with saltiness and color? Doesn’t that mean that we have to have more dimensions than just four? What happened here is that our model deviated from reality.

In the actual universe, color, saltiness, sound — every perceptible dimension — is really just a product of physical space. Saltiness is really just chemical reactions on your taste buds, which boils down to reactions between atoms, and even further, to reactions between quarks. Color is just the movement of light through space. Sound is just the vibration of particles in certain ways. According to the Standard Model, a point in space can only be one of so many things: one of the fundamental particles, or just empty.

But remember my previous argument about dragging color through space? Don’t we need infinitely many dimensions now?

If the universe is continuous, yes. But what if it is discrete — that is, the set of points in space is countable? In that case, it is easy to prove that we only need one more dimension.

I’m not sure how many fundamental particles (plus empty) the Standard Model predicts or how many particles there actually are, but if there are finitely many, then we can use logic similar to Cantor’s proof that rational numbers are countable to prove that we only need one additional dimension.

To make thing simpler, let’s match every particle (and the empty space) to a number. And, for the sake of convenience, let’s say that there are ten of them; the number doesn’t really matter. (If the number is one — that is, space is just space — then this proof doesn’t apply; we will still only be working with four dimensions.)

We will be moving through the fifth dimension by counting up through the numbers. If every possible combination of numbers is represented, then every possible universe can exist in five dimensions.

To start off with, let’s say that every point is set to 0. Now look at some point. Change it from a 0 to a 1. (We are now moving through an additional dimension, because this change cannot be done in space or in time.) Now change it from a 1 to a 2. Now 2 to 3. Keep counting up until you get to 9. Now you’ve covered every single combination of universes where every particle but that one is a zero.

Reset that particle to 0 and add 1 to the particle next to it. Now start counting up again with the original particle. The next time when you get to 9, add another 1 to the second particle, which now becomes 2. Do it again, and it becomes 3. Keep going until this second particle also gets to 9.

Now what do we do? Well, this time, reset the first two particles to zero and add 1 to a third particle. Keep adding numbers to the first particle again.

If we place these three particles in a row, we get a pattern that looks like this:

000
001
002
003
004
005
006
007
008
009
010
011
012
013
014
015
016
017
018
019
020

098
099
100
101
102

Gee, that sure looks familiar. We can continue to extrapolate this to every single point moving along a line, and we can represent every combination of particles using a number.

But wait: if we are moving along a line, we are missing all of the other particles that don’t fall on that line. How do we fix this problem? Well, it’s pretty simple. Instead of moving in a line, we move in a spiral. This way we hit every single particle in all of space and time. It will take a lot longer to reach the outer points, but it is impossible to name a point that won’t eventually be reached. By this process, every possible combination of particles — that is, every possible timeline of the universe — is assigned to a number.

Wait, did I say that we need five dimensions? Hardly. In this case, we can represent every possible timeline of every possible universe using a simple number line. And a number line isn’t called a line for nothing — it’s one-dimensional. That means that if our universe is discrete, then it can be represented using a one-dimensional line.

Notice that this isn’t always true. If the universe is continuous, then there is no way to enumerate all the possible points, which means that we can’t give a number to every single point in space and time. In this case, we need infinitely many dimensions to represent every possible combination of particles.

So let’s recap. If the universe is discrete, it can be represented with one dimension. If the universe is continuous but only represents space-time, then it can be represented with four dimensions. If the universe is continuous and also contains different particles, then it cannot be represented in any finite number of dimensions. If the universe is continuous and saltiness, color, etc are dimensions rather than physical constructs, then we need however many dimensions as there are measurable things — presumably infinite.

That was fun.

Categories: Math, Science

Four Dimensions: A Simple Proof

April 23, 2010 10 comments

This is a proof that four dimensions is sufficient to contain all possible spaces and times — ten are not necessary.

First, let us remember what a dimension is. Mathematically, a dimension is an axis across which something can change. Space has three dimensions, because you can change along length, width, or height. Time has a dimension because you can change through time. Saltiness also has a dimension, although it’s not particularly useful for most purposes; but even so, my science teacher informed me that oceanographers treat saltiness as a dimension.

One dimensions represents every possible value of some particular thing. A dimension could be represented with a line, which contains every possible location in one-dimensional space. It could be represented as moving through every possible shade of red, or every possible level of saltiness, or any other measurable thing that you can think of. You can also use this line to represent every possible combination of this thing: you can represent one shade of red along the redness dimension, or you can use two points to represent two shades of red, or three points to represent three shades of red, and so on.

What about when you introduce a second dimension? Now you can represent every combination of two things and every possible set of combinations. The most obvious example is length and width. On a spacial plane, you use a single point to represent length and width, and a set of points to represent many different lengths and widths.

You can also extend this into three dimensions, for example with three-dimensional space. Using the axes of length, width, and height, you can represent any point in space.

Next, bring it into the fourth dimension. If the first three dimensions are space and the fourth is time, then we are now able to represent every combination of space and time that can possibly exist. This four-dimensional construct contains all possible universes and all possible timelines.

I have an objection to this proof, as well as a refutation. It is much more complex, so I will be addressing it in an upcoming post. If you still have a problem with my proof, stick around.

Categories: Math, Science

Rampant Innumeracy

November 17, 2009 1 comment
Categories: Humor, Math