Additive Number Theory is Hard

.. for example nobody has published a (correct) proof of the Goldbach conjecture that claims every even number is the sum of two primes. Maybe this isn't actually additive number theory as it concerns the addition of prime numbers, and prime numbers are the building blocks of multiplicative number theory.

But let me tell you a couple of interesting results I found recently on the internet.

Question:
Suppose I want to add some numbers and get a specified total. How many ways are there to do this?

Let's see how many ways there are to add up to 4. You have 1+1+1+1, 1+1+2, 1+3, 2+2 and 4. That makes five ways to add up to 4. Amazing. It makes sense to restrict ourselves to using positive integers, and to ignore the order of the summands. Adding up numbers like this to get a total of n is called a partition of n. So we get to say there are 5 partitions of 4.

Let's define a function!

p(n) = The number of partitions of n.

Simple aye? Here are the first few values. Notice how it grows rather quickly.

n	p(n)
1	1
2	2
3	3
4	5
5	7
6	11
7	15
8	22
9	30
10	42
11	56
12	77
13	101
14	135
15	176
16	231
17	297
17	297
18	385
19	490
20	627

This is the partition function and encodes the answer to the above question. Of course it is still hard to evaluate p(n) for a given n, so we are no closer to answering the above question. But you have to feel that by learning about this function, we are making progress.

If you restrict in some way the numbers you can use to get to your specified total, (e.g. primes or squares) then you can do some interesting maths...

Every positive whole number can be written as the sum of four squares. (The four squares theorem)

Now we know a few technical words I can share the interesting result I found.

If n = 5k+4 then p(n) is divisible by 5.
If n = 7k+5 then p(n) is divisible by 7.
If n = 11k+6 then p(n) is divisible by 11.

It seems crazy to me that the divisibility of the number of partitions of n should be related to n like this. Check them for yourself using the table I helpfully provided. The sequence of numbers in the right hand column is one that naturally turns up all over the place and people love to spot patterns in apparent randomness. I strongly suspect that the ancient Greeks or whoever had seen that these results hold for all the values they could check, but were unable to prove them in general.

These results are attributed to Ramanujan, an Indian mathematician whose genius was so unlike anything before or since that you can't help but regard him as a bit mad. His works are dense with the most complicated formulas and I am always bewildered at how he discovered them.

What is information?

So, apparently we live in the information age. But I have never found a satisfactory answer to the question: What is information? I think it is fine to not know at this time. If you went back in time to the iron age (for example) and asked the people there, "what is iron?" they would not hesitate in showing you lots of examples of iron and how they manipulate it. Now we feel we have a better understanding of iron than the people did in the iron age. We know about chemistry and stuff and how atomic properties determine the macroscopic characteristics of iron.

Similarly if you ask about information now, people are very quick to start talking about binary data and the internet and stuff. But there is a lot more to it than that.

\begin{interlude}But first, an example rant on the topic of information in the modern world: Advances in data technology has devalued music. That is not to say that modern music is any less good than it has been in the past. But rather, that as a currency it is worth less. Record companies made shedloads promoting their artists and we all bought their records and the artists enjoyed wealth and fame. But now we can (in principle) all enjoy their music for very little money now that we don't have to produce physical discs any more. I can just re-arrange a few gazillion particles inside my ATX tower (or my phone) and be listening to a hardcore trance mash-up before you can say, "Amy Winehouse". No self-respecting group of greedy music industry CEOs want you to stop giving them money (they wear cowboy hats you know) so we had all that kerfuffle about piracy and stuff. But surely it is an unmaintainable situation. We can't support the cocaine habits of all these people when information (binary data) is so cheep and easy to copy and transport. I suspect in the long run it will be a good thing for music; it will become artistic again, and have less of a mass-produced factory feel to it.\end{interlude}

If you look in a dictionary to find out what information is, you will quickly find there are two separate concepts which share the same word, just to keep things interesting. One is the binary data we all know and love, but there is the unrelated concept of knowledge and meaning. So you can say we live in an age of manipulating binary data, where we can store it and move it in great quantities, but I think we are still struggling to work out what information is. That is a deep philosophical problem.

I wanted to share a link to a factoid I acquired at some stage; the amount of data transmitted over the internet is about 1 exabyte a month. However when looking for said factoid I immediately ran into the problem has been getting me riled up and motivated this post. And that is that you can't measure some things in bytes. Instead of finding what I was looking for, I found a paragraph about how much space it would take to store all the words ever spoken by people, ever. Estimates range from 5 exabytes, to 42 zettabytes depending on if you store it in text or a digitised sound recording. But what are you actually storing? If you record it as text then you are loosing a lot of hesitations and inflections which surely contribute to the intended meaning. And even if you record all the sounds, you loose gestures and expressions.

