부드러운 정수

(+)분류 : 가져온 문서/오메가

Smooth number, friable number

특정 수 이하의 소인수만을 가지는 자연수를 말한다.

목차

1. 정의
2. 분포
2.1. 증명
3. 보기
4. 참고 문헌

1. 정의 _{✎ ⊖}

자연수 n이 k-부드러운 정수(k-smooth number)라는 것은 n이 k 이하의 소인수만을 가진다는 것이다.

2. 분포 _{✎ ⊖}

딕맨(Karl Dickman)은 1930년의 논문⁽¹⁾에서 다음을 증명했다.

\\psi(x,y)를 x 이하의 자연수 중 y-부드러운 정수의 개수라고 정의하자. 이 때 딕맨 함수 \\rho에 대해 다음이 성립한다.
\\psi(x,y) \\sim x\\rho(u)

여기서 u=\\log x/\\log y이다. 조금 더 정확히는, 다음이 성립한다.

\\psi(x,y)=x\\rho(u)+O\\left({x \\over \\log y}\\right)

2.1. 증명 _{✎ ⊖}

증명하고자 하는 것은 임의의 U\\geq0에 대해 0\\leq u\\leq U,\\ x\\geq2에서 \\psi(x,y)=x\\rho(u)+O\\left({x \\over \\log y}\\right)가 균등하게(uniformly) 성립한다는 것이다. 이를 위해 U에 대한 귀납법을 사용할 것이다.

0\\leq u\\leq1일 때는 y\\geq x이므로 \\psi(x,y)=[x]=x+O(1)에서 자명하게 성립한다.

1\\leq u\\leq 2일 때는 x^{1/2}\\leq y\\leq x이므로 x 이하의 자연수가 y보다 큰 소인수를 두 개 이상 가질 수 없다. 따라서

\\begin{aligned} \\psi(x,y) &=[x]-\\sum_{y<p\\leq x} \\sum_{n\\leq x \\atop p|n} 1 \\\\ &=[x]-\\sum_{y<p\\leq x} \\left[{x\\over p}\\right] \\\\ &=x-x\\sum_{y<p\\leq x} {1\\over p}+O(\\pi(x)) \\\\ &= (1-\\log u)x+O\\left(x\\over\\log x\\right) \\end{aligned}

으로 성립한다. (1\\leq u\\leq2에서, \\rho(u)=1-\\log u이다.)

이렇게 초기조건이 증명되었다.

이제 U\\in\\Bbb Z,\\ U\\geq2에 대해 증명하고자 하는 것이 성립한다고 가정하고, 이것이 [U,U+1]에서도 성립함을 보이자.

P(n)을 n의 최대소인수로 정의하면, 다음이 성립한다.

\\psi(x,y)=1+\\sum_{p\\leq y} |\\{n\\leq x \\mid P(n)=p\\}|

n의 최대소인수가 p라는 것은 n/p의 최대소인수가 p 이하라는 것이므로 |\\{n\\leq x \\mid P(n)=p\\}|=\\psi(x/p,p)이다. 따라서 다음과 같이 쓸 수 있다.

\\psi(x,y)=1+\\sum_{p\\leq y} \\psi(x/p,p)

그러므로 y\\leq z일 때 다음이 성립한다.

\\psi(x,y)=\\psi(x,z)-\\sum_{y<p\\leq z} \\psi(x/p,p)

U\\leq u\\leq U+1에 대해 y=x^{1/u},\\ z=x^{1/U}로 두고, \\displaystyle u_p={\\log x\\over \\log p}-1로 정의하면 \\displaystyle p=({x\\over p})^{1/u_p}가 되며 p\\geq y일 때 u_p\\leq u-1\\leq U이다. 따라서 귀납가설에 의해 다음이 성립한다.

