Posts Tagged ‘ Pick의 정리 ’

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