CBC arts & music podcasts. Mmmmmm. Thanks, ceallaighgirl.

(5 Comments |Comment on this)

Frost on window
The red lights are from outside.

(8 Comments |Comment on this)

Problems with representing numbers on computers, part 2
This may not make sense until you read Problems with representing numbers on computers, part 1.

( Here's part 2Collapse )

(3 Comments |Comment on this)

Problems with representing numbers on computers, part 1
notnotrebecca recently pointed out to me that online calculators incorrectly calculate 111111111*111111111. It should be 12345678987654321 (any time you multiply a string of ones by itself you get a nice symmetrical answer like that), except that the online calculators she tried consistently gave 12345678987654320 instead. (Note the zero on the end.)

( Here's what I found out. (It gets technical.)Collapse )

(5 Comments |Comment on this)

IKEA Digital Calculator

"Early Digital Calculator, Price 88¢"

( Termite insurance available at slight extra charge.Collapse )

(Comment on this)

Vector space decompositions
I think I'm beginning to understand the Primary Decomposition Theorem in Linear Algebra. Yay!

First, the Basic Decomposition Theorem says that if there exist orthogonal projection operators that partition identity, then the vector space can be written as the direct sum of the subspaces yielded by the projection operators (by their actions on the vector space, that is).

The Primary Decomposition Theorem says that, given a linear transformation T on the (finite) vector space (an endomorphism), then using the minimum polynomial of the transformation, we can construct a direct sum decomposition of the vector space. We do this by constructing orthogonal projection operations that partition identity. Specifically, the subspace yielded by a projection operator's action on the vector space ends up being the kernel of an irreducible distinct factor of the minimal polynomial (well, the factor with T substituted in for the variable). Now, the projection operators consists of the minimal polynomial, less one distinct factor (which is divided out), times some other stuff obtained using the GCD of .. things I don't feel like trying to describe in words. Anyway, the projection operator's subspace is the kernel of the missing factor.

Right?

(1 Comment |Comment on this)

3-d graphing on paper
A beautiful hand-drawn graph of for the volume of an object.

(3 Comments |Comment on this)

A gorgeous picture of the Horsehead Nebula.

(5 Comments |Comment on this)

Math problem
I came across an intriguing (if not overly complex) little math problem.

In essence, the idea is to determine the number of permutations of a set of integers, where the even numbers are not in their natural places.

Vocabulary:

• Integer: A number without a fractional or decimal part. (e.g. 2, 3, -7, 109, etc., but not 57.2 or 3.3333333...)


• Set: A collection of things, in this case integers. (e.g. {1, 2, 3} is a set containing the numbers 1, 2, and 3.) Think of taking some numbers and throwing them in a bag. That's all that a set is.


• Permutation: A way of ordering a set of things. (e.g. {1, 2, 3} and {2, 1, 3} are two different permutations of the above set.)


• Factorial: Means you multiply things. "4 factorial" is written 4! and means 4*3*2*1 = 24 (4 times 3 times 2 times 1). 6! = 6*5*4*3*2*1 = 720, etc. 1! of course is just equal to 1, and 0! is defined to be equal to 1 (because it makes sense in many many calculations to do so).

So the specific question (simplified slightly, to make possible the drawing of a diagram) is:

Given the set of integers {1, 2, 3, 4, 5, 6}, find the number of permutations (i.e. how many ways you can arrange it) in which the even numbers (2, 4, and 6) are NOT in their natural places.

e.g. {1, 3, 2, 6, 5, 4} has 2, 4, and 6 all in different places from where they started. {1, 3, 2, 5, 4, 6} on the other hand has 6 still in it's natural place where it started.

So here's how you do it.

Using a Venn diagram for illustration.



The problem is "Determine the number of permutations of {1, 2, 3, 4, 5, 6} in which no even number integer is in it's natural position." We can represent this on the above diagram. Let the entire region inside the box be the total number of permutations of the set. There are 6! of these. So we start with 6! permutations.

Now we want to exclude the permutations where "2" is in it's natural position. Let the red circle (the WHOLE circle, not just the section that is pure red) represent these permutations. If we fix "2" in it's natural position and permute the remaining five integers, we get 5! permutations. Because we started with 6! permutations (the entire region inside the box, including the red circle), we want to subtract from that the 5! permutations where "2" is in its natural position (the region of the red circle). So we get 6! - 5!.

Now, we can do the same with "4" (the green circle) and with "6" (the blue circle), and we end up with 6! - 5! - 5! - 5! = 8! - 3x5!. (Note that there are 3C1 = 3 ways to pick one even integer from the set of three even integers, and for each even integer there are 5! permutations; this is why we get 3x5!).

But note that the circles overlap, so we subtracted some regions more than once. When we subtracted the 5! permutations where "2" is fixed, and the 5! permutations where "4" is fixed, we subtracted the yellow region twice. This region represents the number of permutations where both "2" and "4" are fixed in their natural positions. Since we subtracted this region twice, we have to add it back once (so that the net result is subtracting it once). If we fix "2" and "4" in their natural positions, there are 4! ways to permute the rest of the integers. So we get 6! - 3x5! + 4!

We do similarly for "2" and "6", and "4" and "6" (the magenta and cyan regions), and end up with 6! - 3x5! + 4! + 4! + 4! = 8! - 3x5! + 3x4!. (Note that there are 3C2 = 3 ways to pick two even integers at a time from the set of three even integers. Thus, we get 3x4!.)

Now we look at the white middle region. We subtracted it three times (when we subtracted each of the circles individually), then added it back three times (when we added the regions where two circles overlap). The net result is that it didn't get subtracted, so we want to subtract it. This region represents all three even integers being fixed in their natural positions at the same time. Then there are 3! ways to permute the remaining integers. We end up with 6! - 3x5! + 3x4! - 3!.

Note that this final number represents the grey region OUTSIDE of the three circles. Quick recap: The red circle represents the permutations where "2" is in it's natural position; the green and blue circles similarly represent "4" and "6". The overlapping regions represent permutations where two of the even integers are in their natural positions (e.g. yellow represents "2" and "4" both in their natural positions.) The center region represents all three even integers being in their natural positions. So the grey region OUTSIDE the circles represents the permutations where none of the even integers is in its natural position. This is what we want, and we calculated the number of permutations represented by this region to be 6! - 3x5! + 3x4! - 3!.

The original problem used integers from 1 to 8, so it had even integers 2, 4, 6, and 8. Because of this, we'd need to have four overlapping circles for a diagram -- but you can't draw that in two dimensions. We'd have to have four overlapping spheres in three dimensions, which I can't very easily do on a web page! Better to stick with the simpler example. The procedure is the same if you have more integers; you just have to add and subtract more because there are more overlapping regions. Try it!

(5 Comments |Comment on this)

Mathematical art
Carved wooden möbius strips, courtesy of this post on mathart.

Also, beautiful mathematical metal sculptures.

I love seeing the tangible beauty in math, especially when I'm studying not very interesting math for exams. (Introductory differential equations, right now. None of the theory, no overarching elegant concepts that fit together and make sense, just a bunch of rules to learn. Introductory applied math courses aren't much fun.)

(Comment on this)

A fantastic site about fractals. Speaking of beauty in math.

(2 Comments |Comment on this)

Math poetry
ghareth_3 asked about math poetry.

I've never heard it called math poetry, but there are certainly beautiful equations and proofs. "Beautiful" tends to convey elegant, simple, yet non-trivial. A beautiful expression of math is one which states something that matters in a very elegant way.


Probably the expression most widely considered beautiful is the Euler Identity: e^iπ + 1 = 0. It relates five of the most important constants in mathematics: e, i (the square root of negative 1, which gives the so-called imaginary or complex numbers), π, 1, and 0. It's very simple, yet the reason these constants are related is complex... and amazing.


I would submit that the Pythagorean Theorem a² + b² = c² for the lengths of sides of a right triangle is beautiful.


And then there's the golden ratio. If you make a rectangle with one side of length 1 and the other side of length Phi (Φ = 1.61803...), the ratio of the longer side to the shorter side is phi (φ = 0.61803...). (This is just under two thirds.) This is called the golden rectangle, and φ is called the golden ratio or golden section. The golden ratio shows up everywhere, from art to faces to the spirals formed by sunflower seeds. The golden ratio is intimately connected to the Fibonacci Numbers: 1, 1, 2, 3, 5, 8, 13, 21, ... where each successive number is the sum of the previous two (8 = 3 + 5; 13 = 5 + 8; 21 = 8 + 13). If you divide each number by its predecessor:

13 / 8 = 1.625
21 / 13 = 1.615...
34 / 21 = 1.619...

You'll find that the result gets closer and closer to the golden ratio.


Mathematical equations and algorithms can also generate beautiful objects, as in these two strange attractors. (Lots more here.)

Or try Scott Draves' exquisite fractal flames.


Proof by contradiction sometimes gives very elegant proofs, as in the case of Euclid's proof that there are infinitely many prime numbers.

Prime numbers are numbers that can't be divided by other whole numbers. 7 is prime. 11 is prime. 13 is prime. 101 is prime. And so forth. 63 is not prime because 63 can be divided by 3 to give 31. Stated another way, 61 = 3 times 31. In general terms, a prime number is a number which can't be written as two other numbers multiplied together (ignoring a few details, this is essentially correct).

Proof by contradiction works by supposing that the opposite of what you want to prove is actually true. (For example, if I wanted to prove that 2 + 2 = 4, I'd assume that 2 + 2 does not equal 4 (please ignore the fact that this is obviously false -- in a real proof, it would be something more complex that wasn't obviously false). Then I'd start with the assumption that 2 + 2 is not 4, and logically deduce something that obviously doesn't make sense, for example, that 2 = 1. And then I say, if I started with 2 + 2 not equalling 4, and got a wrong answer, then I must have been wrong to say 2 + 2 isn't 4. So 2 + 2 must be 4.)

Euclid's proof: Suppose there are only a finite number of prime numbers. Then we could list them in order: first, second, etc. up until the nth and final one. Now, take all n of those, multiply them together, and add 1. I'll call this new number (the one I got by multiplying them and adding 1) m. But then I note that m isn't divisible by the first prime number (it would have a remainder of 1). Similarly, it's not divisible by the second... or any of the other n prime numbers. So it must be a prime number. But I supposed that I had listed all of them, yet I just found one that wasn't on the list! So I was incorrect in supposing that I could list all of them, and therefore there are infinitely many.

In more mathematical notation: Suppose there are only a finite number of primes, p₁, p₂, ..., p_n. Let m = p₁p₂...p_n + 1. m is not divisible by p₁ since it leaves a remainder of 1. m is not divisible by p₂ since it leaves a remainder of 1. ... m is not divisible by any p_i, for 1 <= i <= n. So m must also be prime. But this contradicts the assumption that p₁, p₂, ..., p_n was a complete list of primes. Therefore there are infinitely many primes.


Some other interesting proofs.

(3 Comments |Comment on this)

"f(x) takes on the value 1 at all the chairs" -- my professor, regarding functions defined on things other than numbers

(Comment on this)

Further results on finite differences
Further to my post "Sequences and differences", I realized that finite differences are indeed very much like differentiation.

First, what is differentiation? It's the study of the slope of a continuous function (a curve on a graph). More specifically, it gives you the slope at a single point on the curve. That may not sound like it makes sense, yet, but hold on.

Suppose you have a graph that looks like:



If we pick two points on the graph and draw a (green) line between them,



we get what is called a secant line. It's easy enough to calculate the slope of the line -- it goes through the points (2, 8) and (4, 64) so from the old formula, slope = rise divided by run, we get slope = (64 - 8) / (4 - 2) = 56 / 2 = 28.

Now, what happens as the second point gets closer to the first point?



See how the slope of the line changes? Now the points are (2, 8) and (3, 27), so the slope is (27 - 8) / (3 - 2) = 19.

What happens as you keep moving the second point closer and closer to the first? Well, you never have to stop moving it closer. Suppose the second point was at x = 2.1. Then you could pick x = 2.05, which is closer. In other words, there's no end to how close you can make the two points. In fact, you can make them so close you might as well think of them as a single point.

Now, as you moved them closer together, the slope of the line changes. So when we talk about the slope at a single point, we're talking about the slope of that line when the two points are arbitrarily close, so close you can think of them as a single point. (This isn't entirely accurate, but conveys the idea.)

