Posts Tagged ‘ 휘리릭뽕퓨젼 ’

Ehrhart 다항식과 Pick의 정리

2009년 가을 학기에 역시 Richard Stanley 교수님 수업을 듣다가 배운 것 중 가장 흥미로웠던 Ehrhart polynomial을 혼자 재정리했던 내용이다. 천년바위라는 다른 곳의 게시판에 남긴 내용을 조금 다듬어 옮긴다.

Pick의 정리에 대해 들어본 적이 있을 것이다. 간략히 설명하자면, 좌표평면에서 두 좌표가 정수인 것을 격자점이라 할 때 꼭지점이 격자점인 도형의 넓이는 흥미롭게도 (도형 내부의 점의 개수) + (테두리 위의 점의 개수)/2 – 1이 된다. 만약 도형이 무지 큰 경우를 생각하면, 각 점을 중심으로 하는 단위정사각형들이랑 넓이가 얼추 비슷해질 것이다. 대충 그런 의미.

이것이 신기한 이유는 도형의 넓이를 계산하는 것은 복잡할 것 같은데 점의 개수만 세면 되기 때문이다. (비록 격자점 case에만 해당되지만) 곧 소개하겠지만, 점의 개수를 센다는 것이 사실은 생각보다 엄청난 행위이다.

이제 이를 3차원으로 확장해보자. 만약 어떤 다면체의 꼭지점들이 전부 격자점이면 그 부피는 무엇과 연관이 있을까? 내부의 점과 면 위의 점들 개수란 두 정보만으로 표현이 될까? 약간 아쉽지만 답은 부정적이다. 하지만 뭔가 한 요소를 더하면 표현이 가능하다! 왜 둘만으로는 부족할까. “왜냐하면 3차원이기 때문이다. 2차원에선 두 가지 요소로 표현이 되지만 3차원에선 세 가지 요소가 필요하다.”란 설명은 뭔가 상당히 석연찮은 설명이다. 하지만 결과론적으로 저 설명이 맞다. 왜냐하면 n차원 내에서의 볼록 격자 도형은 차수가 n인 다항식이 붙고 그 최고차항계수가 부피와 연관되기 때문이다.

그럼 본격적으로 어떤 다항식인지 알아보자. Ehrhart polynomial이란 이름이 붙은 다항식은 m차원 공간 \mathbb{R}^m에서 \mathbb{Z}^m의 원소들을 꼭지점으로 갖는 볼록도형 P에 대해, i(P,n) = \#\{nP \cap \mathbb{Z}^m\}으로 정의된다. 즉, Pn배 확대시킨 것의 내부의 (경계 포함) 격자점 개수로 정의한다. 아주 쉬운 예로, 2차원 공간에서 (0,0), (1,0), (1,1), (0,1)을 꼭지점으로 갖는 정사각형을 생각한다면 i(P,n)=(n+1)^2이 된다. 이와 쌍대적인 개념으로 (dual) \bar{i}(P,n)을 생각할 수 있는데, 이것은 Pn배 확대시킨 것의 내부 (경계 포함하지 않음) 격자점의 개수이다. 즉 위의 예시에서 \bar{i}(P,n)=(n-1)^2이다.

위와 같이 정사각형처럼 변들이 착착 맞아떨어지는 경우라면 저 식이 n에 대한 다항식이 되리란건 알겠는데, 만약 좀 더 복잡하게 생긴 도형이라면? 그 때도 저렇게 일이 잘 풀린다면 얼마나 좋을까. 그런데 그게 실제로 일어났습니다. 바로 i(P,n)n에 대한 유리계수 다항식임이 증명된 것이다. 또한 그 차수는 P의 차수 d가 되고, (꼭 d=m일 필요는 없다. 삼차원에서 평면 도형인 정사각형을 잡을 수 있듯이) 그 최고차항의 계수는 P의 volume이 되며, i(P,0)=1임을 보인 것이다. (이들의 증명은 positive monoid에 대한 언급을 하지 않을 수 없는데 너무 길어지므로 생략한다.) 또한 충격적이게도, 내부의 점의 개수를 세는 \bar{i}i와 밀접한 관계가 있음도 보여졌다. 바로 \bar{i}(P,n) = (-1)^d i(P,-n)이 되는 것이다. 즉, i(P,n)이란 다항식은 기본적으로 n이 양수라면 n배했을 때의 도형 안의 점의 개수인데 n이 음수라면 그것을 n배했을 때 경계를 제외한 내부의 점의 개수 (에 적당히 부호가 붙은) 가 되는 것이다.

