딕맨 함수

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

1. 개요

딕맨-드 브루인 함수 $\rho(u)$ 는 지연 미분 방정식을 만족하는 연속 함수이며, 주어진 크기에서 스무스 넘버의 빈도를 추정하는 데 사용된다. 이 함수는 폴라드 p-1 알고리즘과 같은 수론 알고리즘 최적화에 활용될 수 있다. 딕맨-드 브루인 함수는 $\Psi(x, x^{1/a})\sim x\rho(a)$ 의 관계를 가지며, 여기서 $\Psi(x,y)$ 는 x보다 작고 y-스무스 정수의 개수를 나타낸다. 딕맨-드 브루인 함수는 $\rho(u)\approx u^{-u}$ 로 근사될 수 있으며, 지수 적분을 사용하여 더 정확하게 추정할 수 있다.

딕맨 함수

📚 더 읽어볼만한 페이지

수학 상수 - 허수 단위
허수 단위 i는 i² = −1을 만족하는 수로, 실수 체계에서는 정의되지 않는 음수의 제곱근을 나타내며 복소수 체계의 기본 구성 요소로서 복소평면에서 90° 회전하는 효과를 가지며 1, i, -1, -i를 주기적으로 순환하는 특징을 가진다.
수학 상수 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.
특수 함수 - 람베르트 W 함수
람베르트 W 함수는 we^w = z를 만족하는 w를 찾는 람베르트 이름을 딴 역함수 관계를 가지며, 여러 분야에서 지수 함수 방정식을 푸는 데 응용되는 무한히 많은 가지를 가진 함수이다.
특수 함수 - 감마 함수
감마 함수는 양의 실수부를 갖는 복소수 z에 대해 오일러 적분으로 정의되고 해석적 연속을 통해 복소평면 전체로 확장된 팩토리얼 함수의 일반화로서, 수학, 물리학, 공학 등 다양한 분야에서 활용되며 여러 표현과 성질을 가진다.
해석적 수론 - 타원곡선
타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
해석적 수론 - 리만 제타 함수
리만 제타 함수는 복소수 s의 함수로, 실수부가 1보다 큰 영역에서 무한급수로 정의되고 s ≠ 1인 모든 복소수에서 유리형 함수로 해석적 연속이 가능하며 함수 방정식과 오일러 곱 공식을 만족하고, 영점 분포는 소수 분포와 관련이 있으며, 비자명 영점이 임계선 상에 있다는 리만 가설은 중요한 미해결 문제이다.

1. 개요
2. 정의
3. 성질
4. 응용
5. 추정
6. 계산
7. 확장

2. 정의

딕맨-드 브루인 함수 $\rho(u)$ 는 다음 지연 미분 방정식을 만족하는 연속 함수이다.
: $u\rho'(u) + \rho(u-1) = 0\,$
초기 조건은 0 ≤ u ≤ 1일 때 $\rho(u) = 1$ 이다.

딕맨(Dickman)은 고정된 상수 $a$ 에 대해 다음이 성립함을 증명했다.
: $\Psi(x, x^{1/a})\sim x\rho(a)\,$
여기서 $\Psi(x,y)$ 는 $y$ 보다 작은 소인수만을 갖는 $x$ 이하의 양의 정수(즉, $y$ -smooth 또는 $y$ -friable 정수)의 개수를 나타낸다.

이후 라마스와미(Ramaswami)는 고정된 $a$ 에 대해 $\Psi(x,x^{1/a})$ 가 $x \rho(a)$ 에 점근하며, 오차항을 포함하여 다음과 같이 표현됨을 더 엄격하게 증명했다.
: $\Psi(x,x^{1/a})=x\rho(a)+O(x/\log x)$
( $O$ 는 대문자 O 표기법이다.)

3. 성질

딕맨-드 브루인 함수 $\rho(u)$ 는 다음의 지연 미분 방정식을 만족하는 연속 함수이다.

: $u\rho'(u) + \rho(u-1) = 0\,$

이때 초기 조건은 $\rho(u) = 1$ (단, $0 \le u \le 1$ )이다.

딕맨은 고정된 상수 a에 대해 다음 관계가 성립함을 증명했다.