When you have the two points arbitrarily close, it looks like this:



That's called a tangent line. See how it just touches the curve? And when we talk about the slope of the curve at x = 2 (a single point), we're talking about the slope of the tangent line.

Now, why would you want to calculate the slope of a curve? Because the slope is the rate of change of the curve. Say you're driving your car down the highway, and you have a graph of your position (in kilometers, on the vertical) against time (in minutes, on the horizontal):



The green tangent line would give you the slope of the graph at a particular time -- that is, it would give you your speed in kilometers per minute at a given instant.

Now, what of finite differences? Looking back at our discrete sequence x²:

1		4		9		16		25		...
	3		5		7		9		...

The second row is the differences between the numbers in the sequence (the sequence is the first row), i.e.
4 - 1 = 3
9 - 4 = 5
etc.

But, consider that each successive number in the sequence is a "run" of length 1: x = 1, x = 2, x = 3, ... And the "rise" is the difference between successive numbers. So the "slope" between x = 2 and x = 3 is

(3² - 2²) / (3 - 2) = (9 - 4) / (1) = 5

On a graph:



It's not a smooth curve when you connect the discrete points with lines (see how it has corners at the points?), but the finite difference (i.e. the difference of one number from the next) does indeed give you the slope of the lines between points.

(Note that there isn't anything comparable to talking about the slope AT a single point in this case, since we're not dealing with a continuous function.)

