그레이엄 수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 문제
- 2.1. 그레이엄-로스차일드 정리
- 2.2. 해의 범위
3. 정의
4. 유도 방법
5. 결과
6. 소(小) 그레이엄 수
7. 라브로프 등에 의한 해의 상한
참조

1. 개요

그레이엄 수는 램지 이론과 관련된 문제의 해로, 4개의 꼭짓점을 가진 한 가지 색의 평면 완전 그래프를 포함하는 2색 초입방체의 최소 차원이다. 이 수는 커누스 윗화살표 표기법을 사용하여 정의되며, 3을 밑으로 하여 윗화살표 표기법을 반복 적용하여 얻어진다. 그레이엄 수는 10진수로 표기하는 것이 불가능할 정도로 큰 수이며, 현재 가장 정확한 해의 범위는 13 이상, 라브로프 등이 제시한 수 이하이다. 작은 그레이엄 수는 그레이엄 수보다 훨씬 작지만, 여전히 매우 큰 수이며, 2014년 라브로프 등은 다차원 틱택토에 관한 헤일스-주엣 정리를 응용하여 그레이엄 수의 상한을 제시했다.

더 읽어볼만한 페이지

램지 이론 - 램지의 정리
램지의 정리는 주어진 조건을 만족하는 램지 수가 존재한다는 정리로, 그래프 이론으로 해석되며, 특정 크기의 동색 클릭이 존재함을 보장하고, 램지 이론의 시초로 여겨진다.
램지 이론 - 비둘기집 원리
비둘기집 원리는 n개의 비둘기집에 n+1마리 이상의 비둘기를 넣으면 적어도 하나의 비둘기집에는 두 마리 이상의 비둘기가 들어간다는 간단한 원리이며, 귀류법으로 증명되고, 소프트볼 팀 구성, 해시 테이블 충돌 등 다양한 분야에 응용된다.
큰 수 - 나유타
나유타는 불교 경전에서 큰 수를 비유하는 산스크리트어 유래 수의 단위로, 산학계몽에 처음 등장하여 시대에 따라 크기 정의가 변화했으며 현대에는 특정 수치를 나타내는 단위로도 쓰인다.
큰 수 - 구골플렉스
구골플렉스는 1 뒤에 구골(10¹⁰⁰)개의 0이 붙는 매우 큰 수로, 1940년 밀튼 시로타가 명명했으며, 칼 세이건은 십진법으로 완전히 쓰는 것이 물리적으로 불가능하다고 추정했다.
정수 - 1987
1987은 수학적으로 소수이자 순환소수, 약수 총합과 관련된 특징을 가지며, 천문학, 문화유산, 영화, 음악 등 다양한 분야에서 활용되는 숫자이다.
정수 - 383
383은 76번째 소수이자 안전 소수, 회문 소수, 왼쪽 잘라내기 가능 소수이며, 오일러의 소수 생성 공식에서 유도되는 소수이고, 역수가 순환마디 길이 382인 순환소수인 수학적으로 특징적인 수이다.

그레이엄 수
개요
종류	매우 큰 수
고안자	로널드 그레이엄
발표 년도	1977년
첫 등장	마틴 가드너의 "수학 게임" 칼럼 (Scientific American, 1977년 11월)
크기	구골플렉스보다 훨씬 큼
특징	실제로 사용되는 맥락이 거의 없음 램지 이론과 관련
정의
함수 g1	g1(n) = 3↑↑n (크누스 윗화살표 표기법)
함수 gk	gk(n) = g(k-1)^n(n)
그레이엄 수 (G)	G = g64(4)
설명	그레이엄 수는 특정한 이분 그래프의 모든 꼭짓점을 연결했을 때, 어떤 부분 그래프가 항상 완전한 사면체 그래프를 가지도록 하는 최소 꼭짓점의 개수를 구하는 램지 이론 문제와 관련되어 정의됨. 그레이엄 수를 십진법으로 표현하는 것은 사실상 불가능하며, 마지막 자릿수조차도 현재 기술로는 계산하기 매우 어려움.
크기 비교
구골플렉스	그레이엄 수는 구골플렉스보다 상상할 수 없을 정도로 큼.
기타 큰 수	그레이엄 수는 스큐즈 수, 모저 수 등 다른 큰 수들과 비교해도 압도적으로 큼.
기타
중요성	큰 수에 대한 이해를 넓히고, 수학적 사고의 한계를 시험하는 데 기여.