\\begin{aligned} \\psi(x,y) &=\\psi(x,z)-\\sum_{y<p\\leq z} \\psi(x/p,p) \\\\ &=\\left(\\rho(U)x + O\\left({x\\over\\log x}\\right)\\right) - \\left(x\\sum_{y<p\\leq z} {\\rho(u_p)\\over p} + O\\left(x\\sum_{y<p\\leq z} {1\\over p\\log{x\\over p}}\\right)\\right) \\end{aligned}

이제 \\displaystyle s(w)=\\sum_{p\\leq w} {1\\over p}=\\log\\log w+c+r(w)로 정의하면⁽²⁾, 다음을 얻을 수 있다.

\\begin{aligned} \\sum_{y<p\\leq z} {\\rho(u_p)\\over p} &=\\sum_{y<p\\leq z} \\rho(u_p){1\\over p} \\\\ &=\\int_y^z \\rho(u_w) ds(w) \\\\ &=\\int_y^z \\rho(u_w) d\\log\\log w + \\int_y^z \\rho(u_w) dr(w) \\end{aligned}

두 적분을 따로 계산하자.

t={\\log x\\over\\log w}로 두면 d\\log\\log w=dw/(w\\log w)=-dt/t이므로 첫 번째 적분은 다음과 같다.

\\int_y^z \\rho(u_w) d\\log\\log w = \\int_U^u \\rho(t-1) {dt\\over t}

두 번째 적분에 대해서는, 부분적분을 한 다음 r(w)\\ll{1\\over\\log w}임을 이용하면 다음과 같이 계산할 수 있다.

\\begin{aligned} \\int_y^z \\rho(u_w) dr(w) &=\\rho(u_w)r(w)\\bigg|_y^z - \\int_y^z r(w) d\\rho(u_w) \\\\ &\\ll {1\\over\\log x}\\left(1+\\int_y^z 1 |d\\rho(u_w)|\\right) \\\\ &\\ll {1\\over\\log x} \\end{aligned}

또 \\log\\log z=\\log\\log y+O(1)에서 다음이 성립한다.

x\\sum_{y<p\\leq z} {1\\over p\\log{x\\over p}} \\ll {x\\over\\log x} \\sum_{y<p\\leq z} {1\\over p} \\ll {x\\over\\log x}

이상을 종합하면 U\\leq u\\leq U+1에서 다음을 얻는다.

\\psi(x,y)=x\\left(\\rho(U)-\\int_U^u \\rho(t-1) {dt\\over t}\\right) + O\\left({x\\over\\log x}\\right)=x\\rho(u)+O\\left({x\\over\\log x}\\right)

따라서 귀납조건을 보였고, 본 명제가 증명되었다.

3. 보기 _{✎ ⊖}

딕맨 함수

4. 참고 문헌 _{✎ ⊖}

Hugh L. Montgomery, Robert C. Vaughan (2007). Multiplicative number theory. I. Classical theory. Cambridge Studies in Advanced Mathematics 97. Cambridge University Press. ISBN 0-521-84903-9

이 문서의 내용 중 전체 또는 일부는 오메가에서 가져왔으며 CC BY-NC-SA 3.0에 따라 이용할 수 있습니다.

(1) Dickman, K. (1930). On the frequency of numbers containing prime factors of a certain relative magnitude, Ark. Mat. Astr. fys. 22, 1–14.

(2) c는 오일러 상수 \\gamma에 대해 \\gamma-\\sum_p\\sum_{k=2}^\\infty {1\\over kp^k}로 정의되는 상수이고, r(w)는 O\\left({1\\over\\log w}\\right)인 함수이다.

1. 정의 ✎ ⊖

2. 분포 ✎ ⊖

2.1. 증명 ✎ ⊖

3. 보기 ✎ ⊖

4. 참고 문헌 ✎ ⊖

1. 정의 _{✎ ⊖}

2. 분포 _{✎ ⊖}

2.1. 증명 _{✎ ⊖}

3. 보기 _{✎ ⊖}

4. 참고 문헌 _{✎ ⊖}