[정수론] 승법적 수론함수 (multiplicative number-theoretic function) 와 뫼비우스 변환(Möbius Transform)
Math/Numbers/Combinatorics2011. 1. 16. 01:55 |number-theoretic function (수론함수) 또는 arithmetic function (산술함수) 은 정의역이 자연수인 함수를 말한다.
특히 왼쪽의 것을 f 의 뫼비우스 변환(Möbius Transform) 이라고 부른다. ( 여기서 | 는 나누어떨어짐(divisibility) 의 기호이다. )
뫼비우스 변환의 예로 약수개수 함수 τ 와 약수총합 함수 σ 를 들수 있다.
이 정리를 사용하면, 타우함수와 시그마 함수도 멀티플리케이티브임을 아주 쉽게 보일 수 있다.
어떤 수론함수가 다음의 성질을 만족할 때, multiplicative (승법적) 라고 부르기로 한다.
보통, multiplicative 라고 하면, f(xy) = f(x) f(y) 를 말하는데, 수론함수의 경우, x, y 가 서로소인경우에만 저러면 되므로, 훨씬 더 약한 조건이라고 할 수 있다.
어떤 멀티플리케이티브 수론함수 f 가 , 항상 값이 0 인 함수가 아니라면, 간단히 f(1) = 1 임을 보일수 있다.
f ( n ) = f ( n * 1 ) , n 과 1 은 서로소, 그러므로, f ( n ) = f (n ) * f (1 ) , f ( n ) 이 항상 0 인것은 아니므로, 0 아닌 f ( n ) 이 존재하게 되고,
따라서, 그때의 f(n) 으로 나누면, f ( 1 ) = 1 을 얻는다.
뫼비우스 변환 ( Möbius Transform : summation over all divisors )
수론에서는 서메이션이나 프로덕트를 약수에 대해서 수행하는 경우가 많다.
즉, 다음과 같은 것이다.
( 주의: 복소에서의 Möbius Transformation 과는 다른것이다. )
d 가 n 의 약수일때, d d' = n 이고, d' = n/d 도 역시 n 을 나누기 때문에, 다음이 성립한다.
( 사실, 이것은 서메이션이나 곱 뿐 만 아니라, 다른 지시적 기호에 대해서도 마찬가지이다. )
뫼비우스 변환의 예로 약수개수 함수 τ 와 약수총합 함수 σ 를 들수 있다.
즉, 약수개수함수는 f(k)=1 의 뫼비우스 변환이고, 약수총합함수는 f(k)=k 의 뫼비우스 변환이다.
참고로, 타우함수에 대한 다음의 정리가 성립한다.
즉, 모든 약수의 곱은, 그수에 약수의 개수를 거듭제곱한후에 루트를 씌우면 된다.
일단, 테스트를 해보자.
12 의 약수는 1 , 2, 3, 4, 6 , 12 이고, 모두 곱하면... 1728 이다.
약수의 개수는 6 개 이므로, 12 에 3승 을 하면 1728 이 된다.
증명은 다음과 같다.
뫼비우스 변환의 multiplicativity 보존
" 어떤 수론함수가 멀티플리케이티브이면, 그것의 뫼비우스 변환도 멀티플리케이티브이다. "
증명.
즉, 서로소가 곱해진걸 누가 나눈다면, 각각 나누는 녀석들이 필요하다는 뜻.
아무튼, 그러므로 다음과 같이 된다.
이 정리를 사용하면, 타우함수와 시그마 함수도 멀티플리케이티브임을 아주 쉽게 보일 수 있다.
이 정리는 역도 성립하는데, 우리는 다음에 뫼비우스 반전공식을 사용하여, 역이 성립함을 증명할 것이다.