Smooth number, friable number
특정 수 이하의 소인수만을 가지는 자연수를 말한다.
자연수
n n n 이
k k k -부드러운 정수(k-smooth number)라는 것은
n n n 이
k k k 이하의 소인수만을 가진다는 것이다.
딕맨(Karl Dickman)은 1930년의 논문
(1) 에서 다음을 증명했다.
ψ ( x , y ) \psi(x,y) ψ ( x , y ) 를
x x x 이하의 자연수 중
y y y -부드러운 정수의 개수라고 정의하자. 이 때
딕맨 함수 ρ \rho ρ 에 대해 다음이 성립한다.
ψ ( x , y ) ∼ x ρ ( u ) \psi(x,y) \sim x\rho(u) ψ ( x , y ) ∼ x ρ ( u ) 여기서
u = log x / log y u=\log x/\log y u = log x / log y 이다. 조금 더 정확히는, 다음이 성립한다.
ψ ( x , y ) = x ρ ( u ) + O ( x log y ) \psi(x,y)=x\rho(u)+O\left({x \over \log y}\right) ψ ( x , y ) = x ρ ( u ) + O ( l o g y x ) 증명하고자 하는 것은 임의의
U ≥ 0 U\geq0 U ≥ 0 에 대해
0 ≤ u ≤ U , x ≥ 2 0\leq u\leq U,\ x\geq2 0 ≤ u ≤ U , x ≥ 2 에서
ψ ( x , y ) = x ρ ( u ) + O ( x log y ) \psi(x,y)=x\rho(u)+O\left({x \over \log y}\right) ψ ( x , y ) = x ρ ( u ) + O ( l o g y x ) 가 균등하게(uniformly) 성립한다는 것이다. 이를 위해
U U U 에 대한 귀납법을 사용할 것이다.
0 ≤ u ≤ 1 0\leq u\leq1 0 ≤ u ≤ 1 일 때는
y ≥ x y\geq x y ≥ x 이므로
ψ ( x , y ) = [ x ] = x + O ( 1 ) \psi(x,y)=[x]=x+O(1) ψ ( x , y ) = [ x ] = x + O ( 1 ) 에서 자명하게 성립한다.
1 ≤ u ≤ 2 1\leq u\leq 2 1 ≤ u ≤ 2 일 때는
x 1 / 2 ≤ y ≤ x x^{1/2}\leq y\leq x x 1/2 ≤ y ≤ x 이므로
x x x 이하의 자연수가
y y y 보다 큰 소인수를 두 개 이상 가질 수 없다. 따라서
ψ ( x , y ) = [ x ] − ∑ y < p ≤ x ∑ n ≤ x p ∣ n 1 = [ x ] − ∑ y < p ≤ x [ x p ] = x − x ∑ y < p ≤ x 1 p + O ( π ( x ) ) = ( 1 − log u ) x + O ( x log x ) \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} ψ ( x , y ) = [ x ] − y < p ≤ x ∑ p ∣ n n ≤ x ∑ 1 = [ x ] − y < p ≤ x ∑ [ p x ] = x − x y < p ≤ x ∑ p 1 + O ( π ( x )) = ( 1 − log u ) x + O ( log x x ) 으로 성립한다. (
1 ≤ u ≤ 2 1\leq u\leq2 1 ≤ u ≤ 2 에서,
ρ ( u ) = 1 − log u \rho(u)=1-\log u ρ ( u ) = 1 − log u 이다.)
이렇게 초기조건이 증명되었다.
이제
U ∈ Z , U ≥ 2 U\in\Bbb Z,\ U\geq2 U ∈ Z , U ≥ 2 에 대해 증명하고자 하는 것이 성립한다고 가정하고, 이것이
[ U , U + 1 ] [U,U+1] [ U , U + 1 ] 에서도 성립함을 보이자.
P ( n ) P(n) P ( n ) 을
n n n 의 최대소인수로 정의하면, 다음이 성립한다.
ψ ( x , y ) = 1 + ∑ p ≤ y ∣ { n ≤ x ∣ P ( n ) = p } ∣ \psi(x,y)=1+\sum_{p\leq y} |\{n\leq x \mid P(n)=p\}| ψ ( x , y ) = 1 + ∑ p ≤ y ∣ { n ≤ x ∣ P ( n ) = p } ∣ n n n 의 최대소인수가
p p p 라는 것은
n / p n/p n / p 의 최대소인수가
p p p 이하라는 것이므로
∣ { n ≤ x ∣ P ( n ) = p } ∣ = ψ ( x / p , p ) |\{n\leq x \mid P(n)=p\}|=\psi(x/p,p) ∣ { n ≤ x ∣ P ( n ) = p } ∣ = ψ ( x / p , p ) 이다. 따라서 다음과 같이 쓸 수 있다.
ψ ( x , y ) = 1 + ∑ p ≤ y ψ ( x / p , p ) \psi(x,y)=1+\sum_{p\leq y} \psi(x/p,p) ψ ( x , y ) = 1 + ∑ p ≤ y ψ ( x / p , p ) 그러므로
y ≤ z y\leq z y ≤ z 일 때 다음이 성립한다.
ψ ( x , y ) = ψ ( x , z ) − ∑ y < p ≤ z ψ ( x / p , p ) \psi(x,y)=\psi(x,z)-\sum_{y<p\leq z} \psi(x/p,p) ψ ( x , y ) = ψ ( x , z ) − ∑ y < p ≤ z ψ ( x / p , p ) U ≤ u ≤ U + 1 U\leq u\leq U+1 U ≤ u ≤ U + 1 에 대해
y = x 1 / u , z = x 1 / U y=x^{1/u},\ z=x^{1/U} y = x 1/ u , z = x 1/ U 로 두고,
u p = log x log p − 1 \displaystyle u_p={\log x\over \log p}-1 u p = log p log x − 1 로 정의하면
p = ( x p ) 1 / u p \displaystyle p=({x\over p})^{1/u_p} p = ( p x ) 1/ u p 가 되며
p ≥ y p\geq y p ≥ y 일 때
u p ≤ u − 1 ≤ U u_p\leq u-1\leq U u p ≤ u − 1 ≤ U 이다. 따라서 귀납가설에 의해 다음이 성립한다.
ψ ( x , y ) = ψ ( x , z ) − ∑ y < p ≤ z ψ ( x / p , p ) = ( ρ ( U ) x + O ( x log x ) ) − ( x ∑ y < p ≤ z ρ ( u p ) p + O ( x ∑ y < p ≤ z 1 p log x p ) ) \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} ψ ( x , y ) = ψ ( x , z ) − y < p ≤ z ∑ ψ ( x / p , p ) = ( ρ ( U ) x + O ( log x x ) ) − ( x y < p ≤ z ∑ p ρ ( u p ) + O ( x y < p ≤ z ∑ p log p x 1 ) ) 이제
s ( w ) = ∑ p ≤ w 1 p = log log w + c + r ( w ) \displaystyle s(w)=\sum_{p\leq w} {1\over p}=\log\log w+c+r(w) s ( w ) = p ≤ w ∑ p 1 = log log w + c + r ( w ) 로 정의하면
(2) , 다음을 얻을 수 있다.
∑ y < p ≤ z ρ ( u p ) p = ∑ y < p ≤ z ρ ( u p ) 1 p = ∫ y z ρ ( u w ) d s ( w ) = ∫ y z ρ ( u w ) d log log w + ∫ y z ρ ( u w ) d 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} y < p ≤ z ∑ p ρ ( u p ) = y < p ≤ z ∑ ρ ( u p ) p 1 = ∫ y z ρ ( u w ) d s ( w ) = ∫ y z ρ ( u w ) d log log w + ∫ y z ρ ( u w ) d r ( w ) 두 적분을 따로 계산하자.
t = log x log w t={\log x\over\log w} t = l o g w l o g x 로 두면
d log log w = d w / ( w log w ) = − d t / t d\log\log w=dw/(w\log w)=-dt/t d log log w = d w / ( w log w ) = − d t / t 이므로 첫 번째 적분은 다음과 같다.
∫ y z ρ ( u w ) d log log w = ∫ U u ρ ( t − 1 ) d t t \int_y^z \rho(u_w) d\log\log w = \int_U^u \rho(t-1) {dt\over t} ∫ y z ρ ( u w ) d log log w = ∫ U u ρ ( t − 1 ) t d t 두 번째 적분에 대해서는, 부분적분을 한 다음
r ( w ) ≪ 1 log w r(w)\ll{1\over\log w} r ( w ) ≪ l o g w 1 임을 이용하면 다음과 같이 계산할 수 있다.
∫ y z ρ ( u w ) d r ( w ) = ρ ( u w ) r ( w ) ∣ y z − ∫ y z r ( w ) d ρ ( u w ) ≪ 1 log x ( 1 + ∫ y z 1 ∣ d ρ ( u w ) ∣ ) ≪ 1 log x \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} ∫ y z ρ ( u w ) d r ( w ) = ρ ( u w ) r ( w ) y z − ∫ y z r ( w ) d ρ ( u w ) ≪ log x 1 ( 1 + ∫ y z 1∣ d ρ ( u w ) ∣ ) ≪ log x 1 또
log log z = log log y + O ( 1 ) \log\log z=\log\log y+O(1) log log z = log log y + O ( 1 ) 에서 다음이 성립한다.
x ∑ y < p ≤ z 1 p log x p ≪ x log x ∑ y < p ≤ z 1 p ≪ x log x 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} x ∑ y < p ≤ z p l o g p x 1 ≪ l o g x x ∑ y < p ≤ z p 1 ≪ l o g x x 이상을 종합하면
U ≤ u ≤ U + 1 U\leq u\leq U+1 U ≤ u ≤ U + 1 에서 다음을 얻는다.
ψ ( x , y ) = x ( ρ ( U ) − ∫ U u ρ ( t − 1 ) d t t ) + O ( x log x ) = x ρ ( u ) + O ( x log x ) \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) ψ ( x , y ) = x ( ρ ( U ) − ∫ U u ρ ( t − 1 ) t d t ) + O ( l o g x x ) = x ρ ( u ) + O ( l o g x x ) 따라서 귀납조건을 보였고, 본 명제가 증명되었다.
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