: $\Psi(x, x^{1/a})\sim x\rho(a)\,$

여기서 $\Psi(x,y)$ 는 x보다 작거나 같고, 가장 큰 소인수가 y보다 작거나 같은 정수, 즉 y-스무스(또는 y-프라이어블) 수의 개수를 나타낸다.

나중에 라마스와미는 고정된 a에 대해 $\Psi(x,x^{1/a})$ 가 $x \rho(a)$ 에 점근한다는 것을 더 엄밀하게 증명했으며, 오차항은 다음과 같다.

: $\Psi(x,x^{1/a})=x\rho(a)+O(x/\log x)$

4. 응용

딕맨-드 브루인 함수의 주요 목적은 주어진 크기에서 스무스 넘버의 빈도를 추정하는 것이다. 이는 폴라드 p-1 알고리즘과 같은 다양한 수론 알고리즘을 최적화하는 데 사용될 수 있으며, 그 자체로도 유용하다.

딕맨은 고정된 $a$ 에 대해 다음을 증명했다.
: $\Psi(x, x^{1/a})\sim x\rho(a)\,$
여기서 $\Psi(x,y)$ 는 $y$ 이하의 스무스 넘버(y-smooth 또는 y-friable)인 양의 정수의 개수를 나타낸다.

라마스와미(Ramaswami)는 나중에 고정된 $a$ 에 대해 $\Psi(x,x^{1/a})$ 가 $x \rho(a)$ 에 점근하며, 오차 항을 포함하여 다음과 같이 표현된다는 더 엄격한 증거를 제시했다.
: $\Psi(x,x^{1/a})=x\rho(a)+O(x/\log x)$
(O 표기법 사용)

x의 가장 큰 소인수와 두 번째로 큰 소인수가 x^a보다 작을 확률을 계산하는 데 사용되는 딕맨-드 브루인 함수

또한 다음이 증명될 수 있다.
:

\Psi(x,y)=xu^{O(-u)}

이는

\rho(u)\approx u^{-u}

라는 추정치와 관련이 있다.

골롬-딕맨 상수는 딕맨-드 브루인 함수와 관련하여 정의되기도 한다.

5. 추정

딕맨-드 브루인(Dickman-de Bruijn) 함수 $\rho(u)$ 는 다음 지연 미분 방정식을 만족하는 연속 함수이다.

: $u\rho'(u) + \rho(u-1) = 0\,$

이때 초기 조건은 $\rho(u) = 1$ (0 ≤ u ≤ 1)이다. 딕맨(Dickman)은 고정된 $a$ 에 대해 다음이 성립함을 증명했다.

: $\Psi(x, x^{1/a})\sim x\rho(a)\,$

여기서 $\Psi(x,y)$ 는 $y$ -smooth (또는 $y$ -friable)인 $x$ 이하의 정수의 개수를 나타낸다.

라마스와미(Ramaswami)는 나중에 고정된 $a$ 에 대해 $\Psi(x,x^{1/a})$ 가 $x \rho(a)$ 에 점근하며, 오차항을 포함하여 다음과 같이 표현된다는 엄밀한 증명을 제시했다.

: $\Psi(x,x^{1/a})=x\rho(a)+O(x/\log x)$

위 식에서 $O$ 는 대문자 O 표기법을 의미한다.

딕맨 함수 $\rho(u)$ 에 대한 첫 번째 근사는 $\rho(u)\approx u^{-u}$ 로 나타낼 수 있다. 더 나은 추정치는 다음과 같다.

: $\rho(u)\sim \frac 1 {\xi\sqrt{2\pi u}} \cdot \exp(-u\xi+\operatorname{Ei}(\xi))$

여기서 Ei는 지수 적분 함수이고, $\xi$ 는 다음 방정식의 양의 근이다.

: $e^\xi-1=u\xi.\,$

딕맨 함수에 대한 간단한 상한은 $\rho(x)\le1/x!$ 이다.

다음은 몇 가지 $u$ 값에 대한 $\rho(u)$ 의 근사값이다.

👆

좌우로 밀어서 보기