(Comment on this)

Sequences and differences
While I was in Portland, vruba introduced me to a curiosity: Take the sequence x²:

1, 4, 9, 16, 25, ... (i.e. 1 squared, 2 squared, 3 squared, ...)

Now, subtract each number from the next one:

4 - 1 = 3
9 - 4 = 5
16 - 9 = 7
...

to get this sequence:

3, 5, 7, 9, ...

Repeat this, and you end up with:

2, 2, 2, 2, ...

Put together in a table, this looks like:

1		4		9		16		25		...
	3		5		7		9		...
		2		2		2		...

Now, vruba pointed out that by assuming the bottom row is always going to consist of 2s (which it looks like it will), we can then calculate the next number in the original sequence. The 2s in the bottom row tell us that the difference between the numbers in the middle row is always 2... so the next number in the middle row should be 9 + 2, or 11:

1		4		9		16		25		...
	3		5		7		9		11		...
		2		2		2		2		...

But then that tells us that the difference between 25 and the next number in the first row is 11... so the next number in the first row shoule be 25 + 11, or 36:

1		4		9		16		25		36		...
	3		5		7		9		11		...
		2		2		2		2		...

And indeed, 36 is 6 squared, the next number in the sequence. Now, this way of figuring out the sequence might seem a little convoluted, but consider this. You might immediately recognize the first row as being squares of numbers, but a computer wouldn't. But, if you gave a computer the first row, and it used this method, it could figure out the rest of the sequence without knowing anything about the sequence other than the few numbers you gave it.

