골롬-딕맨 상수

1. 개요

골롬-딕맨 상수는 크기가 무한대로 커질 때 순열에서 가장 긴 사이클의 길이와 관련된 수학 상수이다. 이 상수는 확률론, 수론, 그리고 유한 집합에서 자신으로 가는 임의의 함수에서 가장 긴 사이클의 평균 길이를 고려하는 문제 등 다양한 분야에서 나타난다. 골롬-딕맨 상수는 여러 적분 표현식으로 나타낼 수 있으며, 로그 적분, 지수 적분, 딕만 함수 등을 사용하여 정의된다. 또한, 커누스의 추측과 관련이 있으며, 관련 상수 및 함수를 통해 표현될 수 있다.

2. 정의

a_n을 크기가 n인 집합의 모든 순열에 대해 구한 평균값으로, 각 순열에서 가장 긴 사이클의 길이라고 하자. 그러면 골롬-딕맨 상수는 다음과 같다.

:$\backslash lambda\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; \backslash frac\{a\_n\}\{n\}.$

확률론의 용어로 표현하면, $\backslash lambda\; n$은 크기가 n인 집합의 균등하게 분포된 무작위 순열에서 가장 긴 사이클의 기댓값 길이와 점근적으로 같다.

수론에서 골롬-딕맨 상수는 정수의 가장 큰 소인수의 평균 크기와 관련하여 나타난다. 보다 정확하게는,

:$\backslash lambda\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; \backslash frac1n\; \backslash sum\_\{k=2\}^n\; \backslash frac\{\backslash log(P\_1(k))\}\{\backslash log(k)\},$

여기서 $P\_1(k)$는 k의 가장 큰 소인수이다. 따라서 k가 d 자리 정수이면, $\backslash lambda\; d$는 k의 가장 큰 소인수의 자리 수의 점근적 평균값이다.

골롬-딕맨 상수는 수론에서 다른 방식으로 나타난다. n의 두 번째로 큰 소인수가 n의 가장 큰 소인수의 제곱근보다 작을 확률은 얼마인가? 점근적으로 이 확률은 $\backslash lambda$이다. 보다 정확하게는,

:$\backslash lambda\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; \backslash text\{Prob\}\backslash left\backslash \{P\_2(n)\; \backslash le\; \backslash sqrt\{P\_1(n)\}\backslash right\backslash \}$

여기서 $P\_2(n)$는 n의 두 번째로 큰 소인수이다.

골롬-딕맨 상수는 유한 집합에서 자신으로의 임의의 함수에서 가장 긴 사이클의 평균 길이를 고려할 때도 나타난다. X가 유한 집합이고, 이 집합의 임의의 원소 x에 함수 f: X → X를 반복적으로 적용하면, 결국 사이클에 들어가게 된다. 이는 어떤 k에 대해 충분히 큰 n에 대해 $f^\{n+k\}(x)\; =\; f^n(x)$가 성립한다는 것을 의미하며, 이 속성을 갖는 가장 작은 k가 사이클의 길이이다. b_n을 크기가 n인 집합에서 자신으로 가는 모든 함수에 대해 구한 평균값으로, 가장 긴 사이클의 길이라고 하자. 그러면 Purdom과 Williams는 다음을 증명했다.

:$\backslash lim\_\{n\backslash to\backslash infty\}\; \backslash frac\{b\_n\}\{\backslash sqrt\{n\}\}\; =\; \backslash sqrt\{\backslash frac\{\backslash pi\}\{2\}\; \}\; \backslash lambda.$

3. 공식

골롬-딕맨 상수($\backslash lambda$)는 로그 적분, 지수 적분, 딕만 함수를 사용하여 표현할 수 있다.

3.1. 로그 적분

로그 적분을 사용하면 다음과 같이 표현할 수 있다.

$\backslash lambda\; =\; \backslash int\_0^1\; e^\{\backslash mathrm\{li\}(t)\}\; \backslash ,\; dt$

3.2. 지수 적분

$\backslash lambda$에 대한 몇 가지 표현은 다음과 같다.

