π < 2φ의 조합적 증명

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

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

그리고 길이 인 교대순열의 집합을 으로 놓는다. 교대순열은 를 만족시키는 순열.

여기서 을 정의한다: 교대순열 과 단어 이 주어져있을 때, 에서 의 쌍에 해당되는 위치를 뒤바꿔 얻는 순열을 로 정의한다. 예컨대, 이 된다. 그러면 이 가 전사함수라는 것. 이는 뒤바꿔 말하면, 임의의 순열을 택해도 몇 개의 연속하게 위치한 쌍을 겹치지 않게 선택해서 각각에 대해 두 수를 뒤바꾸면 교대순열을 얻을 수 있다는 것과 동치이다. 순열의 짝수 번째에 위치한 수들의 최솟값을 주목해 경우를 나눠 필요에 따라 뒤바꾸는 행위를 하고 그 수의 왼쪽 파트와 오른쪽 파트에 대해 재귀를 돌리는 것으로 증명을 완료한다. 디테일은 논문 참조.

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

pi = 3.14159… while 22/7 = 3.14285… so 22/7 is bigger. But here's a cute proof that 22/7 is bigger.

The integral that gives 22/7 – pi is surprisingly elegant, and it's clearly positive since you're integrating a positive function. pic.twitter.com/Dj2HJMYRJD

— John Carlos Baez (@johncarlosbaez) January 11, 2019

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

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

https://t.co/DBl9KINg7P (Morales-Pak-Panova, 2016) 피보나치수와 오일러수 곱이 n! 이상임을 조합적으로 증명하고 이를 통해 2*황금비가 원주율보다 큼을 증명함 ㅋㅋㅋ

— 유닼 (@udaqueness) April 1, 2018

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.