그레이엄 수

또 다른 그레이엄 수에 대해서는 벤저민 그레이엄 수 문서를 참고하십시오.

그레이엄 수(Graham's number)는 미국의 수학자 로널드 그레이엄이 이름을 붙인 특정한 자연수의 명칭으로, $G$로 표시한다. 램지 이론에 대한 수학 문제의 해결 과정에서 상계(upper bound)로 제시된 큰 수이다. 그레이엄 수는 구골플렉스보다도 훨씬 큰 스큐스 수나 모서 수보다도 훨씬 크다. 마찬가지로 각 자릿수마다 측정 가능한 가장 작은 길이인 플랑크 길이만큼의 부피를 차지한다고 가정해도 그레이엄 수의 모든 숫자를 담기에는 관측 가능한 우주를 모두 동원해도 부족하다. 그레이엄 수를 디지털로 표현한다고 해도 자릿수가 너무 커서 관측 가능한 우주를 모두 사용해도 이를 디지털로 표현할 수 없다. 또한 그레이엄 수의 자릿수는 관측 가능한 우주를 동원해 플랑크 부피 단위로 사용하더라도 자릿수의 숫자도 커 표현할 수 없다. 따라서 그레이엄 수는 실제로 3의 거듭제곱 형식으로 표현할 수 있으나 이를 $a^{b^{c^{\cdot ^{\cdot ^{\cdot }}}}}$ 형식의 물리적 우주 규모의 테트레이션으로는 표현할 수 없다.

그레이엄 수는 이 수의 이름을 붙인 로널드 그레이엄이 사용한 것처럼 커누스 윗화살표 표기법 혹은 이와 유사한 표기법을 사용해 계산 가능한 재귀 공식 형태로 표현할 수 있다. 이를 정의하는 재귀 공식이 존재하므로 계산 가능한 어떠한 수열보다도 빠른 속도로 증가하는 보통의 바쁜 비버 수보다 그레이엄 수가 훨씬 작다. 그레이엄 수는 너무 커서 전부를 계산할 순 없지만, 간단한 알고리즘을 통해 그레이엄 수의 앞자리는 무엇인지 계산할 수 있으며 마지막 13자리는 ...7262464195387이다. 커누스 윗화살표 표기법을 사용하면 그레이엄 수는 $g_{64}$라고 표현할 수 있으며, 여기서 g 함수는 다음과 같이 정의할 수 있다.

$$g_{n}={\begin{cases}3\uparrow \uparrow \uparrow \uparrow 3,&{\text{if }}n=1{\text{ and}}\\3\uparrow ^{g_{n-1}}3,&{\text{if }}n\geq 2.\end{cases}}$$

그레이엄 수는 그레이엄이 통속과학 작가인 마틴 가드너과의 대화에서 자신이 연구하던 문제의 상한값을 단순화해 설명하면서 처음 정의되었다. 1977년 가드너는 《사이언티픽 아메리칸》지에 이 수를 설명하며 일반 대중에게 처음으로 소개했다. 소개 당시 그레이엄 수는 지금까지 발표된 수학적 증명에 사용된 수 중 가장 큰 양의 정수였다. 이 수는 1980년 《기네스 세계 기록》에 등재되며 대중의 관심을 끌어모았다. 그레이엄 수의 등장 이후 그레이엄 수보다 훨씬 더 큰 수로 알려진 TREE(3)와 같은 수가 하비 프리드먼의 크러스컬 나무 정리의 다양한 유한한 형태와 관련되어 사용되는 등 이후 많은 진지한 수학 증명에서 매우 큰 수로 등장했다. 또한 그레이엄 수가 도출된 램지 이론에서 더 작은 상한의 수도 맞다고 증명되었다.

문제

하나의 색만 가진 4개 꼭지점의 동일평면 완전하위그래프를 포함한 2색 3차원 정육면체의 예시이다. 하위 그래프는 정육면체 아래에 표시했다. 만약 현재 하위 그래프의 아래쪽 가장자리 선분을 파란색으로 바꾸면 이 정육면체에는 하나의 색만 가진 4개 꼭기점의 동일평면 완전하위그래프가 존재하지 않으므로 이런 반례를 통해 N* > 3임을 증명할 수 있다.

그레이엄 수는 램지 이론의 다음 문제와 연결된다.

N차원 초입방체의 각 꼭짓점을 서로서로 이어 2ⁿ개의 꼭짓점에 대한 완전 그래프를 구한다. 이 그래프의 각 모서리를 빨강 혹은 파랑 두 가지 색으로 칠한다. 모든 모서리를 색칠했을 때 어떻게 색칠하든 한 평면에 있는 4개의 꼭지점을 이은 완전 그래프가 모두 한 가지 색으로만 이루어져 있으러면 그 최소값 n이 얼마 이상이 되어야 하는가?

1971년 그레이엄과 로스차일드는 매개변수 단어의 램지 이론에 대한 그레이엄-로스차일드 정리를 증명했는데 이 정리는 위 문제의 특수한 경우에서 문제의 해가 N*임을 보여주었다. 그레이엄은 N* 값을 6 ≤ N* ≤ N 사이로 제한시켰는데 여기서 N값은 매우 큰 아래의 수이다.

$N=F^{7}(12)=F(F(F(F(F(F(F(12))))))),$

여기서 커누스 윗화살표 표기법 식으로는 $F(n)=2\uparrow ^{n}3$이며 콘웨이 연쇄 화살표 표기법으로는 4 → 2 → 8 → 2와 2 → 3 → 9 → 2 사이의 값이다. 이 상계는 2014년 헤일스-주에트 정리에서 나온 수의 상한값에 따라 다음과 같이 줄어들었다.

$N'=2\uparrow \uparrow 2\uparrow \uparrow (3+2\uparrow \uparrow 8),$

위 수에는 세 테트레이션이 존재한다. 2019년에는 N을 아래와 같이 좀 더 정확하게 정의했다.

$N''=(2\uparrow \uparrow 5138)\cdot ((2\uparrow \uparrow 5140)\uparrow \uparrow (2\cdot 2\uparrow \uparrow 5137))\ll 2\uparrow \uparrow (2\uparrow \uparrow 5138)$

6이라는 하한은 이후 2003년 제프리 엑소가 11로, 2008년 제롬 버클리가 13으로 올라감을 증명했다. 따라서 N*의 가장 확실한 유계는 13 ≤ N* ≤ N''이다.

그레이엄 수 G는 N보다 훨씬 큰데 $f(n)=3\uparrow ^{n}3$라고 정의된 함수에서 $f^{64}(4)$이다. 이 문제에 대한 약한 상한은 그레이엄의 미발표된 연구에서 나온 값으로 결국 1977년 11월에 마틴 가드너가 《사이언티픽 아메리칸》지에 이를 발표하고 이름을 붙였다.

유도 방법

그레이엄 수의 기본은 3이다. 3을 밑으로 하여 3의 연산을 무수히 반복하는 과정이 되풀이된다. 물론 실제로 무수히 반복하지는 않고 유한하지만, 그 수의 크기가 극도로 크다는 말로는 모자라기 때문에 이 수를 감당해내는 것조차도 불가능하다. 이 연산을 나타내기 위해서 커누스 윗화살표 표기법의 이해가 필요하다. 커누스 윗화살표 표기법은 하이퍼연산자라고도 하며, 덧셈-곱셈-거듭제곱-테트레이션-펜테이션-....등으로 그 직전 연산의 반복으로 상위 연산을 정의하는 기호이다. 이 커누스 윗화살표 표기법을 재귀하면 G(n)에 도달한다.

커누스 윗화살표 표기법을 이용하여 f(n)를 다음과 같이 정의하자.

$f(1)=3\uparrow 3=3^{3}=27$

$f(2)=3\uparrow \uparrow 3=3\uparrow (3\uparrow 3)=3\uparrow f(1)=3^{3^{3}}=3^{27}=7,625,597,484,987$

$f(3)=3\uparrow \uparrow \uparrow 3=3\uparrow \uparrow (3\uparrow \uparrow 3)=3\uparrow \uparrow f(2)=3\uparrow (3\uparrow (3\uparrow ...\uparrow 3))$   (f(2)번 반복) $=3^{3^{3^{.^{.^{.^{.^{3}}}}}}}$ (7,625,597,484,987번 반복)

$f(4)=3\uparrow \uparrow \uparrow \uparrow 3=3\uparrow \uparrow \uparrow (3\uparrow \uparrow \uparrow 3)=3\uparrow \uparrow \uparrow G(3)=3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow ...(3\uparrow \uparrow (3\uparrow \uparrow 3))...))$   (G(3)번 반복)
          $=\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{\cdot ^{3}}}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{\cdot ^{3}}}}}\end{matrix}}\right\}\dots \left.{\begin{matrix}3^{3^{\cdot ^{\cdot ^{3}}}}\end{matrix}}\right\}\left.{\begin{matrix}3^{3^{3}}\end{matrix}}\right\}3$   (f(3)번 반복)

