π < 2φ의 조합적 증명

황금비 \phi=\frac{1+\sqrt{5}}{2}에 대해 \pi < 2\phi가 성립한다는 것을 조합적으로 증명한 논문[1]을 읽었다. (타이틀이 자동적으로 대문자화되는 바람에 Π < 2Φ이 되어버림… 그리스 문자까지 변환할 줄은 몰랐다;) 요는 피보나치 수 F_n과 오일러 수 E_n(Eulerian number 말고 Euler number. 보통 교대순열(alternating permutation)의 개수로 정의된다)의 곱이 n!보다 크거나 같고, \displaystyle F_n \sim \frac{1}{\sqrt{5}} \phi^{n+1}\displaystyle E_n \sim \frac{4}{\pi} (\frac{2}{\pi})^n n!이기 때문에 \displaystyle F_n \cdot E_n \sim cn! (\frac{2\phi}{\pi})^n으로 증명이 끝난다는 것. 여기서 F_n \cdot E_n \geq n!을 조합적으로 보인 것이다.

먼저, \mathcal{B}_n을 세 심볼 \circ, \subset, \supset로 이루어지고, \subset 바로 뒤에 \supset이 와야 하며 \supset 바로 앞에 \subset이 있어야 하는 길이 n의 단어들의 집합으로 정의한다. 예컨대 \mathcal{B}_4=\{\circ\circ \circ\circ,\circ\circ\subset\supset,\circ\subset\supset\circ,\subset\supset\circ\circ ,\subset\supset\subset\supset\}이 된다. 이렇게 정의한 집합 \mathcal{B}_n의 원소의 개수가 바로 F_n이다. 이는 |\mathcal{B}_n|F_n이 같은 점화식+초기값을 갖는다는 것을 통해 확인할 수 있음.

그리고 길이 n인 교대순열의 집합을 \mathcal{A}_n으로 놓는다. 교대순열은 \sigma(1)<\sigma(2)>\sigma(3)<\sigma(4)>\cdots를 만족시키는 순열.

여기서 \Phi:\mathcal{A}_n \times \mathcal{B}_n \rightarrow S_n을 정의한다: 교대순열 \sigma \in \mathcal{A}_n과 단어 w \in \mathcal{B}_n이 주어져있을 때, \sigma에서 w\subset,\supset 쌍에 해당되는 위치를 뒤바꿔 얻는 순열을 \Phi(\sigma,w)로 정의한다. 예컨대, \Phi \left( (3,6,2,5,4,7,1,8), \circ\circ\subset\supset\circ\subset\supset\circ \right) = (3,6,5,2,4,1,7,8)이 된다. 그러면 이 \Phi가 전사함수라는 것. 이는 뒤바꿔 말하면, 임의의 순열을 택해도 몇 개의 연속하게 위치한 쌍을 겹치지 않게 선택해서 각각에 대해 두 수를 뒤바꾸면 교대순열을 얻을 수 있다는 것과 동치이다. 순열의 짝수 번째에 위치한 수들의 최솟값을 주목해 경우를 나눠 필요에 따라 뒤바꾸는 행위를 하고 그 수의 왼쪽 파트와 오른쪽 파트에 대해 재귀를 돌리는 것으로 증명을 완료한다. 디테일은 논문 참조.

비교적 elementary하고 마지막 해석적 스텝을 거친 결론은 다소 수학적 해학을 의도한 느낌이 나는데, Igor Pak 선생님의 말씀에 의하면 애초부터 연구논문이라기보다는 학부생을 위한 내용에 가까웠다고. 즉 일종의 주의 환기용 statement. 참고로 F_n \cdot E_n \geq n!은 Sidorenko’s theorem[2]의 특수 케이스이다.

방금 John Carlos Baez 선생님의 트윗을 보고 떠올라 정리했다.

트윗 타래를 정리. (2018/04/01)

References

[1] A. H. Morales, I. Pak and G. Panova, “Why Is Pi Less Than Twice Phi?” The American Mathematical Monthly, 125:8, 715-723, DOI:10.1080/00029890.2018.1496757

[2] A. Sidorenko, “Inequalities for the number of linear extensions” Order 8 (1991/92), 331–340.

π < 2φ의 조합적 증명”의 1개의 생각

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중