Archive

Archive for October, 2010

A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial

October 31st, 2010

The look-and-say sequence is the sequence of numbers 1, 11, 21, 1211, 111221, 312211, …, in which each term is constructed by “reading” the previous term in the sequence. For example, the term 1 is read as “one 1”, which becomes the next term: 11. Then 11 is read as “two ones”, which becomes the next term: 21, and so on.

The remarkable thing about this sequence is that even though it seems at first glance to be quite arbitrary and non-mathematical, it has some interesting properties that were unearthed by John Conway. Most notably, he showed that the number of digits in each term of the sequence on average grows by about 30% from one term to the next. A bit more specifically, he showed that if Ln is the number of digits in the nth term in the sequence, then

where λ is the unique positive real root of the following degree-71 polynomial:

In order to demystify this seemingly bizarre fact, in this post we will show where this polynomial comes from and prove that the above limit does indeed equal its largest root (which happens to be its one and only positive real root).

The Cosmological Theorem

What lets us formally study the look-and-say sequence is a rather ominous-sounding result known as the cosmological theorem, which says that the eighth term and every term after it in the sequence is made up of one or more of 92 “basic” non-interacting subsequences. These 92 basic subsequences are summarized in lexicographical order in the following table. The fourth column in the table says what other subsequence(s) the given subsequence evolves into. For example, the first subsequence, 1112, evolves into the 63rd subsequence: 3112. Similarly, the second subsequence, 1112133, evolves into the 64th subsequence followed by the 62nd subsequence: 31121123.

# Subsequence Length Evolves Into
1 1112 4 (63)
2 1112133 7 (64)(62)
3 111213322112 12 (65)
4 111213322113 12 (66)
5 1113 4 (68)
6 11131 5 (69)
7 111311222112 12 (84)(55)
8 111312 6 (70)
9 11131221 8 (71)
10 1113122112 10 (76)
11 1113122113 10 (77)
12 11131221131112 14 (82)
13 111312211312 12 (78)
14 11131221131211 14 (79)
15 111312211312113211 18 (80)
16 111312211312113221133211322112211213322112 42 (81)(29)(91)
17 111312211312113221133211322112211213322113 42 (81)(29)(90)
18 11131221131211322113322112 26 (81)(30)
19 11131221133112 14 (75)(29)(92)
20 1113122113322113111221131221 28 (75)(32)
21 11131221222112 14 (72)
22 111312212221121123222112 24 (73)
23 111312212221121123222113 24 (74)
24 11132 5 (83)
25 1113222 7 (86)
26 1113222112 10 (87)
27 1113222113 10 (88)
28 11133112 8 (89)(92)
29 12 2 (1)
30 123222112 9 (3)
31 123222113 9 (4)
32 12322211331222113112211 23 (2)(61)(29)(85)
33 13 2 (5)
34 131112 6 (28)
35 13112221133211322112211213322112 32 (24)(33)(61)(29)(91)
36 13112221133211322112211213322113 32 (24)(33)(61)(29)(90)
37 13122112 8 (7)
38 132 3 (8)
39 13211 5 (9)
40 132112 6 (10)
41 1321122112 10 (21)
42 132112211213322112 18 (22)
43 132112211213322113 18 (23)
44 132113 6 (11)
45 1321131112 10 (19)
46 13211312 8 (12)
47 1321132 7 (13)
48 13211321 8 (14)
49 132113212221 12 (15)
50 13211321222113222112 20 (18)
51 1321132122211322212221121123222112 34 (16)
52 1321132122211322212221121123222113 34 (17)
53 13211322211312113211 20 (20)
54 1321133112 10 (6)(61)(29)(92)
55 1322112 7 (26)
56 1322113 7 (27)
57 13221133112 11 (25)(29)(92)
58 1322113312211 13 (25)(29)(67)
59 132211331222113112211 21 (25)(29)(85)
60 13221133122211332 17 (25)(29)(68)(61)(29)(89)
61 22 2 (61)
62 3 1 (33)
63 3112 4 (40)
64 3112112 7 (41)
65 31121123222112 14 (42)
66 31121123222113 14 (43)
67 3112221 7 (38)(39)
68 3113 4 (44)
69 311311 6 (48)
70 31131112 8 (54)
71 3113112211 10 (49)
72 3113112211322112 16 (50)
73 3113112211322112211213322112 28 (51)
74 3113112211322112211213322113 28 (52)
75 311311222 9 (47)(38)
76 311311222112 12 (47)(55)
77 311311222113 12 (47)(56)
78 3113112221131112 16 (47)(57)
79 311311222113111221 18 (47)(58)
80 311311222113111221131221 24 (47)(59)
81 31131122211311122113222 23 (47)(60)
82 3113112221133112 16 (47)(33)(61)(29)(92)
83 311312 6 (45)
84 31132 5 (46)
85 311322113212221 15 (53)
86 311332 6 (38)(29)(89)
87 3113322112 10 (38)(30)
88 3113322113 10 (38)(31)
89 312 3 (34)
90 312211322212221121123222113 27 (36)
91 312211322212221121123222112 27 (35)
92 32112 5 (37)