이렇게 급격히 증가하며, f(3)부터 이미 계산하거나 표기하기가 곤란해진다. 여기서 $g_{1}=f(4)=3\uparrow \uparrow \uparrow \uparrow 3$라 정의된다. 그러면

$g_{2}=f^{2}(4)=f(f(4))=3\uparrow ...\uparrow 3$ (화살표가 f(4)개, 여기서 지수는 합성 횟수를 뜻한다.)

$g_{3}=f^{3}(4)=f(f^{2}(4))=3\uparrow ...\uparrow 3$ (화살표가 f²(4)개)

$g_{4}=f^{4}(4)=f(f^{3}(4))=3\uparrow ...\uparrow 3$ (화살표가 f³(4)개)

...

$g_{63}=f^{63}(4)=f(f^{62}(4))=3\uparrow ...\uparrow 3$ (화살표가 f⁶²(4)개)

$g_{64}=f^{64}(4)=f(f^{63}(4))=3\uparrow ...\uparrow 3$ (화살표가 f⁶³(4)개)

이와 같이 증가하여 $G=g_{64}=f^{64}(4)$로 정의되는 G가 그레이엄 수이다.

결과

그레이엄 수는 너무 크기 때문에 10진수로 표기하는 것이 불가능하지만, 마지막 500자리의 수는 다음과 같이 알려져 있다.

 …02425950695064738395657479136519351798334535362521
  43003540126026771622672160419810652263169355188780
  38814483140652526168785095552646051071172000997092
  91249544378887496062882911725063001303622934916080
  25459461494578871427832350829242102091825896753560
  43086993801689249889268099510169055919951195027887
  17830837018340236474548882222161573228010132974509
  27344594504343300901096928025352751833289884461508
  94042482650181938515625357963996189939679054966380
  03222348723967018485186439059104575627262464195387

