증명에 사용된 가장 큰 수 그레이엄수(Graham's number)

[손님]

가장 큰 수를 가리키는 말은 무엇일까?

우리 고유어에서는 ‘온’(100), ‘즈믄’(1000)까지가 확인될 뿐, 이외에 ‘골’이나 ‘잘’ 따위가 있었다고는 하나 정확한 수치나 쓰임은 확인되지 않으며 천, 만, 억, 조와 같은 중국에서 유래한 한자 명수법이 보편화 되어 있다. 이에 의하면 10⁶⁴에 해당하는 무량수(無量數)가 최대의 수이다. 한국, 중국, 일본 등 한자문화권에 공통적으로 통용되는 명수법이다.

한편, 인도의 수 개념에 근간을 두고 독특한 자승(自乘) 방식을 취하는 불경의 수 체계에 따르면 문헌마다 차이가 있기는 하나 《화엄경》에 나오는 124개의 수 중 가장 큰 단위인 불가설불가설전(不可說不可說轉)은 10^{37,218,383,881,977,644,441,306,597,687,849,648,128}에 이르는 큰 수이다. (☞ 보충자료)

영미권에서 사전에 수록된 가장 큰 수는 센틸리온(centillion)으로 영국식 기수법으로는 10⁶⁰⁰, 미국식으로는 10³⁰³에 해당된다. 미국의 수학자 Edward Kasner의 조카 Milton Sirotta에 의해 만들어진 구골(googol)은 10¹⁰⁰을, 그리고 구골플렉스(googolplex)는 10^googol (10¹⁰¹⁰⁰)을 나타내나, 단지 특별하게 큰 수를 상정하기 위해 고안됐을 뿐 실제적 의미를 갖지는 않는다.

수학 증명에 사용된 가장 큰 수로 기네스북에까지 오른 수가 있으니 바로 그레이엄수(Graham's number)이다. 이 수는 구골플렉스와도 비교할 수 없을 만큼 클 뿐만 아니라, 지수 형태(거듭제곱꼴)로는 표현할 방법이 없어 특수한 화살표 기호를 정의하여 나타내야 한다.

정리: “n차원 초입방체의 2ⁿ개의 꼭지점을 모두 연결하고, 이 선들을 2가지 색을 사용해 칠한다. 이 때 n이 충분히 크다면 칠하는 방법에 상관없이 동일 평면상에 있는 네 점을 연결한 선이 모두 같은 색인 것이 반드시 존재한다.”

위 정리에서 ‘충분히 큰 n’이 어느 정도 커야 하는가에 대한 답으로 그레이엄수 이상이 되면 성립한다는 것이 그레이엄 자신에 의해 증명된 바 있다.

이 문제는 아직 해결되지 않았는데 그레이엄수는 상계(upper bound)로 알려져 있으며, 마틴 가드너(Martin Gardener)는 그의 저서에서 ‘6’이라 하였고, Geoff Exoo는 하계(下界)가 11인 것을 보였다.

그레이엄수는 다음과 같이 정의된다.

자연수 x, y에 대해 연산자 ↑는 다음과 같다:

x↑y = x^y

또, ↑↑는 다음과 같이 귀납적으로 정의한다.

x↑↑2 = x↑x = x^x

x↑↑3 = x↑(x↑x) = x^xx

...

x↑↑y = x↑(x↑↑(y-1)) = x↑x↑x↑.....↑x (y개) = x^xx... (y개)

마찬가지로 ↑↑↑는 다음과 같이 정의한다.

x↑↑↑2 = x↑↑x

x↑↑↑3 = x↑↑x↑↑x

...

x↑↑↑y = x↑↑(x↑↑↑(y-1)) = x↑↑x↑↑x↑↑...↑↑x (y개)

이와 같이 하여 ↑↑↑...(n개)...↑ = ↑ⁿ를 정의한다.

x↑ⁿ2 = x↑^n-1x

x↑ⁿy = x↑^n-1(x↑ⁿ(y-1))

이 정의를 이용하여 함수 G(x)를 다음과 같이 정의한다.

G(x) = 3↑^x3

이 때, G⁶⁴(4)를 그레이엄수라 한다.

G(X)를 계산해 보면,

G(1) = 3↑3 = 3³ = 27

G(2) = 3↑↑3 = 3↑(3↑↑2) = 3↑(3↑3) = 3↑27 = 7625597484987

G(3) = 3↑↑↑3 = 3↑↑(3↑↑↑2) = 3↑↑(3↑↑3) = 3↑↑G(2) = 3↑↑7625597484987

G(4) = 3↑↑↑↑3 = 3↑↑↑G(3)

이처럼 급격히 증가하여 이미 G(3) 이후부터 계산이나 표기가 곤란하다.

G²(4) = G(G(4)) = 3↑.....{G(4)개}.....↑3

G³(4) = G(G²(4))

.....

이와 같이 증가하여 G⁶⁴(4)에 이른 것이 그레이엄수이다.