2. 문제

그레이엄 수는 램지 이론의 문제와 관련이 있다. 이 문제는 n차원 초입방체의 꼭짓점을 연결하고, 각 선분을 빨간색 또는 파란색으로 칠하는 문제를 다룬다. 이렇게 색칠했을 때, 어떤 방식으로 색칠하더라도 동일 평면 상에 있는 네 꼭짓점을 잇는 완전 그래프가 항상 단색으로 나타나도록 하는 최소 차원 n을 찾는 것이 이 문제의 핵심이다. 즉, 특정 차원 이상에서는 반드시 단색의 완전 부분 그래프가 존재하게 된다.

단색의 4개 꼭짓점 완전 부분 그래프를 포함하는 2색 3차원 큐브의 예시. 큐브 아래에 부분 그래프가 표시되어 있다. 예를 들어, 현재 부분 그래프의 하단 모서리가 파란색 모서리로 대체되면 이러한 부분 그래프를 포함하지 않으므로 반례로 ''N''* > 3임을 증명한다.

구체적인 문제의 내용은 다음과 같다.

2. 1. 그레이엄-로스차일드 정리

1971년, 로널드 그레이엄과 브루스 로스차일드는 매개변수 단어에 대한 그레이엄-로스차일드 정리를 증명하여, 특정 문제의 해가 존재함을 보였다.^[2] 이들은 해의 상한과 하한을 제시했는데, 상한은 매우 큰 수(그레이엄 수)였고, 하한은 6이었다.^[10]

문제는 다음과 같다.

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

그레이엄과 로스차일드는 이 문제의 해 ''N*''의 값을 로 제한했다. 여기서 ''N''은 다음과 같이 정의된 매우 큰 수이다.

:

N=F^7(12) = F(F(F(F(F(F(F(12))))))),

여기서

F(n) = 2\uparrow^n 3

는 커누스 윗화살표 표기법이며, 콘웨이 연쇄 화살표 표기법에서 이 수는 와 사이이다.^[2]

이 상계는 2014년 헤일스-주에트 정리에서 나온 수의 상한값에 따라 다음과 같이 줄어들었다.^[3]

:

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

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

:

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로,^[5] 2008년 제롬 버클리가 13으로 올라감을 증명했다.^[6] 따라서 ''N*''의 가장 확실한 유계는 이다.

2. 2. 해의 범위

1971년 그레이엄과 로스차일드는 그레이엄-로스차일드 정리를 통해 이 문제의 해 *N*^*가 존재함을 증명하고, 해의 범위를 6 ≤ *N*^* ≤ *N* 으로 제한했다. 여기서 *N*은 매우 큰 수였다.^[20]

이후 하한은 2003년 제프리 엑소가 11로,^[23] 2008년 제롬 버클리가 13으로 상향 조정했다.^[24]

상한 역시 초기 그레이엄 수보다 더 작은 수로 줄어들었다. 2014년 미하일 라브로프 등은 헤일스-주엣 정리를 응용하여 더 작은 상한 *N'* 을 제시했다.^[12]

:

N' = 2 \uparrow\uparrow\uparrow 6 = 2 \rightarrow 6 \rightarrow 3 =\operatorname{hyper}(2, 5, 6)

현재까지 알려진 가장 정확한 해의 범위는 13 ≤ *N*^* ≤ *N'* 이다.

3. 정의

그레이엄 수는 램지 이론의 문제와 관련되어 정의된다. 이 문제는 N차원 초입방체의 각 꼭짓점을 서로 이어 완전 그래프를 만들고, 각 모서리를 빨강 또는 파랑으로 칠할 때, 한 평면에 있는 4개의 꼭짓점을 이은 완전 그래프가 모두 한 가지 색으로만 칠해지는 최소의 n 값을 찾는 것이다.^[20]

1971년 그레이엄과 로스차일드는 이 문제의 해가 ''N*''임을 보였고, N*의 값을 사이로 제한했다. 여기서 ''N''은 매우 큰 수로, 커누스 윗화살표 표기법으로는 $F(n) = 2\uparrow^n 3$ 이며, 콘웨이 연쇄 화살표 표기법으로는 와 사이의 값이다.^[20]

