Wednesday, 18 June 2008

What you can do with Information Theory

You can get some bounds on the number of prime numbers, for one thing.

In the latest newsletter of the IEEE Information Theory Society there are some really neat calculations of lower bounds on the number of prime numbers under N [1]. I've been thinking about what significance there is to the fact that it is information theory that is being used to do this. Is it just a set of maths tools, like any others, or is it using the fact that it is 'information'.

FWIW, this is where I've got to.

A difficulty I've always had with any mathematical proof is what goes on between the lines. I write:

a < b + 3
b > a - 3

The 'therefore' seems pretty obvious to me, and I know that mathematicians will be able to come up with rigorous arguments as to why and under what conditions that 'therefore' is valid or not, as the case may be, but it seems to me that there will always be steps that take place inside your head. The reasoning will always require some sort of mental assumptions.

The proof you use in any specific case is therefore sitting on top of some internal reasoning. So, if you use information theory in the proof, there are some assumptions about information used in the argument. And in answer to my question; yes, it is a mathematical proof just like any other, but also, yes it does make use of 'information'.

Like everything I put in this blog, this needs working through more rigorously, in that mythical future when I've got time to do it.

[1] Ioannis Kontoyiannis. Counting Primes Using Entropy. IEEE Information Theory Society Newsletter Vol. 58, No. 2, June 2008. It will eventually appear here.

1 comment:

David Chapman said...

I think Penrose is covering a similar point to this - my problem with steps in the maths when he says this:

DO WE know for certain that 2 plus 2 equals 4? Of course we don't.

Maybe every time everybody in the whole world has ever done that calculation and reasoned it through, they've made a mistake. Maybe it isn't 4, it's really 5.

There is a very, very small chance that this has happened. But now I am talking about probabilities: I am using mathematics again, on the basis that it makes sense in the first place. So my reasoning is circular and, as often happens, you have to stand back and ask, well, what is reasonable?

In his article in the New Scientist item on Reason.