이제 연결고리가 보인다. 2차원의 경우 그 Ehrhart polynomial은 P의 넓이가 A일 때 i(P,n)=An^2 + an + 1로 주어져야 한다. 이 때, i(P,1)=I+B, i(P,-1)=I가 되니까 이 결과들을 종합하면 우리가 원하는 결과인 Pick의 정리를 얻는 것이다. 2차원이니까 식이 2차, 따라서 세 점에 의해 다항식 결정, 그런데 최고차항 계수가 바로 넓이 => 넓이와 몇 가지 “점들의 개수” 간의 관계 도출. 이것이 주요 flow이다.

따라서, 도형이 주어지면 그것을 적당히 확대하여 점을 세는 것만으로 그 도형의 일종의 특성식(=Ehrhart polynomial)을 얻어낼 수 있다는 것이다! 앞에서 점을 세는 행위가 왜 중요한 행위가 되었는지에 대해 짤막히 언급했는데 그 이유가 여기에 있다.

그리하여 Pick의 정리와 똑같은 짓을 Reeve란 사람이 3차원으로 확장했고, Macdonald란 사람이 햄버거 세트를 4차원 이상으로 확장했다. 즉 앞에서 말한 특성식이 구체적으로 어떤 결과를 가져다 주는지를 밝혔다. 정확한 식은 구글링하면 나올텐데 별로 중요치 않고, 중요한 사실은 i(P,2), i(P,1), i(P,0), i(P,-1)의 값을 기하적으로 표현할 수 있고, 최고차항의 계수가 P의 부피임을 이용하여 부피, 도형 내부의 점의 개수, 도형 경계의 점의 개수, 그리고 도형을 2배 확대했을 때의 내부의 점의 개수들의 관계식을 얻어낼 수 있다는 것이다.

예제 1. 음수 계수를 갖는 Ehrhart polynomial이 존재하는가?
예제 2. \mathbb{R}^d에서 2d개의 벡터 \pm e_i들의 볼록포로 이루어진 도형의 Ehrhart polynomial을 i(P_d,n)이라 하면 \displaystyle (1-x)^{d+1} \sum_{n \geq 0} i(P_d,n) x^n은 어떤 다항식이 된다. 그 값을 구하여라.
예제 3. \displaystyle \sum_{n\geq 0}i(P,n)x^n=\frac{1+x^3}{(1-x)^4}, 즉 i(P,n)=\binom{n+3}{3}+\binom{n}{3}인 격자점 볼록 다양체 P는 존재하지 않음을 보여라.

Reference.
M. Beck and S. Robins, Computing the Continuous Discretely, Ch. 3
R. Stanley, Enumerative Combinatorics, Ch. 4

Advertisements

조합 삼각 함수

이 글은 서울과학고 수학연구반 MO의 연회지인 ‘셈사랑’ 19호에 졸업생투고로 낸 원고로, 학부 시절에 Richard Stanley 교수님의 수업을 들으며 알게 된 사실을 조금 정리한 글이다. 앞의 서문은 불필요하다고 생각하여 생략하고 나머지 부분을 조금 다듬었다. 이 글의 본문에는 미분 방정식과 관련된 내용이 조금 언급되는데, 관련 배경 지식이 있으면 좋고 없어도 그 부분만 스킵하고 넘어가도 좋을 것 같다.

일단 한 종류의 수열에 대해서 생각하는 것으로 시작하기로 한다.

정의 1. [n]= \{ 1,2,\cdots,n \}이라 한다. 이 때 이 집합에서 자기 자신으로 대응하는 함수 \sigma:[n] \rightarrow [n] 중에 일대일대응인 것을 순열이라고 부른다.

순열을 표현하는 법에는 두 가지 방법이 있다. 하나는 \sigma(1),\sigma(2),\cdots,\sigma(n)을 나열하는 법으로 순열을 w=w_1w_2\cdots w_n으로 표현하는 것이고, 다른 하나는 싸이클을 이용한 것으로, \sigma^k(a)=a인 최소의 자연수 k에 대해, (a,\sigma(a),\cdots,\sigma^{k-1}(a))을 하나의 싸이클이라 하며 이것들을 합성하여 표현하는 것이다. 이 글에서는 첫 번째 방법인 나열식을 쓰기로 한다. [n]에서 정의되는 순열의 집합은 보통 S_n으로 표시하며, symmetric group이라는 이름을 갖는다.