:$\backslash lambda\; =\; \backslash int\_0^1\; e^\{\backslash mathrm\{li\}(t)\}\; \backslash ,\; dt$

여기서 $\backslash mathrm\{li\}(t)$는 로그 적분이다.

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; e^\{-t\; -\; E\_1(t)\}\; \backslash ,\; dt$

여기서 $E\_1(t)$는 지수 적분이다.

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash rho(t)\}\{t+2\}\; \backslash ,\; dt$

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash rho(t)\}\{(t+1)^2\}\; \backslash ,\; dt$

여기서 $\backslash rho(t)$는 딕만 함수이다.

3.3. 딕맨 함수

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash rho(t)\}\{t+2\}\; dt$

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash rho(t)\}\{(t+1)^2\}\; dt$

여기서 $\backslash rho(t)$는 딕맨 함수(Dickman–de Bruijn function)이다.

4. 커누스의 <math>\beta</math> 와 <math>B</math>에 대한 추측

커누스(Knuth, 1981)는 임의의 상수 $\backslash beta$ 와 $B$에 대해 다음과 같은 추측을 제시했다.

:$\backslash lim\_\{n\; \backslash to\; \backslash infty\}\; n^\backslash beta\; \backslash left(\; \backslash left\backslash langle\; M(x)\; \backslash right\backslash rangle\; -\backslash gamma\; n\; -\{1\backslash over2\}\; \backslash gamma\; \backslash right)\; =\; B$

여기서 $\backslash gamma$는 오일러-마스케로니 상수이다.

이후 고든(Gourdon, 1986)은 이 추측을 다음과 같이 증명하였다.

:$j\; =\; e^$에서,

:$\backslash left\backslash langle\; M(\backslash alpha)\; \backslash right\backslash rangle\; =\; \backslash lambda\; \backslash left(n+\{1\; \backslash over\; 2\}\backslash right)\; -\; \backslash over\{24n\}\}+e^\{\backslash gamma\}\; -\{1\; \backslash over\; 8\}(-1)^n\; \backslash over\{n^2\}\}+$

:$E(M(\backslash alpha))=\; \backslash lambda\; n\; +\{\backslash lambda\; \backslash over\; 2\}-\{e^\{\backslash gamma\}\backslash over24\}\{1\backslash over\; n\}+\backslash left(\; \backslash over\; 48\}-\{\{(-1)^n\}\; \backslash over\; 8\}\; \backslash right)\{1\; \backslash over\; n^2\}\; +\; \backslash left(\; \backslash over\; 3840\}+\{(-1)^n\; \backslash over\; 8\}+\{\{e^\{2(2n+1)\backslash pi\; i\}\backslash over\; 3\}\; \backslash over6\}+\; \{\{e^\{2(n+2)\backslash pi\; i\}\backslash over\; 3\}\; \backslash over6\}\; \backslash right)\; \{1\backslash over\; n^3\}+\; O\backslash left(\{1\backslash over\; n^4\}\; \backslash right)$

:$M(\backslash alpha)\; =\; \backslash underset\{j\}\{max\}\; \backslash \{\; j:\backslash alpha\_\{j\}\; >\; 0\; \backslash \}$

5. 관련 상수 및 함수

골롬-딕맨 상수($\backslash lambda$)와 관련된 여러 표현식은 다음과 같다.

:$\backslash lambda\; =\; \backslash int\_0^1\; e^\{\backslash mathrm\{li\}(t)\}\; \backslash ,\; dt$

여기서 $\backslash mathrm\{li\}(t)$는 로그 적분이다.

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; e^\{-t\; -\; E\_1(t)\}\; \backslash ,\; dt$

여기서 $E\_1(t)$는 지수 적분이다.

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash rho(t)\}\{t+2\}\; dt$

:$\backslash lambda\; =\; \backslash int\_0^\backslash infty\; \backslash frac\{\backslash rho(t)\}\{(t+1)^2\}\; dt$

여기서 $\backslash rho(t)$는 딕맨 함수(Dickman–de Bruijn function)이다.