Sure, you can take all the words ever spoken, and digitize them somehow so that it takes up lots of bytes. You can even undo the process and recover large parts of the intended meaning. But I think it is impossible to do that without loosing some of the intended meaning. And if the process is not completely reversible, what have you got stored in your bytes?

Check out this link, it makes me sad. These are the kind of people who tell you how many bytes it takes to store a person. I really don't see how you can do that when we are still struggling to understand what a person is, with unresolved questions like the mind-body dichotomy. I for one believe that I am not simply the product of electrical impulses in my brain – that I do not exist inside my cranium.

Digital information seems to be stored in specific locations. By this I mean that if you opened up your phone or your hard drive and looked at it hard enough, it is possible to say "this bit of information is stored in this physical location". I expect there are technical reasons why the preceding sentences aren't entirely true, but I am sure the premise is sound. On the other hand, I know all the words to "De Colores" and I strongly believe if you were to dissect my brain you could not say that the first instance of the word "colours" was contained in any specific location. Moreover, I believe it would be possible to remove any individual portion of my brain without affecting my memory in the slightest.. However, like all the best theories, this is completely untestable. You could never be sure you hadn't just removed a part of my brain that has nothing to do with memory.

Even if the things I know are somehow contained in my head (which I am prepared to accept is not the case), then I feel it is likely that each quantum of knowledge is equally distributed over a wide region.

Is information even quantizable? Computer says, "no". It seems nobody has thought to ask this question before. We try quantize everything we can (my favourite is the phonon) and the world is making lots of money out of binary data, so why stop to ask this question?

The concept of steganography is quite interesting and not completely unrelated to what I am trying to say in my post. It is the "art and science" of hiding one message inside another. People get all mathematical about it, looking for redundant bytes inside a file, working out how much extra information you can hide in there (measured in bytes of course) and worrying about the statistical likelihood of different patterns occurring and stuff. Which is great, I like mathematics and shit.

But surely there is another way to do it. Surely it is possible for somebody to say something, but given the correct context and background knowledge it can mean something quite different. I can't deny that the first type of steganography appears in my blog, but I think there is more of this second type.

Check out this topical story. It seems everybody is at it, although 8 billion-to-one is surely an over-estimate. Like how many words (or paragraphs) start with a K? A quick glance through my post reveals zero. And people always do rubbish maths when producing statistics for popular consuption. Sure the chance of 7 random letters spelling that particular word is 26⁷, but what about all the other combintations of 7 letters which could be considered "meaningful".

Final thoughts

Perhaps this image sums up the point I am trying to make, and like my favourite book (and potentially my blog) can be interpreted on several levels. Is it a sequence of 71552 bits of binary data? Maybe it is a picture of an American themed race-track? Maybe it is the numeral zero? Can we attach meanings to any of these interpretations, and how many bytes of information are you actually gaining when you look at it? I like to think that should the right person receive a tiny (in terms of bytes) message then they could attach to it vasts amounts of information.

New book

Yay, my new book has arrived. Let me tell you a little about it. I call it the bible according to Conway. Which is wrong in many different ways. I am (obviously) mixing two ideas: the Gospel according to X, and the Bible. Not only that, but this book isn't written by Conway - he only co-authored it. But, like the Bible, it is a collection of many different pieces all together in one hardback volume. It contains lots of lists and data on the best known results in many unsolved problems, some of which are already out of date. (Most notably, the status of the face-centred-cubic packing has changed from "the densest lattice packing and probably the best packing" to "the densest packing". But it's a great book and I am going to enjoy reading it.

It has already reminded me of the kissing number problem. In three dimensions you can fit 12 identical spheres around another sphere of the same size so that they all touch it. You can't do the same with 13 spheres touching the central one. This second fact has been suspected for centuries, but it wasn't proved until 1953. And the proof is quite simple, once you have developed your spherical geometry toolkit. I am tempted to look it up again.

This is Conway from the 70's (I suppose). When I did maths talks, I liked to use colourful props to distract from my lack of preparation. I am fairly certain that is an Escher on his shirt, surely used as a distraction from his hair. Nice beard though.

Best Thing Since Sliced Bread

SATA is one of those occasions when a new technology comes along that is better than its predecessor in every possible way. For those not in the know, SATA is the thing that is replacing (some of) those massive ribbon cables that inhabit computer cases. It is faster, and importantly smaller, meaning that air circulates more easily and computers run cooler. I am quite a fan.

And the little connectors are much easier to maniuplate than the huge ones on IDE cables.