정의 2. S_n의 원소 중에서, w_1>w_2<w_3>\cdots, 즉 모든 자연수 k에 대해 w_{2k-1}>w_{2k},w_{2k}<w_{2k+1}이 성립하는 순열을 교대순열이라고 한다. 반대로, w_1<w_2>w_3<\cdots, 즉 w_{2k-1}<w_{2k},w_{2k}>w_{2k+1}이 성립하는 순열을 역교대순열이라고 한다.

정의 3. S_n의 교대순열의 개수를 오일러 수라고 하며, E_n으로 표기한다.

그러면 여기서 간단한 정리를 하나 얻을 수 있다.

정리 1. S_n의 역교대순열의 개수 역시 E_n이다.
증명) 일대일대응 f:S_n \rightarrow S_n을 생각하여 f(\sigma)(i)=n+1-\sigma(i)로 정의한다. 그러면 f(\sigma)는 한 순열로, n+1에서 각 \sigma(i)를 뺀 것을 나열한 것이 된다. 곧 f는 교대순열을 역교대순열로 대응시키며, 역대응은 바로 자기 자신으로, 역교대순열을 교대순열로 대응시킨다. 따라서 f는 교대순열과 역교대순열 사이의 일대일대응이 되어 둘의 개수는 같다. -증명끝

수열에 대한 더 자세한 것을 알기 위해서 일반적으로 수학자들은 그에 대한 특성을 찾는데, 그 중의 하나가 생성함수이다. 생성함수를 얻기 위해 점화식을 먼저 얻는 경우도 비일비재한데, 여기에서도 오일러 수 E_n의 점화식을 먼저 살펴보기로 한다.

정리 2. \displaystyle 2E_{n+1}=\sum_{k=0}^n \binom{n}{k}E_kE_{n-k}가 성립한다.
증명) [n]의 부분집합 중에서 원소가 k개인 부분집합 S를 택한다. 그 경우의 수는 \binom{n}{k}이다. 이 때, S 내부에서 역교대순열 u를 잡는 방법의 수는 정의에 의해 E_k이고, S^c에서 역교대순열 v를 잡는 방법의 수는 E_{n-k}이다. 이제 u=u_1u_2 \cdots u_k이라 할 때 u^r=u_ku_{k-1}\cdots u_1이라 하자. 그러면 (u^r)(n+1)(v), 즉 u^rn+1의 왼쪽에 쓰고 vn+1의 오른쪽에 써서 얻어지는 길이 n+1인 순열은 [n+1]의 교대순열이거나 역교대순열이다. (k의 기우성에 따라 그 결과가 다르다.) 또한 임의의 교대순열이나 역교대순열의 경우, n+1을 기준으로 양 옆으로 나눈 후 왼쪽에 있는 것을 거꾸로 한 것과 오른쪽에 있는 것은 모두 역교대순열이다. 왜냐하면 n+1 다음에 나오는 것은 반드시 n+1보다 작으므로, 그 다음은 증가부터 시작하기 때문이다.
따라서 \binom{n}{k}E_kE_{n-k}를 전부 합한 우변의 식은 [n+1]의 모든 교대순열과 역교대순열을 세는 식이 된다. 정리 1에 의해 둘 다 그 개수가 E_{n+1}이므로, 이 식은 좌변인 2E_{n+1}와 같게 되어 증명이 끝난다. -증명끝

이제 E_n과 관련된 생성함수를 찾는다. 이 때, 생성함수보다 지수생성함수를 쓰는 것이 더 적합하다는 것을 깨달아야 한다. 왜냐하면 정리 2에서 얻은 식에는 \binom{n}{k}와 같이 계승을 이용한 것이 나오는데, 지수생성함수가 보다 이것을 원활히 처리해줄 수 있기 때문이다. \displaystyle F(x)=\sum_{n\geq 0} E_n \frac{x^n}{n!}이라 하자. 또한 앞으로의 편의를 위해 E_0=E_1=1으로 정의한다. 그러면 이를 미분한 식은
\displaystyle F'(x)=\sum_{n\geq 0}E_{n+1}\frac{x^n}{n!}=\frac{1}{2}\sum_{n\geq 0}\sum_{k=0}^n \binom{n}{k}E_kE_{n-k}\frac{1}{n!}x^n
이 되어 \displaystyle 2F'(x)=\sum_{n\geq 0}\sum_{k=0}^n \frac{E_k}{k!} \frac{E_{n-k}}{(n-k)!}x^n을 얻는다. 이는 곧 F를 제곱한 것에서 얻는 식이므로, 초기조건과 맞물려 이 관계식을 정리하면 2F'=F^2+1F(0)=1이라는 결과를 얻는다.