The important thing about this particular basis of subsequences is that the evolution of any sequence made up of these subsequences is determined entirely by the evolution rule for the subsequences given in the final column of the above table. For example, the eighth term in the look-and-say sequence is 1113213211 = (24)(39). The subsequence (24) evolves into (83) and the subsequence (39) evolves into (9), so the ninth term in the look-and-say sequence is (83)(9), which is 31131211131221.

Computing the Number of Digits in Sequences

Since the evolution of every term in the look-and-say sequence after the eighth can be computed using the table above, we can easily compute the length of every term after the eighth as well. For example, the eighth term in the sequence evolves into (83)(9), so the number of digits of the ninth term in the sequence is 6 + 8 = 14. The subsequence (83) evolves into a subsequence with 10 digits, and (9) evolves into a subsequence with 10 digits, so the tenth term in the look-and-say sequence has 10 + 10 = 20 digits.

All of the information about how the lengths of the 92 subsequences change can be represented in a 92×92 matrix T. In particular, the matrix T has its (i,j) entry equal to Cij × ℓi/ℓj, where Cij is the number of times subsequence (i) appears in the evolution rule for subsequence (j) and ℓi is the length of subsequence (i). This matrix is represented in the following image – white squares represent zero entries in the matrix, and black squares represent the number 2, which is the largest value present in the matrix. Shades of grey represent non-zero numbers, with larger numbers being darker.

Then if we represent a term in the look-and-say sequence as a vector v with its ith entry being ci × ℓi, where ci is the number of times the subsequence (i) appears in that term, we find that the sum of the entries in v is the total length of that term of the look-and-say sequence. More important, however, is the fact that the sum of the entries in Tv is the length of the next term in the look-and-say sequence. The sum of the entries in T2v is the length of the next term in the look-and-say sequence, and so on. So we have found a degree-92 recurrence relation for the length of terms in the look-and-say sequence, and the corresponding transition matrix is T.

Computing the Limit

It is a basic fact of linear homogeneous recurrence relations that a closed-form solution to the recurrence relation can be written down in terms of the eigenvalues of the transition matrix (see the linked Wikipedia page for specifics). As a corollary of this, the limiting ratio of terms in the sequence is equal to the spectral radius of the transition matrix. Fortunately, the transition matrix in this case is quite sparse, so its characteristic polynomial isn’t too difficult to compute:

Indeed, the degree-71 polynomial that λ is a root of is one of the factors of the characteristic polynomial of the transition matrix T. All that remains to do is to get MATLAB to compute the largest root of that polynomial (i.e., the spectral radius of T):

>> max(abs(eig(T)))

ans =
    1.303577269034287

The matrix T is attached below for those who would like to play with it. Something fun to think about: what do the rational eigenvalues (-1, 0, and 1) of T represent?

Download: Transition matrix [plaintext file]

Update [March 17, 2013]: Entry 91 of the subsequence table has been corrected – thanks to Marcus Stuhr and liuguangxi for the correction.