I decided to play around with this technique some more, and found some very interesting things.

First, it works for more than x². Here's x³:

1		8		27		64		125		216		...
	7		19		37		61		91		...
		12		18		24		30		...
			6		6		6		...

Again, we could figure out what the next number in the first row is by working up from the bottom row (this is called "extrapolation").

I started trying this for other things, such as x⁴ and x⁵, and noticed two patterns.

The number of rows needed before the numbers become the same ("constant") seems to the be the power of x plus 1. So for x² it takes three rows. For x³ it takes four rows. And so on.

Also, the constant number that you end up with appears to be the factorial of the power. (The best way to explain a factorial is by example. 5 factorial, written 5!, means 5*4*3*2*1. 6! = 6*5*4*3*2*1. It's just multiplication.) If you have x³, you end up with 3*2*1, or 6. If you have x⁵ you get 5!, which is 120.

Curious, no?

So I started looking for the underlying pattern. I tried looking at three consecutive, arbitrary numbers -- x, (x+1), and (x+2) -- and the sequence x². Then I looked at x³, where it gets more interesting:

x3

(x+1)3

(x+2)3

(x+3)3

...

I expanded these out and subtracted:

(x+1)³ - x³ = (x³ + 3x² + 3x + 1) - x³ = 3x² + 3x + 1

and obtained:

x3		(x+1)3		(x+2)3		(x+3)3		...
	3x2 + 3x + 1		3x2 + 9x + 7		3x2 + 15x + 19		...
		6x + 6		6x + 12		...
			6		...

See how the power goes down by one in each row, and how the coefficient on the first term (starting in the second row) is 3, then 3*2, then 3*2*1? At this point, I started wondering if it has anything to do with differentiation, since you see a similar pattern there. But I couldn't figure out how this would have anything to do with calculus. We pulled out a calculus textbook and I was going to play around with it, but I got sidetracked explaining limits and differentiation to Rebecca.

I wrote a little perl script to create these sort of tables for me, and by playing around found out that this behaviour happens for any polynomial, and that it's only the highest power that affects what the final constant will be. (Note that if there's a coefficient on the highest-power term, it carries through and the eventual constant is multiplied by the coefficient.)

I played around some more, and tried to research it on the net, but didn't turn up anything until today.

Turns out that this sort of method is called a Finite Difference and it is the discrete analogue of differentiation.

(Discrete means talking about something at specific points. e.g. the sequence of x² I was using above is what you get when you take x=1, x=2, x=3, ... and square them. If you plot x² on a graph discretely (x on the horizontal, x² on the vertical) you get:



Whereas if you treat x² continously, and you draw the graph, you get:



See how it's all points, not just certain points?)

Well, finite differences are what you do on discrete functions, whereas differentiation is what you do on continuous functions. So I was right, there is a connection.

I found several other useful pages:
Figuring out functions using finite differences
Another explanation

None of those directly explain why you get the factorial of the highest power, but I think it could be explained fairly easily (let me know if you figure it out). I haven't tried playing with it as a difference of polynomials in general form (a_kx^k + a_k-1x^k-1 + ... + a₂x² + a₁x + a₀ where a_j is the coefficient of the j^th term) yet; I suspect this would yield the result. Similar to proving the power rule in calculus. Actually, I'm sure that it could be shown that addition isn't affected across finite differences, so you could look at the polynomial term by term, and prove that a_kx^k becomes k*a_kx^k-1.

Sorry, that got a bit technical at the end... ask me if you want a simpler breakdown or explanation of anything in here.

(3 Comments |Comment on this)