I had no problems fitting my new hard drive, but it hasn't cured my BSoD like I expected.

Spring Greens


I discovered a new vegetable this week. Little did I know that I was eating it out of season, I guess the clue was in the name.

So many options how to cook them.

Why 2pi is better than pi

1  My opinions


1.1  2π is better than π


I spent an enjoyable few years studying maths. And during that time I kept seeing "2π" in formulas. I came to the conclusion that it is wrong that π has a special name and a symbol, and that 2π should have those privileges instead.


I didn't take it much further than that. Occasionally I would tell people my feelings on this issue in the pub, cos in those days I got to discuss maths in the pub all the time. I certainly didn't go on a massive internet crusade to do anything about it. Then years later, it was pointed out to me that this is not a new idea. And there is indeed a whole lot of people who agree with me. Check it out.


Today is the day when people stop what they are doing and remember "2π". Because in some countries the date looks like "6 . 28", which is the start of the decimal representation of this interesting value. Of course, the day is all rubbish, because some people like to write "28 . 6 . 2011". And there is nothing special about the decimal system either. Whereas the value is some magical intangible object which is completely independent of how we represent it in physical form.

Two pies

1.2 Why is it better?


Well, think about this. The circumference of a circle is πD where D is the diameter. Who uses diameters anymore? (Apart from midwives) Whereas, the circumference is also 2πr where r is the radius. And everybody likes to use radii. The above website will give you lots of information on the topic, so I am not going to bother. But in short, it boils down to the fact whenever you see a a 2π you have gone all the way around a circle. And when you see π you have gone half way, or magicked a half into your equation by some other means. (For example integrating - see below!)


2  Some maths


2.1  Area of a circle


Let's start with the junior school example, the formula for the area of a circle.

How do you derive this? How do you work out any area? You integrate! We want to integrate the constant function 1 over the inside of a circle of radius r, a region henceforth known as B_r for ball. The natural choice is to use polar coordinates, and changing to polar coordinates a sneaky r appears in the integrand.

2.2  Gaussian Distribution

Everybody's favourite probability distribution: the Gaussian distribution. If we take the "standard" one, then it has this formula:

What's that I see? A 2π. How does that get there. Well, being a probability distribution, the Gaussian has the property that

Looking at this another way, you might spot that the area under the curve

(1)

is actually √{2π}. Without going into too much detail, this 2π appears in the same way as the previous example, by integrating around a circle. It turns out that y(x) is very difficult to integrate, but if you square it and change to polar coordinates again, you end up trying to integrate

which, bizarrely, is possible. But not very interesting.


2.3  Stirling's approximation


Stirling's approximation gives you an approximation to the factorial function for large values. Here it is:

So you started by multiplying a few integers together and you end up with a 2π appearing in your maths. What!?! I did a little digging to see how this happens, and it is actually the same as the previous example, you need to evaluate the same integral integral (1). Perhaps it is not so incredible then?


2.4  Bernoulli numbers and the Reimann zeta function


The Reimann zeta function is an interesting thing, and people have written whole books on it. I just want to look at one of its many interesting properties. We only need to worry about the value of the zeta function for positive even integers, and for those values you can express the zeta function using this formula.

When you think about the zeta function at s = 2, you find you are summing the reciprocals of the squares. It's quite fun to work out the value of this sum, but I will just tell you.

Look at that, it's got π in it. Why? No idea. Let's try the same thing with s = 4.

That has a π⁴ in it. So one naturally senses a pattern forming after just two of these equations. And indeed, there is a pattern, it is usually written like this.

(2)

Where B_n are the Bernoulli numbers. Here are the first few...

If this is the first time you have seen the Bernoulli numbers then you might want to take (2) as their definition. Then you could incorporate the factor of 2²ⁿ into B_2n and you are left with a formula involving π and not 2π. However that would be a daft thing to do. The Bernoulli numbers turn up all over mathematics and most of the time, they aren't next to any pis, so you can't use them to sneakily try to change from π to 2π or back again. The appearance of 2π in this formula is pretty strong evidence that we have given a name and symbol to the wrong value.


2.5  The reduced Planck's constant


A little bit of history of physics now. Way back at the turn of the 20th century, before people had "invented" quantum mechanics, Max Planck discovered a relationship between energy and the frequency of some light and invented a new constant h to put in his equation. This came to be known as Planck's constant. Over the years, as quantum mechanics developed, physicists decided that it was better to measure the frequency of light, not in Hertz (cycles per second), but in radians. With the effect that everything gets multiplied by 2π. They found that h / 2π appeared all over their work, so invented a new constant

so that things looked neater. Even physicists want their work to look pretty.