이후 상계는 2014년 $N' = 2 \uparrow\uparrow 2 \uparrow\uparrow (3 + 2 \uparrow\uparrow 8)$ (세 테트레이션 존재)로,^[21] 2019년에는 $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)$ 로 줄어들었다.^[22] 하한은 2003년 11,^[23] 2008년 13으로 올라갔다.^[24] 따라서 ''N*''의 가장 확실한 유계는 이다.

그레이엄 수 ''G''는 ''N''보다 훨씬 큰 수로, $f(n) = 3 \uparrow^n 3$ 로 정의된 함수에서 $f^{64}(4)$ 이다.

3. 1. 커누스 윗화살표 표기법

커누스 윗화살표 표기법은 거듭제곱을 반복하는 연산을 간결하게 나타내는 방법이다. 화살표 하나는 거듭제곱, 화살표 두 개는 거듭제곱의 반복(테트레이션)을 나타내는 식이며, 화살표 개수가 늘어날수록 연산의 수준이 높아진다.^[1] 이 표기법을 사용하여 함수 f(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 3\uparrow \uparrow \uparrow 3 = 3\uparrow \uparrow (3\uparrow \uparrow (3\uparrow \uparrow ... (3\uparrow \uparrow (3\uparrow \uparrow 3))...))$ (3↑↑↑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)개)

이와 같이 증가하여, f(3)부터 이미 계산하거나 표기하기가 곤란해진다.^[1]

G = g_{64} = f^{64}(4)

로 정의되는 '''G'''가 그레이엄 수이다.^[1]

크누스 윗 화살표 표기법을 사용하여, 그레이엄 수 ''G'' (가드너의 ''Scientific American'' 기사에서 정의됨)는 다음과 같다.^[1]

:

\left.\begin{matrix}G &=&3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \cdots \uparrow}3 \\& &3\underbrace{\uparrow \uparrow \cdots \cdots \cdots \cdots \uparrow}3 \\& & \underbrace{\qquad \quad \vdots \qquad \quad} \\& &3\underbrace{\uparrow \uparrow \cdots \cdots \uparrow}3 \\& &3\uparrow \uparrow \uparrow \uparrow3\end{matrix}\right \} \text{64 layers}

여기서 각 레이어의 ''화살표'' 수는 바로 아래 레이어의 값에 의해 지정된다. 즉,^[1]

:

G = g_{64},

where

g_1=3\uparrow\uparrow\uparrow\uparrow 3,

g_n = 3\uparrow^{g_{n-1}}3,

윗 화살표의 위첨자는 화살표의 수를 나타낸다. 즉, ''G''는 64단계로 계산된다. 첫 번째 단계는 3 사이에 4개의 윗 화살표를 사용하여 ''g''₁을 계산하는 것이다. 두 번째 단계는 3 사이에 ''g''₁개의 윗 화살표를 사용하여 ''g''₂를 계산하는 것이다. 세 번째 단계는 3 사이에 ''g''₂개의 윗 화살표를 사용하여 ''g''₃을 계산하는 것이다. 마지막으로 3 사이에 ''g''₆₃개의 윗 화살표를 사용하여 ''G'' = ''g''₆₄를 계산할 때까지 이 과정을 반복한다.^[1]

동등하게,^[1]

:

G = f^{64}(4),\text{ where }f(n) = 3 \uparrow^n 3,

''f''의 위첨자는 함수의 반복을 나타낸다. 예를 들어,

f^4(n) = f(f(f(f(n))))

이다. 초연산 의 함수로 표현하면, 함수 ''f''는 빠른 속도로 증가하는 아커만 함수 ''A''(''n'', ''n'')의 한 형태인

f(n) = \text{H}_{n+2}(3,3)

이다. (사실, 모든 ''n''에 대해

f(n) > A(n, n)

이다.) 함수 ''f''는 또한 콘웨이 연쇄 화살표 표기법으로

f(n) = 3 \rightarrow 3 \rightarrow n

로 표현할 수 있으며, 이 표기법은 또한 ''G''에 대한 다음 경계를 제공한다.^[1]

:

3\rightarrow 3\rightarrow 64\rightarrow 2 < G < 3\rightarrow 3\rightarrow 65\rightarrow 2.

