읽고 말하기 수열과 콘웨이 상수의 증명

일전에 Look and Say Sequence에 대한 포스팅을 한 적이 있지만, 그 증명을 찾지 못해서 애석해 했던 적이 있다. 뭐 본 블로그 방문자 대부분은 이미 알고 있을 것이라 생각되지만, 노파심에서 한 번 더 소개해 본다. ㅋ

읽고 말하기 수열이란 주어진 숫자의 나열을 보고 그 숫자를 읽는 법을 그대로 다음 줄에 쓰는 수열이다. 맨 처음에는 1이 주어지는데, 이를 읽으면 ‘한 개의 1’이므로 11이 된다. 이것은 ‘두 개의 1’이 있으므로 다음 값은 21이 되고, 이번에는 ‘한 개의 2와 한 개의 1’이 있으므로 다음 값은 1211이 된다. 그 다음은 111221, 312211, 13112221, 1113213211, … 이렇게 계속 된다. gif 등의 몇몇 이미지 포맷에 쓰이는 일종의 Run-length encoding이라 생각해도 좋다.

여하간 각 단계에서 길이가 늘어나는 비율이 오늘의 관심사인데, 각 단계에서 숫자의 개수를 \lambda_n 이라 하면, 다음 극한으로 정의될 수 있다.

\displaystyle \lim_{n\to\infty}\frac{\lambda_{n+1}}{\lambda_n}

이 극한은 대략 1.30357769…에 수렴하는데, 이른바 잡기에 능한(?) Conway선생의 이름을 딴 Conway’s Constant이다. 놀라운 점은 이 값이 대수적 수이며 다음 71차(!) 방정식의 유일한 실근이다.

x71 − x69 − 2x68 − x67 + 2x66 + 2x65 + x64 − x63 − x62 − x61 − x60 − x59 + 2x58 + 5x57 + 3x56 − 2x55 − 10x54 − 3x53 − 2x52 + 6x51 + 6x50 + x49 + 9x48 − 3x47 − 7x46 − 8x45 − 8x44 + 10x43 + 6x42 + 8x41 − 5x40 − 12x39 + 7x38 − 7x37 + 7x36 + x35 − 3x34 + 10x33 + x32 − 6x31 − 2x30 − 10x29 − 3x28 + 2x27 + 9x26 − 3x25 + 14x24 − 8x23 − 7x21 + 9x20 + 3x19 − 4x18 − 10x17 − 7x16 + 12x15 + 7x14 + 2x13 − 12x12 − 4x11 − 2x10 + 5x9 + x7 − 7x6 + 7x5 − 4x4 + 12x3 − 6x2 + 3x − 6 = 0

증명을 어떻게 했는지 꽤나 궁금증을 자아내는 결과가 아닐 수 없는데, 웹서핑을 하다보니 이 증명을 설명해주는 친절한 포스트[2]가 있어 소개한다. ㅋㅋ

뭐 지금부터 본인의 설명은 이 블로그[2]의 내용을 베낀 것에 지나지 않으니 설명이 불충분하면 링크를 참조하기 바란다.

먼저 다음 표를 보기 바란다.

# 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)

표의 맨 마지막 열은 각 단계에서 등장한 수열이 다음 단계로 이전할 때 변하는 표의 번호를 가리킨다. look and say sequence에서 여덟 번째 단계에 이르면 (24)(39)가 되는데, 이 이후로는 이 표안에 갇히게 되어 모든 결과물이 이 표에 제시된 수열들의 결합으로 표현가능하게 된다.

이 표를 바탕으로 92×92 크기의 행렬을 만들 수 있는데, 행렬의 각 entry는 C_{ij} \times \ell_i / \ell_j이다. 여기서 \ell_i는 i번째 수열의 길이이고, C_{ij}는 j번째 수열이 다음 단계가 될 때 i번째 수열이 나오는 회수이다. 이 행렬을 T 라고 하자. 행렬 T는 다음 그림으로 표현가능하다.
matrix
여기서 흰 사각형은 영이고, 검은 사각형은 entry중 가장 큰 값인 2이다. 회색 사각형은 영이 아닌 값이 들어 있다. 값이 클 수록 어둡다. 물론 이 이미지는 저 블로그[2]에서 가져온 것이다.

자 이제 각 단계의 주어진 수열에 대해 벡터 v를 생각해보자. i번째 entry는 c_i \ell_i이다. 여기서 c_i는 i번째 수열이 나타나는 회수이다. Tv는 다음 단계를 묘사하는 벡터가 되고 v에 T를 곱할 수록 그 다음 단계를 가리키는 벡터가 된다. 각 벡터의 entry 합이 바로 수열의 길이가 된다. 따라서 이걸 바탕으로 각 수열의 길이를 표현하는 점화식을 만들 수 있고, 선형점화식에서 극한을 구하는 방법은 잘 알려져 있다. (아마 기본적으로는 고교 수준일 것이다. 물론 직접 계산은 안 해봤지만-_-) 다행히도 행렬에 영이 많아서 컴퓨터로 하면 그리 오래걸리지 않는다고 한다.

그리하여 92차 방정식을 얻게 되는데, 인수분해하면 x^{18}(x-1)^2(x+1)이 나오고 남은 인수가 위 소개한 71차 방정식이 된다고 한다.

 


[1] http://zariski.egloos.com/2146620
[2] A Derivation of Conway’s Degree-71 “Look-and-Say” Polynomial by Nathaniel Johnston

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중