한 편, 주어진 구간 내에서 연속 함수에 대한 일차미분방정식은 초기조건이 하나 주어지면 그 해는 유일함이 잘 알려져 있다. 이 미분방정식은 F'만이 연루되어 있으므로 일차이며, 초기조건이 하나 주어져 있으므로 그 해는 유일해야 한다. 여기에서 F(x)=\sec{x}+\tan{x}를 대입하면 등식이 성립하므로, 이것이 그 해가 됨을 알 수 있다. 이를 짧게 정리하면 다음과 같다.

정리 3. \displaystyle \sum_{n\geq 0}E_n\frac{x^n}{n!}=\sec{x}+\tan{x}이 성립한다.

\sec 함수는 우함수, \tan 함수는 기함수라는 데에서, 이 함수의 우함수와 기함수를 분리할 수 있다. 그 결과로, \displaystyle \sum_{n\geq 0}E_{2n}\frac{x^{2n}}{(2n)!}=\sec{x}\displaystyle \sum_{n \geq 0}E_{2n+1}\frac{x^{2n+1}}{(2n+1)!}=\tan{x}를 얻을 수 있다. 곧, 삼각함수를 두 가지 조합등식을 이용해서 역으로 얻어낼 수 있다. 이를 이용하면 \cos\sin을 쉽게 얻을 수 있고, 이는 곧 조합적인 언어만을 이용하여 삼각함수를 재구축할 수 있다는 것이다. 그 결과는 삼각함수가 원래 지니고 있어야 할 기하적인 면이나 해석적인 면이 일체 들어있지 않은 순수 조합적인 그것이 된다.

한 예로 다음 문제를 보자.

정리 4. 1+\sec^2{x}=\tan^2{x}가 성립한다.
증명) 상수항은 쉽게 알 수 있다. x^{2n}의 계수를 계산하기로 하자. 좌변의 계수는 \displaystyle \binom{2n}{0}E_{2n}E_0+\cdots+\binom{2n}{2n}E_0E_{2n}이며, 우변의 계수는 \displaystyle \binom{2n}{1}E_{2n-1}E_1+\cdots+\binom{2n}{2n-1}E_1E_{2n-1}이다. 이 둘이 같음을 증명하기 위해, 길이가 2n+1인 교대순열과 역교대순열을 생각하낟. 앞에서 2n+1을 기준으로 생각할 때에 왼쪽과 오른쪽의 개수를 쉽게 셀 수 있었다. 만약 2n+1 양 옆에 각각 짝수 개의 수들이 있다면, 그 결과는 교대순열이 되고, 따라서 좌변의 계수의 값이 바로 그 개수가 되어 E_{2n+1}이다. 한 편, 2n+1 양 옆에 각각 홀수 개의 수들이 있다면, 그 결과는 역교대순열이 되므로 우변의 계수의 값이 바로 그 개수가 되어 역시 E_{2n+1}이 된다. 따라서 두 계수의 값이 같고, 증명은 끝난다. -증명끝

다음 예제들을 통해, 기존의 정리들을 다른 눈으로 바라보면 다른 방법이 생김을 느껴보고, 한 수학적인 결론은 오직 한 맥락에서만 도출되지 않을 수도 있다는 것을 깨달아보자.

예제 1. \tan{x}+\tan{y}=(\tan(x+y))(1-\tan{x}\tan{y})를 조합적으로 증명하여라.
예제 2. \displaystyle \sec{x}(\sum_{n\geq 0} \frac{(-1)^nx^{2n}}{(2n)!})=1를 조합적으로 증명하여라.
예제 3. \displaystyle \tan{x}=(\sum_{n\geq 0} \frac{(-1)^nx^{2n+1}}{(2n+1)!})(\sec{x})를 조합적으로 증명하여라.