크누스 윗화살표 표기법에서, ''x'', ''y''를 자연수라고 할 때, 연산자 "↑"는 다음과 같이 정의한다.^[1]

:

x \uparrow y = x ^ y

"↑↑"는 다음과 같이 재귀적으로 정의한다.^[1]

:

x \uparrow\uparrow 1 = x

:

x \uparrow\uparrow y = x \uparrow \left\{x \uparrow\uparrow \left(y - 1\right)\right\}

즉,

:

x\uparrow\uparrow y =\ \underbrace{x\uparrow x\uparrow \cdots \uparrow x}_y = \underbrace{x^{x^{\cdot^{\cdot^{\cdot^x}}}}}_{y}

(

\underbrace{}_y

는, ''x''가 ''y''개 있음을 나타낸다). 단, 연산은 오른쪽부터 수행한다. ''x''↑''x''↑''x'' = ''x''↑(''x''↑''x'')이다. 예를 들면 다음과 같다.^[1]

:

\begin{align}3\uparrow\uparrow2=&3^3=27 \\3\uparrow\uparrow3=&3^{3^3}=3^{27}=7625597484987 \\3\uparrow\uparrow4=&3^{3^{3^3}}=3^{7625597484987}\\\approx &1.258\times 10^{3638334640024} \\3 \uparrow\uparrow 5=&3^{3^{3^{3^3}}}=3^{3^{7625597484987}}\\\approx &3^{1.258\times 10^{3638334640024}}\\\approx &10^{6.0022\times 10^{3638334640023}}\end{align}

마찬가지로 "↑↑↑"를 다음과 같이 재귀적으로 정의한다.^[1]

:

x \uparrow\uparrow\uparrow 1 = x

:

x \uparrow\uparrow\uparrow y = x \uparrow\uparrow \left\{x \uparrow\uparrow\uparrow (y - 1)\right\}

즉,

:

x\uparrow\uparrow\uparrow y = \underbrace{x\uparrow\uparrow x\uparrow\uparrow \cdots \uparrow\uparrow x}_{y\text{ copies of }x}

이다.

일반적인 경우, "↑…(''n''개)…↑"＝"↑^''n''"를 다음과 같이 정의한다.^[1]

:

x \uparrow^n 1 = x

:

x \uparrow^n y = x \uparrow^{n-1} \left\{x \uparrow^n \left(y - 1 \right)\right\}

3. 2. 함수 G(n)과 그레이엄 수

커누스 윗화살표 표기법을 사용하여 함수 ''G''(''n'')을 다음과 같이 정의한다.

:

G(n) = 3 \uparrow^n 3 = 3 \mathbin{\underbrace{\uparrow\cdots\uparrow}_{n\ \textrm{arrows}}} 3

여기서

\uparrow^n

은 n개의 화살표를 의미한다.

예를 들어,

$G(1) = 3\uparrow 3 = 3^3 = 27$
$G(2) = 3\uparrow \uparrow 3 = 3\uparrow (3\uparrow 3) = 3^{27} = 7,625,597,484,987$
$G(3) = 3\uparrow \uparrow \uparrow 3$ 은 3을 밑으로 7,625,597,484,987번 거듭제곱한 수이다.
$G(4) = 3\uparrow \uparrow \uparrow \uparrow 3$ 은 3을 밑으로 G(3)번 거듭제곱한 수이다.

이와 같이 G(n)은 급격하게 증가하며, G(3)부터 이미 계산하거나 표기하기가 곤란해진다.

'''그레이엄 수'''는 함수 G(n)을 64번 반복 적용하여 얻어지는 수, 즉

G^{64}(4)

로 정의된다.

:

G = G^{64} (4) = \underbrace{G(G(\cdots G}_{64} (4) \cdots ))

이는 다음과 같이 표현할 수도 있다.

:

\left.\begin{matrix}3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots\cdots\cdots\cdots \cdots \cdots\cdots\cdots \uparrow \uparrow \uparrow}3 \\\qquad\quad3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots\cdots\cdots\cdots \uparrow \uparrow \uparrow}3\text{ arrows} \\\vdots \\\qquad\quad3\underbrace{\uparrow \uparrow \uparrow \uparrow \uparrow \uparrow \cdots\cdots \uparrow \uparrow \uparrow}3\text{ arrows} \\3 \uparrow\uparrow\uparrow\uparrow 3 \text{ arrows}\end{matrix}\right \} 64 \text{ layers}