$u$	$\rho(u)$
1	1
2	0.30685282
3	0.048608388
4	0.0049109256
5	0.00035472470
6	0.000019649696
7	0.00000087456700
8	0.000000032320693
9	0.0000000010162483
10	0.000000000027701718

6. 계산

딕맨-드 브루인(Dickman-de Bruijn) 함수 $\rho(u)$ 는 다음 지연 미분 방정식을 만족하는 연속 함수이다.

: $u\rho'(u) + \rho(u-1) = 0\,$

초기 조건은 0 ≤ u ≤ 1 범위에서 $\rho(u) = 1$ 이다. 딕맨(Dickman)은 고정된 $a$ 에 대해 다음 관계가 성립함을 증명했다.

: $\Psi(x, x^{1/a})\sim x\rho(a)\,$

여기서 $\Psi(x,y)$ 는 $y$ 이하의 소인수만을 갖는 정수(y-smooth 또는 y-friable 정수)의 개수를 나타낸다.

라마스와미(Ramaswami)는 나중에 고정된 $a$ 에 대해 $\Psi(x,x^{1/a})$ 가 $x \rho(a)$ 에 점근하며, 오차항은 다음과 같음을 더 엄격하게 증명했다.

: $\Psi(x,x^{1/a})=x\rho(a)+O(x/\log x)$

(O 표기법 참고)

각 정수 n에 대해, 구간 [n − 1, n]에서 $\rho(u)$ 와 같은 값을 가지는 해석 함수 $\rho_n(u)$ 가 존재한다. 구간별 $\rho(u)$ 의 값은 다음과 같다.
* 0 ≤ u ≤ 1: $\rho(u) = 1$
* 1 ≤ u ≤ 2: $\rho(u) = 1-\log u$
* 2 ≤ u ≤ 3:
: $\rho(u) = 1-(1-\log(u-1))\log(u) + \operatorname{Li}_2(1 - u) + \frac{\pi^2}{12}.$
여기서 Li₂는 딜로그 함수이다. 다른 구간에서의 $\rho_n$ 값은 무한 급수를 사용하여 계산할 수 있다.

함수 값을 계산하는 또 다른 방법은 사다리꼴 공식을 사용하여 하한과 상한을 구하는 것이다. 계산 간격을 점차 미세하게 조정하면 임의의 정확도를 얻을 수 있다. 매우 높은 정밀도(수백 자리) 계산이 필요한 경우에는 구간의 중간점에 대한 재귀 급수 전개가 더 효율적이다.

7. 확장

딕맨-드 브루인 함수 $\rho(u)$ 는 지연 미분 방정식 $u\rho'(u) + \rho(u-1) = 0$ 을 만족하는 연속 함수이며, $0 < u \le 1$ 에서 $\rho(u) = 1$ 이라는 초기 조건을 갖는다. 딕맨(Dickman)은 고정된 $a$ 에 대해 $\Psi(x, x^{1/a})\sim x\rho(a)$ 임을 보였다. 여기서 $\Psi(x,y)$ 는 $x$ 이하의 정수 중 가장 큰 소인수가 $y$ 이하인 수(y-매끄러운 수(y-friable number))의 개수를 나타낸다.

라마스와미(Ramaswami)는 나중에 고정된 $a$ 에 대해 $\Psi(x,x^{1/a})$ 가 $x \rho(a)$ 에 점근하며, 오차항을 포함하여 다음과 같음을 더 엄격하게 증명했다.
: $\Psi(x,x^{1/a})=x\rho(a)+O(x/\log x)$
여기서 $O$ 는 대문자 O 표기법이다.

존 프리들랜더(John Friedlander)는 딕맨 함수를 확장하여 2차원 유사체인 $\sigma(u,v)$ 를 정의했다. 이 함수는 $\Psi(x,y,z)$ , 즉 $x$ 이하의 y-매끄러운 정수 중에서 $z$ 보다 큰 소인수를 최대 1개만 갖는 수의 개수를 추정하는 데 사용된다. 이 함수를 이용하면 다음과 같은 점근식이 성립한다.
: $\Psi(x,x^{1/a},x^{1/b})\sim x\sigma(b,a)$