Goodstein’s Theorem

May 20, 2008

In the previous post, I had talked about a special kind of sequence. Such sequences are called Goodstein’s sequences. And Goodsten’s theorem states that all Goodstein sequences converge to 0. Now, this is a rather counter-intuitive result given the way the series expands. Remember, in every iteration, you are increasing the base and the exponent of the terms in a sum by 1, whereas you are subtracting the whole sum by just 1. Surely, the number is increasing very rapidly notwithstanding the subtractions? For example, even a small first number, say 4, increases in this manner: 4, 26, 41, 60, 83, 109, 139, 173,…, 3319048, …, 93850207,…

How can this sum start reducing and converge to 0? One has to look more carefully to see what is happening. Let us start with a smaller number, say 3.

Iteration 1 (hereditary base-2):
(1) 3 = 2 + 1
(2) 3 + 1
(3) 3 + 1 – 1 = 3
Iteration 2 (hereditary base-3):
(1) 3 = 3
(2) 4
(3) 4 + 1 – 1 = 3
Iteration 3 (hereditary base-4)
(1) 3 = 3
(2) 3
(3) 3 – 1 = 2

See what’s happening? Firstly, note that in step(2) of iteration 1, the last term, which is 1, does not get increased, because the number is less than the current base. Say the base is n. Then increasing the base of numbers 1 through (n – 1), does not change them. For example, 2 is base 4 is 40 + 40. And 2 in base 5 is, 50 + 50. Correct? So, in this case, the last term is not increased and there is a subtraction following that.

What happens is, even when you are increasing the bases of the terms, the subtraction by 1 operation is slowly “eating” into the last term of the sum. This process may be arbitrarily slow, but eventually, it so happens that, the power of the last term in the sum “falls off”, and the last term falls into a lower base than the ongoing one, hence ceasing to increase. So then, the subtraction can now eat away the last term easily, before it starts attacking the next term (which will now be the last term).

So, you can now see that, that the sum does in fact start reducing, albeit after numerous steps, even for small numbers. In fact, you can only check this for the numbers 1, 2 and 3 by hand. You can probably write a program to check this for bigger numbers, though it might take extremely long.

***

Now, another important thing about Goodstein’s theorem is that it is one of Godel type theorems. The truth of Goodstein’s theorem cannot be proved using the axioms of first order arithmetic (Peano arithmetic). There is a proof for this, as well as a proof for Goodsteins’s theorem using techniques that are outside of Peano arithmetic.


An interesting sequence

May 16, 2008

Mandar has an interesting set of posts on convergence and divergence of infinite series. It made me recall a fascinating result I had come across once. It is not about an infinite series, though. But it is a very interesting sequence.

The sequence needs some explanation of a notation called hereditary base-n notation. Let me explain this with an example. Let us write the number 26 in its hereditary base-2 notation. First we start by writing 26 as the sum of powers of 2.
26 = 24 + 23 + 21
Next, the powers are written as sums of powers of 2 as well.
So, 26 = 222 + 221 + 1 + 21

Similarly, the hereditary base-3 notation of 1000 is the following.

1000 = 36 + 34 + 33 + 1 = 33 + 3 + 33 + 1 + 33 + 1

Note that the bases and the powers cannot be bigger than n. Also, we can write the terms as a product of a base power n and a number smaller than n. For example – 26 can be written in hereditary base-3 notation as, 2.32 + 2.3 + 2.

Now, let us take a number, say 26, and do the following:

  1. Take the number. Start with base, n = 2.
  2. Express number in hereditary-n notation
  3. The next number is formed by changing all the n’s to n+1’s. That is, “increase” the base of the sequence by 1. [n = n + 1]
  4. Subtract 1 from the above number and goto 2. [number = number – 1]

Let’s take an example. Let’s start with 4.

4 = 22 (step 2)

33 (step 3)

33 – 1 = 26 (step 4) — Iteration 1

26 = 2.32 + 2.3 + 2 (step 2)

2.42 + 2.4 + 2 (step 3)

2.42 + 2.4 + 2 – 1 = 41 (step 4) — Iteration 2

41 = 2.42 + 2.4 + 1 (step 2)

2.52 + 2.5 + 1 (step 3)

2.52 + 2.5 + 1 – 1 = 60 (step 4) — Iteration 3

60 = 2.52 + 2.5 (step 2)

2.62 + 2.6 (step 3)

2.62 + 2.6 – 1 = 83 (step 4) — Iteration 4

83 = 2.62 + 6 + 5 (step 2)

2.72 + 7 + 5 (step 3)

2.72 + 7 + 5 – 1 = 109 (step 4) — Iteration 5

And so on. Now the question is, does this sequence converge (or terminate)? If it converges, what does it converge to? Or if you think it does not converge, explain why.

As always, people who already know this result may please defer commenting.


Everybody stand back…

April 21, 2008

… I have arrived!

After numerous false starts, I have finally learnt (just) enough Perl to do the essential Unix-like file processing operations like head, tail, grep etc. on Windows. I am in my “Windows usage phase”, and there is absolutely nothing you can do through the command line. (And Windows Vista sucks even otherwise, which means soon I will be back to my “Ubuntu phase”.) I do use cygwin, but Perl is fun.


Question

April 13, 2008

I have a question that has been bothering me a bit more over the last few days than ever. What are the core computer science areas? What are the core skills that computer scientists have that researchers in other disciplines don’t have (or computer scientist have an edge over others in them)?


Quiz question

March 21, 2008

Connect the following –

  1.  
  2. Christian Goldbach, Emmanuel Kant, David Hilbert

Of Gas Bills and Modulo Arithmetic

March 17, 2008

Alright, the title is meant to be catchy; there is no real connection there. Except that it is in the context of paying my apartment gas bill I found out about a simple application of modulo arithmetic in electronic transactions in the US. (I am not talking about cryptography. Nowhere near that.) While trying to pay the gas bill through an e-cheque, I found that I had to fill in something called a “routing number” before submitting the e-cheque. Having never heard of the term before, I searched a bit and found out that the number serves chiefly as an identifier of a bank (or other financial institutions) in electronic transactions. It is a 9 digit number which identifies the location of a bank and the bank. (I think a bank can have multiple routing numbers.)

The modulo arithmetic part comes in in generating and validating a routing number. To validate a routing number the following checksum is used:

[3(d1 + d4 + d7) + 7(d2 + d5 + d8) + 1(d3 + d6 + d9)] mod 10 = 0

I don’t know why this particular checksum. And I think, the the first 8 digits are known and the last digit is generated using the above formula. Not sure who does this.

[Source: wikipedia and official ABA policy (pdf link)]

***

Incidentally, Gauss was responsible for modulo arithmetic (or clock arithmetic). The book The Music of the Primes has a nice description of this and many other beautiful things that Gauss developed. On this note, I also recall a quote in the brilliant book called Concrete Mathematics. In that book, the authors have included what are called “marginal notes” — they are actually the notes/comments written by the first set of students who got to read the draft of the book. The quote is – “It seems a lot of stuff is attributed to Gauss; either he was really smart or he had a great press agent.” On the same page, there is another marginal comment – “Maybe he just had a magnetic personality.”


Graph Toughness

March 17, 2008

A small quiz – do you know what toughness of a graph is? Hint: what does it mean to say a circle topology is 1-tough?

[If you don’t know it already, just guess; should be simple to guess. If you know it already, don’t answer for now. Don’t point to the wikipedia (or any other) page in any case :p]