여기서 각 층(layer)의 화살표 수는 바로 아래 층의 값에 의해 결정된다. 즉, 64개의 층이 있으며, 각 층은 3과 3 사이에 엄청나게 많은 화살표가 있는 형태로 구성된다.

3. 3. 콘웨이 연쇄 화살표 표기법

Conway^영어 연쇄 화살표 표기법은 커누스 윗화살표 표기법보다 더 큰 수를 간결하게 나타내는 강력한 표기법이다.

''F''(12) = 2↑¹²3 = 2→3→12
''F''²(12) = ''F''(''F''(12)) = 2↑…(''F''(12) 개)…↑3 = 2→3→''F''(12)
''F''³(12) = 2↑…(''F''²(12) 개)…↑3 = 2→3→''F''²(12)
''F''⁷(12) = 2↑…(''F''⁶(12) 개)…↑3 = 2→3→''F''⁶(12)

''F''(3)까지는 공학용 계산기나 컴퓨터로도 계산할 수 있지만, ''F''(4)는 십진법 표기가 현실적으로 불가능하다. ''F''²(12)는 2와 3 사이에 ''F''(12)개의 화살표를 놓은 것으로, 모저 수를 초과한다.

체인 표기법을 사용해도 ''F'' = ''F''⁷(12)를 간결하게 나타낼 수 없지만, 다음 부등식이 성립한다.

:

3\rightarrow 2\rightarrow 8\rightarrow 2 < F < 3\rightarrow 2\rightarrow 9\rightarrow 2

4. 유도 방법

그레이엄 수는 커누스 윗화살표 표기법을 사용하여 유도된다. 우선, 함수 f(n)을 다음과 같이 정의한다.

f(1) = 3↑3 = 3³ = 27
f(2) = 3↑↑3 = 3↑(3↑3) = 3²⁷ = 7,625,597,484,987
f(3) = 3↑↑↑3 = 3↑↑(3↑↑3) = 3↑↑7,625,597,484,987 = 3↑(3↑(3↑...(3↑3)...)) (7,625,597,484,987번 반복)
f(4) = 3↑↑↑↑3 = 3↑↑↑(3↑↑↑3)

여기서 ↑는 커누스 윗화살표 표기법을 나타낸다. f(3)부터는 이미 계산하거나 표기하기 매우 어려워진다.

이제, g₁ = f(4) = 3↑↑↑↑3 으로 정의한다. 그 후, 다음과 같이 함수 f를 반복 적용한다.

g₂ = f(g₁) = f(f(4)) = 3↑...↑3 (화살표가 f(4)개)
g₃ = f(g₂) = f(f(f(4))) = 3↑...↑3 (화살표가 f²(4)개)
...
g₆₄ = f(g₆₃) = f⁶⁴(4) = 3↑...↑3 (화살표가 f⁶³(4)개)

이와 같이 64번 반복하여 얻어진 g₆₄가 바로 그레이엄 수이다. 즉, 그레이엄 수는 G = g₆₄ = f⁶⁴(4)로 정의된다.

함수 f는 f(n) = 3 ↑ⁿ 3으로 표현할 수 있으며, 이는 콘웨이 연쇄 화살표 표기법으로 f(n) = 3 → 3 → n 과 같이 나타낼 수 있다.

5. 결과

10진수로 표기하는 것은 불가능하지만, 마지막 500자리의 수는 다음과 같이 알려져 있다.

…02425950695064738395657479136519351798334535362521

43003540126026771622672160419810652263169355188780

38814483140652526168785095552646051071172000997092

91249544378887496062882911725063001303622934916080

25459461494578871427832350829242102091825896753560

43086993801689249889268099510169055919951195027887

17830837018340236474548882222161573228010132974509

27344594504343300901096928025352751833289884461508

94042482650181938515625357963996189939679054966380

03222348723967018485186439059104575627262464195387^[15]

그래엄 수 자체는 슈퍼컴퓨터로도 ''G''(3)의 계산조차 기대할 수 없을 정도로 크지만, 꼬리 숫자를 계산하는 방법은 확립되어 있으며, 어느 정도의 자릿수는 판명되어 있다.