같이 보기

• 큰 수
• 커누스 윗화살표 표기법
• 하이퍼 연산
• 아커만 함수
• 램지의 정리

참고 문헌

• Gardner, Martin (November 1977). “Mathematical Games” (PDF). 《Scientific American》 237 (5): 18–28. Bibcode:1977SciAm.237e..18G. doi:10.1038/scientificamerican1177-18. ; reprinted (revised) in Gardner (2001), cited below.
• Gardner, Martin (1989). 《Penrose Tiles to Trapdoor Ciphers》. Washington, D.C.: Mathematical Association of America. ISBN 978-0-88385-521-8. 
• Gardner, Martin (2001). 《The Colossal Book of Mathematics: Classic Puzzles, Paradoxes, and Problems》. New York, NY: Norton. ISBN 978-0-393-02023-6. 
• Graham, R. L.; Rothschild, B. L. (1971). “Ramsey's Theorem for n-Parameter Sets” (PDF). 《Transactions of the American Mathematical Society》 159: 257–292. doi:10.2307/1996010. JSTOR 1996010.  The explicit formula for N appears on p. 290. This is not the "Graham's number" G published by Martin Gardner.
• Graham, R. L.; Rothschild, B. L. (1978). 〈Ramsey Theory〉. Rota, G-C. 《Studies in Combinatorics (MAA Studies in Mathematics)》 17. Mathematical Association of America. 80–99쪽. ISBN 978-0-88385-117-3.  On p. 90, in stating "the best available estimate" for the solution, the explicit formula for N is repeated from the 1971 paper.

외부 링크

• "A Ramsey Problem on Hypercubes" by Geoff Exoo
• Mathworld article on Graham's number
• How to calculate Graham's number
• Some Ramsey results for the n-cube prepublication mentions Graham's number
• Padilla, Tony; Parker, Matt. “Graham's Number”. 《Numberphile》. Brady Haran. 2014년 5월 27일에 원본 문서에서 보존된 문서. 2014년 5월 26일에 확인함.