Goodstein Sequences and Hereditary Base Notation

In mathematics, Goodstein sequences are certain sequences of natural numbers. Though they are fairly easy to define, their properties have important consequences in logic. Before investigating these, however, we give the definition. It depends on the concept of expressing numbers in different bases (well-known examples in addition to normal base-10 representations include binary, base 2, and hexadecimal, base 16). Recall that when writing a number, such as 4291, what we mean is 4 thousands plus 2 hundreds plus 9 tens, plus 1 one, alternatively expressed as

4291 = 4*10³ + 2*10² + 9*10¹ + 1.

This decomposition uses 10 as a base. Note that the numbers multiplying the powers of 10 always vary between 0 and 9. Base 2, for example, could be used just as easily, with only digits 0 and 1 as coefficients. Expressing 4291 as powers of 2 yields

4291 = 1*4096 + 0*2048 + 0*1024 + 0*512 + 0*256 + 1*128 + 1*64 + 0*32 + 0*16 + 0*8 + 0*4 + 1*2 + 1*1
= 1*2¹² + 0*2¹¹ + 0*2¹⁰ + 0*2⁹ + 0*2⁸ + 1*2⁷ + 1*2⁶ + 0*2⁵ + 0*2⁴ + 0*2³ + 0*2² + 1*2¹ + 1.

Therefore, 4291 is typically expressed in binary as the sequence of coefficients 1000011000011. However, for our purposes, it is more convenient to explicitly express the powers of the base involved, although it will simplify matters to drop those terms with coefficient 0 since they have no contribution to the sum. The equation above then becomes

4291 = 1*2¹² + 1*2⁷ + 1*2⁶ + 1*2¹ + 1.

The system described above is known as ordinary base notation, but the definition of Goodstein sequences requires a slightly modified version, hereditary base notation. This involves taking the exponents themselves and subjecting them to the same base decomposition as the original number. Since 12 = 1*2³ + 1*2², 7 = 1*2² + 1*2¹ + 1, and 6 = 1*2² + 1*2¹, the integer 4291 now becomes

4291 = 1*2^{1*23 + 1*22} + 1*2^{1*22 + 1*21 + 1} + 1*2^{1*22 + 1*21} + 1*2¹ + 1.

This expression is quite complicated, but the process is not quite finished yet! The exponents 2 and 3 within the exponents are not yet in base-2: 3 = 1*2¹ + 1 and 2 = 1*2¹. Making the necessary replacements finally gives 4291 in hereditary base-2 notation:

4291 = 1*2^{1*21*21 + 1 + 1*21*21} + 1*2^{1*21*21 + 1*21 + 1} + 1*2^{1*21*21 + 1*21} + 1*2¹ + 1.

In the general case, there may be many iterations of this process, which motivates the name "hereditary"; a base-2 decomposition is applied to the original integer and then the exponents that result, and then their exponents, and so on. The end result has only 2's as bases of exponents and only 1's as coefficients. The interested reader can verify that this type of process may be repeated for any positive integer in any base (using as coefficients positive integers less than the base), and that for a fixed number and base, the representation thus obtained is unique. The stage is now set for the definition of Goodstein sequence.

A Goodstein sequence is simply a sequence of nonnegative numbers. We may choose any number 1, 2, 3,... to begin the sequence. Next, whatever this number is, we express it in hereditary base-2 notation, just as we did with the example 4291 above. To generate the next member of the sequence, simply change every 2 in the hereditary base-2 representation to a 3, and then subtract 1 from the resulting number. This is the second member of the sequence. After that, express this second number in hereditary base-3 notation, change the 3's to 4's, and subtract one to get the third, and so on. We denote the nth member of the Goldstein sequence beginning with m by G_m(n). The first few sequences G_m die out quickly: if the seed is 1 (whose hereditary base-2 representation is just 1), there are no 2's to change to 3's so we simply subtract 1 to find G₁(2) = 0. If a sequence reaches 0, we end it there, so that the sequence

G₁ = {1,0}.

G₂ is scarcely more interesting: G₂(1) = 2 = 1*2¹ so changing the single 2 to a 3 and subtracting 1 yields G₂(2) = 1*3¹ - 1 = 2. Recall that coefficients 0-2 are allowed in hereditary base-3 notation so 2 in this notation is simply 2. There are no 3's to change to 4's, so we subtract 1 to get G₂(3) = 1. There are no 4's to change to 5's, so G₂(4) = 0 and the sequence is finished:

G₂ = {2,2,1,0}.

Beginning with 3 leads to a sequence nearly identical: the reader may try calculating the sequence. The end result is G₃ = {3,3,3,2,1,0}. However, at m = 4, new behavior emerges. 4 = 1*2^1*21, so both 2's must be replaced by 3's to get: G₄(2) = 1*3^1*31 - 1 = 27-1 = 26. In hereditary base-3, 26 = 2*3² + 2*3¹ + 2 so G₄(3) = 2*4² + 2*4¹ + 2 - 1 = 41. For the next step, we get G₄(4) = 2*5² + 2*5¹ + 1 - 1 = 60. Note that the units digit is reduced by one in each step even as the sequence increases. When it hits zero, as in this step, the coefficient of the penultimate coefficient is decreased by one: G₄(5) = 2*6² + 2*6¹ - 1 = 83 = 2*6² + 1*6¹ + 5. However, the new units digit becomes one less than the base, namely 5, so it takes more steps for this to reach zero than previously. After another five steps, we arrive at G₄(10) = 2*11² + 1*11 = 253. When changing to base 12 at the next step, we obtain G₄(11) = 2*12² + 11 = 299. The units digit again decreases for the next 11 steps, until G₄(22) = 2*23² = 1058.

The next step starts to indicate why Goodstein sequences can increase for so long: G₄(23) = 2*24² - 1 = 1151 = 1*24² + 23*24¹ + 23. Since the base is 24, we get two new coefficients of 23. Each time the units digit reaches zero, the value at which it has to start the next time doubles. The square term in the base representation does not vanish until the base reaches 402653184. And at this point the sequence has barely begun. The largest value it reaches is 3*2^402653210 - 1 at base 3*2^402653209, after which the sequence remains stable for a while before finally declining to zero. This maximum value is so astronomically large that if the digits of the number were printed at a typical font size, front and back, it would fill a stack of paper over 10 feet tall! And this is just G₄. Goodstein sequences with higher initial values increase much, much faster.

If we start with 18, for instance, since 18 = 1*2^1*21*21 + 1*2¹, replacing all the 2's with 3's gives G₁₈(2) = 1*3^1*31*31 + 1*3¹ - 1 = 7625597484989. The third term is G₁₈(3) = 1*4^1*41*41 + 2 - 1, which is about 10¹⁵⁴. The values this sequence reaches quickly become difficult to even write down. However, Reuben Goodstein himself, after whom the sequences are named, proved in 1944 a statement that became known as Goodstein's Theorem. His remarkable result showed that no matter how incalculably large the sequences become, they always terminate at 0. That is, after some finite, though possibly immense, series of steps, each sequence stops increasing eventually and decreases to 0.

The theorem's proof has significance beyond demonstrating this surprising fact about Goodstein sequences. For more, see the next post.

Source: https://www.jstor.org/stable/2268019, http://mathworld.wolfram.com/GoodsteinSequence.html