십진법으로 나타냈을 때의 꼬리 10자리는 2,464,195,387이며, 암흑통신단이 꼬리 100만 자리를 기록한 서적도 출판했으며^[17], 그 후, 암흑통신단의 웹사이트에서 꼬리 1,600만 자리를 기록한 PDF 형식의 파일도 공개하고 있다^[18].

6. 소(小) 그레이엄 수

소(小) 그레이엄 수(Little Graham)는 그레이엄과 로스차일드가 1971년에 제시한 그레이엄 문제 해의 또 다른 상한이다. 이 수는 그레이엄 수보다는 작지만, 여전히 매우 큰 수이다. 함수 $F(n) = 2\uparrow^n 3$ 를 정의하고, $F^7(12)$ 를 계산하여 얻어진다.^[20]

7. 라브로프 등에 의한 해의 상한

2014년, 미하일 라브로프 등은 다차원 틱택토에 관한 헤일스-주엣 정리를 응용하여 그레이엄 문제의 해에 대한 더 작은 상한을 제시했다.^[21] 이 상한은 다음과 같이 표현된다.

: $N' = 2 \uparrow\uparrow\uparrow 6 = 2 \rightarrow 6 \rightarrow 3 =\operatorname{hyper}(2, 5, 6)$

이 수는 십진 표기가 사실상 불가능할 정도로 매우 크지만, 그레이엄 수나 소 그레이엄 수와 비교하면 훨씬 작다. 그레이엄 문제의 해 ''n''은 다음 범위에 있게 된다.

: $\begin{align} 13 \le n \le 2 \uparrow\uparrow\uparrow 6 =& 2 \rightarrow 6 \rightarrow 3 =\operatorname{hyper}(2, 5, 6) \\=& 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2 = 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow4 = 2\uparrow\uparrow2\uparrow\uparrow2\uparrow\uparrow65536 \\=& {}^{2} = {}^{2} = {}^}}{2}}{2}}{2} = {}^{2}}{2}\end{align}$

참조

_[1] 웹사이트 Graham's Number https://mathworld.wo[...]
_[2] 웹사이트 Graham's number records https://web.archive.[...] Iteror.org 2014-04-09
_[3] 논문 Improved upper and lower bounds on a geometric Ramsey problem 2014
_[4] 간행물 Further improving of upper bound on a geometric Ramsey problem
_[5] 논문 A Euclidean Ramsey Problem 2003
_[6] 간행물 Improved lower bound on an Euclidean Ramsey problem
_[7] 논문 In which joining sets of points leads into diverse (and diverting) paths https://web.archive.[...] 1977
_[8] 웹사이트 A while back I told you about Graham's number... https://web.archive.[...] 2013-01-11
_[9] 서적 Guiness Book of World Record 1980
_[10] 웹사이트 Ramsey's theorem for n-parameter sets http://www.ams.org/j[...]
_[11] 웹사이트 Mathematical Games http://www.nature.co[...]
_[12] 논문 Improved upper and lower bounds on a geometric Ramsey problem 2014
_[13] 웹사이트 A Ramsey Problem on Hypercubes http://isu.indstate.[...]
_[14] 간행물 Improved lower bound on an Euclidean Ramsey problem
_[15] 문서 ''G''(4)には[[グラハル]]という名前がついている。
_[16] 문서 桁数が非常に大きいため、時間の単位を[[プランク時間]]・[[秒]]・[[年]]のいずれにしても無視できる範囲で近似する。
_[17] 서적 グラハム数百万桁表最終巻暗黒通信団
_[18] 웹사이트 グラハム数の末尾1600万桁表（オンライン版）【PDF】 http://ankokudan.org[...]
_[19] 웹인용 Graham's Number https://mathworld.wo[...]
_[20] 웹인용 Graham's number records https://web.archive.[...] Iteror.org 2014-04-09
_[21] 논문 Improved upper and lower bounds on a geometric Ramsey problem 2014
_[22] 간행물 Further improving of upper bound on a geometric Ramsey problem
_[23] 논문 A Euclidean Ramsey Problem 2003
_[24] 간행물 Improved lower bound on an Euclidean Ramsey problem
_[25] 논문 In which joining sets of points leads into diverse (and diverting) paths https://web.archive.[...] 1977

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com