$\pi$ is irrational, due to Bourbaki.

 This proof uses the characterization of $\pi$ as the smallest positive zero of the sine function.

First of all, assume that $\pi$ is rational, i.e., $\pi=\frac{a}{b}$ for some integers $a$ and $b$, $b$ nonzero. Set $$ f(x)=\frac{x^{n}(a-bx)^{n}}{n!} $$ for $x\in \mathbb{R}$ and $$ A_{n}=\int_{0}^{\pi}f(x)\sin xdx=b^{n}\int_{0}^{\pi}\frac{x^{n}(\pi-x)^{n}}{n!}\sin xdx. $$

 The steps are given below.

Claim 1. $A_{n}$ is a positive integer.

Claim 2. $A_{n}$ converges to 0 as $n \to \infty$.

Claim 3. Therefore, it is absurd if $\pi$ is rational.

Fill the details, and complete the proof.

 You may consider for the first step that $$ A_{n}=\int_{0}^{\pi}f(x)\sin xdx=[-f(x)\cos (x)]_{0}^{\pi}-[-f^{(1)}(x)\sin (x)]_{0}^{\pi}+\cdots \pm [f^{(2n)}(x)\cos (x)]_{0}^{\pi} \pm \int_{0}^{\pi}f^{(2n+1)}(x)\cos xdx $$ and $f(x)$ is expanded with integral coefficients over $n!$. For the second step, use the inequality $$ x^{n}(\pi -x)^{n}\leq (\frac{\pi}{2})^{n}$$ for $x\in [0,\pi].$

너무 할게 없어서 Lovasz 다시 붙잡고 몇문제 풀어봤는데 괜찮은 문제가 있어서 공유 차원에 올린다. 사실 풀이까지 쓰려했는데 솔직히 쓰려니 너무 많네...

나는 푸는데 한참 걸렸다.

Lemma. Suppose that G is 2-connected. Let T_1, T_2 be two spanning trees of a connected graph G. Then to obtain T_1 from T_2 it suffices repeatedly to apply the following transformation: we remove the edge adjacent to some endpoint x of the tree and connect x to the rest by some other edge of G.

Problem.

(a) Let G be a 2-connected graph on n points and n_1+n_2=n. Then V(G) has a partition {A_1,A_2} such that #A_i=n_i and each A_i induces connected subgraph.

(b) Let G be a 2-connected non-bipartite graph on 2m points. Then V(G) has a partition {A_1,A_2} such that #A_i=m and (A_1,A_2) edges form a connected spanning subgraph.

개인적으로 이 중에서 problem (a)가 가장 무난하다. 힌트로는 lemma 풀 땐 backward induction, problem (b)를 풀 땐 non-bipartite의 동치조건을 먼저 생각하길... 그리고 lemma에서 최대한 많은 것을 얻어내야 한다. 저 lemma의 statement 자체만 쓰이는 것이 아니다.

(A. Bondy,-L. Lovasz)

얼마 전에 연습문제 중 하나로 이 정리의 또 다른 증명을 봤는데 너무 깔끔해서 혹시나 했더니 이게 von Neumann의 증명이란다.

(Radon-Nikodym) Let be a measurable space, let be a -finite positive measure on , and let be a finite signed or complex measure on . If is absolutely continuous with respect to , then there is a function or such that for each A in . The function g is unique up to -almost everywhere equality.

(proof due to von Neumann)

사실상 와 가 finite positive measure일 때만 보이면 충분하다. 유일성도 어렵지 않으니 가장 핵심 부분의 증명을 보자.

 

에서 g는 서로 다른 measure의 integral을 잘 저울질해주는데 모든 f에 대해서 성립해야 하니 g는 0이상 1이하일거란 느낌이 든다.

식을 정리하면

이 되는데 만약 가 -null set이 아니면 큰일난다. f는 characteristic function of A로 놓고 로 표현하면 망함이 눈에 보인다.

가 -null set임은 더 분명하게 보인다.

이제 저 위의 식에 를 대입하고 싶지만 분모가 0가 될 수도 있다. 그렇지 않음을 보이기 위해 , 을 에 대입하면 , 따라서 이 된다. 여기서 absolute continuity조건이 쓰였다. 그래야 안심하고 양변에 를 대입할 수 있다. 계획대로 대입하면 최종을 얻는다.

얼마 전에 Sperner`s lemma를 쓴 일이 있어서 proof from the book에 있던 lemma의 응용이 생각났다. 처음 읽었을 때도 포스팅 감으로 괜찮겠다고 생각했고, 이제 쓰게 되었다.

Sperner`s lemma.

큰 삼각형 가 triangulate되었다고 하자. 각각의 작은 삼각형의 각 꼭지점에 세 가지 색 1, 2, 3으로 칠하자. 그리고 꼭지점 를 순서대로 i로 칠했다. 그리고 변 에는 색이 i와 j밖에 없다.

그러면 반드시 색 123을 모두 가지고 있는 작은 삼각형이 존재한다.

증명은 간단하다(물론 읽는 사람 입장에서... 다음의 아이디어를 떠올리려면 약간의 감이 필요할 듯). dual graph의 subgraph를 생각하는데 edge를 줄때 본래의 graph G의 edge의 양 꼭지점의 색이 다르면 dual graph에 edge를 준다. 자 그럼 이제 이 새로 생성된 그래프에서 exterior face에 해당하는 꼭지점은 각 대변 마다 홀수개의 edge로 연결되어있다(V_1에서 V_2로 갈때 색이 1에서 1,2를 교대하다가 결국 2로 바뀌니...). degree가 홀수인 꼭지점은 반드시 짝수개 있어야 하니 본래의 삼각형 안에 odd degree vertex가 하나 이상 무조건 더 있다. 얘가 바로 그놈이다. 삼각형 세 꼭지점의 각 coloring case마다 나올 수 있는 변의 수는 0, 2, 3뿐이다.

Sperner는 Brower fixed point theorem(n=2)을 증명했다. 이 theorem은 커피잔을 숟가락으로 휘저을 때에도 각 연속변환에는 무조건 고정점이 있다는 것이다.

Brower fixed point theorem(n=2).

모든 연속함수 는 고정점을 가진다.

증명.

일단 아니라고 하자. closed unit ball B^2대신 (1,0,0), (0,1,0), (0,0,1)을 꼭지점으로 하는 정삼각형 에 대해서 증명하자(저 고정점 성질은 topological property이다. 사실 이 모든게 당연하지 않다. 보면 공간의 성질을 얘기하기 위해 open set의 모임을 생각한다는 것부터가 참 신기하다. 그리고 저 고정점 성질은 공간의 특성이다.). 어떤 주어진 triangulation T에 대해 를 T의 edge의 길이 중 최대값이라고 하자. 라 하고 T_(k+1)을 T_k의 barycentric division이라고 하자. 그러면 이 infinite sequence의 델타값은 0으로 수렴한다.

각 triangulation의 꼭지점 v에 대해서 coloring \lambda를 라 하자. 여기서 i첨자는 i번째 좌표를 말한다. 항상 저 i 집합은 nonempty이다. 이제 각 triangulation T_k는 큰 삼각형을 로 해서 Sperner lemma의 가정을 만족시킨다. 따라서 각 T_k 마다 를 만족시키는 삼각형 가 있다.

수열 는 반드시 수렴할 필요는 없지만, 큰 삼각형 는 compact하므로 어차피 수렴하는 subsequence를 가질 것이다. 그러므로 그냥 저 v^(k:1)가 로 수렴한다고 해도 되겠다. 그러면 v^(k:2), v^(k:3)도 v로 수렴해야 한다(저 델타라는 큰 삼각형은 complete하다).

이제 f(v)는 무엇일까. 우선 각 모든 k에 대해 가 음수이다. 연속함수는 limit을 보존하므로 는 양이 아니다. 이 것이 모든 i=1,2,3에 대해서 참이다. 이므로 f(v)=v이어야 한다. 모순! 

참... 이런 증명이 어떻게 나온거지...

lemma는 유한에 관한 것인데 theorem은 무한에 관한 것이다. 유한에 극한을 취했다. 초기치가 정해져 있고 recursive algorithm이 있으면 그에 맞는 infinite set 그 자체가 있다는 것이다. 요게 Brower가 의심한 건가? 이 쪽은 잘 모르겠다.

생각해보면 이 우주에 무한한 양은 뭐가 있을까. 깊게 생각해보진 않았지만 딱 생각나는 것은 없다. 양자역학은 선도 분해해버린다. 무한은 우주를 잘 근사하면서도 매력적이고, 또 그만큼 논란이 많고 역사가 깊다. 종교는 유한과 무한이 인간과 신의 경계라고 하기도 하며, 누군가는 인간은 무한을 상상할 수 있으므로 인간의 능력은 무한하다고 주장했다(그 당시엔 받아들여지지 않았다). 어떤 스승과 제자에게는 그 사이에 해소되지 않는 갈등을 주었다. 하지만 후에 Hilbert는 "그 누구도 칸토어가 창조한 낙원에서 우리를 추방할 수 없다"는 명언을 남겼다. 괴델 이후로 절대 진리에 대한 믿음이 약해진 것은 사실이다. 현대 대부분의 수학자들도 ZFC 공리계에 크게 신경을 쓰지 않고 받아들인다(나도 그렇다. 상상하고 이해할 수 있으니까. 근데 ㅇㅅㄴ은 다른 생각을 가지고 있고, 이에 대해서 대화하는 동안 즐거웠다. 재밌는 친구다.). 하지만 여전히 한편에서는 끊임없이 토론이 벌어지고 있다.

이번에 열리는 과목 중에 Discrete and Computational Topology라고 열리는데 아마 저런 논의하고 관련있나 생각해본다. 재밌겠다.

출처는 우리 학교 문제.

방에 100개의 상자가 있다고 하자. 각 상자는 이름 하나씩 가지고 있고 이름은 모두 다르다. 100명의 사람들은 일련의 순서대로 한명한명 방 안으로 들어갔다가 나온다. 들어가면 100개의 상자 중 50개를 열어볼 수 있다. 이때 게임 시작. 100명의 사람들이 살아남으려면 모든 사람들 각각이 50개를 열었을 때 자기 이름을 찾아야 한다. 무작위로 50개씩 열면 성공할 확률이 2의 100승 분의 1이지만, 그들에게는 게임 전에 작전회의 시간이 있고, 시작되고 난 후에는 서로 얘기할 수 없다. 승률이 1/4이 넘는 전략을 찾을 수 있을까?

일단 힌트를 주자면 답은 Yes인데, 2의 100승분의 1에서 1/4까지 올릴 수 있다는게 참 놀랍다.

A family F of a set이 을 만족시키면 F는 intersecting 또는 intersecting family라 부른다. n>=2k, F는 a family of k-subsets of 라 하자. Erdos-Ko-Rado theorem은 F가 intersecting family이면 라는 것이다. 등호의 경우는 한 점을 항상 들어가게 하고 남은 n-1 멤버중에서 k-1개 골라주면 된다.

G. Katona의 확률론적 증명을 소개할 것이고(매우 짧지만, 다른 증명들이 길다는 걸 생각하면 강력...), 모두 Alon, Spencer의 The Probablistic Method에 잇다.

Lemma.

이라 하면, F는 기껏 해봐야 k개의 A_s를 가지고 잇다. 어떤 l에 대해, 라 해보자. 그럼 A_s들 중에서 A_l이랑 intersect하는 것은 2k-2개가 잇는데(A_l 빼고) 이들은 k-1개의 nonintersecting pair로 정리할 수 잇다(평행이동하면서). 그렇다면 F는 저 각각의 k-1개의 pair에서 기껏 해봐야 하나밖에 못 가진다.

Erdos-Ko-Rado theorem을 증명해보자. n-set 의 permutation 와 가 uniformly, independently, randomly 골라진다고 하자. 라 하면, lemma에 의해 각각의 sigma에 대해 A가 F에 속할 확률이 k/n을 넘지 못한다(n-set은 아무리 섞어봐야 n-set이다). 따라서

A는 모든 k-subset을 uniform하게 취하므로,

저번에도 비슷한 주제로 하나 썻지만 estimation이 이루어지는걸 보면 논리가 참 간드러진다. Tricky하고 센스터지는 수학자들의 테크닉은 우리를 즐겁게 한다. 딱 처음보면 이런 보조함수를 왜 잡앗는지 감이 안 오기도 한다. 하지만 곰곰히 두고 보면 분명 이렇게 잡는데는 이유가 잇다.(글쎄 이런건 어떤 근본적인 걸 이해해서라기보단, 그냥 계산에 능한 직관 비슷한...) 문제는 아니 어떻게 이런 것들이 성립하는지 알수 잇는가 이거지. 증명됏으면 하는, 또는 원하는 형태의 proposition을 자주 써놓고 계속 증명되기를 고대하며 뚫어나가는 것인가?(신이 참/거짓을 말해준다면 그것만큼 큰 힌트도 없겟지) 현장에 잇으면 조금은 알수도 잇지 않을까? 어린 학생으로서 궁금할 뿐이다.

이만 각설하고 본론으로 들어가자. Maximum modulus principle은 정의역이 bounded region일 때만 쓸 수 잇는데, unbounded인 경우는 쓸 수가 없다. 그 예로 , 라고 바운더리에서 이지만 얘는 실수축에서 아주 빠르게 발산한다.

빠르게 발산하는 애가 쟤라면, '느리게' 발산하는 애는 어떨까. '느리게'라는 말은 다음과 같은 상황을 이를 수도 잇다. f가 entire고 라면 Cauchy estimate에 의해 f는 상수일 수 밖에 없다. 이는 루트 z가 느리게 발산하기 때문이다.

Phragmen, Lindelof는 첫째로, 우선 f가 bounded면 그 bound condition을 improve할 수 잇다는 것이고 둘째로, f가 느리게 발산하는 함수에 의해 bound되면 f는 bounded라는 것이다. 개인적으로 maximum modulus principle을 이용한 논리가 elegant하다고 느낀다.

Theorem 1.

라 하고 f가 omega의 closure에서 연속, omega에서 holomorphic, |f(z)| for 라 하자. 그럼 다음이 성립한다.

두번째로, log M(x)가 convex function이라는 것이다.

pf.

만약 어떤 strip에 대해서 M값이 0면 그 함수는 0다. 만일 바운더리 M(a) 또는 M(b)가 0면 Schwartz reflection을 쓸 수 잇겟다. 그러니 M값 중에서 0는 없다고 하자. 그리고 strip의 M값을 잘 보존시키는 함수 로 normalize 해볼수 잇겟으니, M(a)=M(b)=1일 경우에 증명하자. 라 두면 이므로 , omega의 boundary에서 이다. 또한 이므로, 전체집합 에서 이다. 우변이 y가 커질때 0으로 수렴함을 확인하고, R을 에서 로 잘라낸 rectangle이라 하면, maximum modulus principle에 의해서 R 상에서. 따라서, for all z in the closure of Omega and for all epsilon. epsilon이 임의의 양수이므로,각각의 z에 대해서 epsilon을 0으로 보내면 |f(z)|<=1을 얻는다. 일반적인 경우는, 위에서 말햇던 것처럼, f/g를 고려하면 된다.(f/g의 M(a), M(b)는 1이다.) =

Theorem 2.

, f가 omega의 closure에서 연속, omega에서 holomorphic이라 하자. z=x+iy, 1보다 작은 alpha에 대해 이고 Omega의 바운더리에서 이라 하자. 그럼 전체 Omega에서도 라는게 thm이다.

alpha가 1보다 작다는게 crucial. alpha=1이면 f(z)=e^(e^z)로 반례가 잇다.

pf.

인 beta를 하나 fix하고, 양수 epsilon에 대해 라 하자.   

이므로 .

(저기서 cos값이 양수.)

따라서, 이제 x를 플러스마이너스 infinity로 보내면 저 지수부분이 -infinity로 간다. as . 이제는 다시 thm1과 같은 논리로 마무리하면 되겟다.

저 논리를 알고 잇다면 보조함수만 잡아도 거의 끝나는 증명.

좋은 exercise 두개를 소개할테니 관심잇는 사람은 함 생각해보시길...

(1) , , for some constants A, alpha라 하자. alpha가 1보다 작다고 하자. 라 하자.

그러면 open right plane Pi 전체에서도 이다. (alpha가 1일때는 거짓임을 확인하자)

Pi가 region bounded by two rays through the origin, at an angle not equal to 일때는 어떤가.

(2) 다시 라 하자.

Pi 전체에서 이고 인 alpha에 대해 r이 무한대로 갈때

Mittag-Leffler thm과 Weierstrauss thm은 zero or pole이 임의로 취해질 수 잇다는(물론 limit point 제외) 긍정적 결과를 내놓는다. 그러나 zero의 분포는 해당함수의 growth rate에 영향을 주기 때문에 우리가 growth rate마저 임의로 선택할 수 없다. essence는 Jensen`s formula로부터 온다.

떡밥 하나.

f가 open disc D(0:R)에서 holomorphic하고 f(0)가 nonzero, r을 0보다 크고 R보다 작은 어떤 수라 하자. 에 잇는 f의 zero를 중복도를 다 카운팅해서 라 하자. 그러면 다음이 성립한다.

 

증명은 보조함수 하나 잡아서 거의 한방에 끝낸다.

  까지는 크기가 r보다 작고 는 크기가 r이라 하자.

라 하면, 얘는 에서 holomorphic라고 zero가 없다. 따라서, D는 simply connected이므로 는 D에서 harmonic이다. mean value property를 쓰기 전에 저 g를 왜 저리 잡앗는지 생각해보자. 사실, 에서 자기자신으로 가는 대표적인 conformal mapping을 알고잇으면(알파가 1보다 작을때, . 그리고 얘는 boundary를 보존한다.) 그 이유를 어렵지 않게 알수 잇다. 지금 open disc D(0;r)에서 놀고잇으니 1/r배로 줄여주는 함수와 합성하면 저 중간 이상하게 생긴 factor의 역수가 나온다.(왜 역수를 취해줫는고 하니 당연히 zero를 다 remove하려고...)

 

f가 entire function, n(r)을 크기가 r이하의 zeros of f의 개수, 라 놓고서 가시적인 estimation을 해보자. (편의상 f(0)=1이라 하겟다)

 

위 부등식을 다시 쓰면,

그니까 f가 근을 많이 가지면 f는 좀더 '출렁이는' 놈이다. 가령 f가 충분히 큰 z에 대해로 bound되면 다시 log을 취함으로써 다음을 얻는다

 

예를 들어, 로 잡으면 저 등호가 딱 성립한다.)

f가 entire하고,  (n=1,2,3,...), 충분히 큰 z에 대해서, 라 해보자.

을 대입하면 alpha는 2 이상이어야 하고, 는 alpha가 2보다 클 경우에 저 가정을 모두 만족시킨다. alpha가 2인 경우엔 어떨까.

Theorem. 각 1보다 같거나 큰 자연수 n에 대하여, n보다 크고 2n보다 같거나 작은 소수 p가 존재한다.

Chebyshev가 1850년에 처음으로 증명하고(이게 아마 어떤 이론의 부산물로 나왓다는걸로 기억하는데 맞으려나) 후에 라마누잔에 의해 훨씬 간단히 증명되엇다고 한다. 그리고 Erdos가 19살에 '쉬운 방법으로' 증명하고(이것도 아마 Erdos가 처음으로 낸 논문이엇나? 기억이 잘 안나네) 이름을 알리기 시작한다.

여기서 소개할 증명이 Erdos의 증명이다. 고전이지만 충분히 감탄할 만하여 포스팅한다.

Proof.

(1)

증명. 먼가 x가 홀수일때만 관찰해도 된다. x=2m+1라 하자. 2m이하일때는 다 성립한다고 가정하자.

 

디테일은 어렵지 않다.

(2)

 

은 p factor를 정확히 가지고 잇고 다시 각 summand는 이므로 저 summand들은 0 또는 1이다. 얘네들이 p^k>2n일때는 다 죽어버리는것을 보면 결국 전체 summation은 을 넘지 못한다. 따라서 의 소인수분해에서, 가장 큰 prime power도 2n을 넘지 못하고, 특히 은 factoring중 등장해봐야 최대 한번이다.

더 나아가서, 인 p는 을 전혀 나누지 못한다 (증명한 본인 Erdos에 따르면 요게 key라고 한다). 왜냐하면, 3p가 2n보다 크다는 것은 (2n)!의 factor중 오직 p와 2p만이 p의 배수임을 말하는데, 분모에 잇는 n! 두 놈은 p를 각 한번씩 가지기 때문에 결국엔 다 소거된다.(n이 2보다 크면 p는 2일 수 없다.)

(3) 따라서 다음을 얻는다.

다시 쓰면,

 

이제 여기서, 어떤 n에 대하여 n과 2n사이의 prime p가 없다고 가정해보자! (1)에 의해서,

또는

 

양변에 log씌워서 n을 크게하면 좌변이 더 커짐을 알수 잇다. 따라서 충분히 큰 n에 대해서 Bertrand postulate는 참이다. 위에 저 key part라 해서 3분의 2가 나오는 부분은 부등식 좌변 지수부분이 n/3까지 클 수 잇음을 이끌어내기 위함이엇던것 같다. 

작은 n에 대해서도 확인하기 위해, 저 부등식의 경계값을 확인하고 그 유한한 경계값까지 실험적으로 증명한다. log씌운 상태에서 4000을 대입하면 좌변은 1500이 넘고 우변을 1000을 넘지 못한다. 머 여기서부터는 누구나, 모든 4000이상의 n에 대해서 저 부등식이 성립할 수 없음을 증명할 수 잇다. 책에서는(또는, Erdos에 따르면?) 그냥 어찌어찌 estimate햇는데 중요한 부분도 아니거니와 수식편집이 귀찮으므로 생략한다.

이제 다음 4000보다 작은 n에 대하여 postulate가 참임은 다음 prime을 늘어놓음으로써 확인한다.

2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631, 1259, 2503, 4001

규칙이야 머, 이전 항을 2배 해놓고는 그 미만 중 최대의 소수를 고른 것으로 보인다.

증명 끝.

Hilbert가 평생동안 theorem을 100개 넘게 만들엇다는데 그 중에서 90번째다.

물론 그 정리들 다 본게 아니고 이 정리가 cyclic extension을 푸는데 도움이 되기 때문에 Hungerford 책에 잇엇고 단지 그걸 공부한 것이다.

Thm. 

F/K를 cyclic extension of finite degree n이라 하고 Galois group이 로 generated 된다고 하자. 그럼 다음이 성립한다.

(1) for some v in F.

(2) for some v in F.

증명.

먼저 저런 v가 잇으면 trace나 norm이나 저리 된다는 건 자명하다. T(u)=0라 해보자. 우선 T(w)=1을 만족하는 w가 F에 존재한다(은 linearly independent over F. trace가 nonzero가 되게 하는 원소 아무거나 잡은 후에 scaling). 이제 라 하고(...!) 를 계산하면 u를 얻는다.

N(u)=1라 해보자. 가 nonzero가 되게 하는 y가 잇고 계산으로 을 얻는다.

참... 증명을 보면서 나도 저런 센스를 가졋으면 얼마나 좋을까 하고 생각한다. 물론아이디어가 정말 노력의 결과일수도 잇다. 내가 한시간 두시간 고민해서 내놓은 솔루션이 남들이 정말 tricky하다고 몇번 들은적이 잇다. 하지만, 알고나서 그런것일수도 잇지만, 센스가 좀만 더 좋으면 시간이 오래 걸리지 않고도 생각해볼수 잇는 솔루션이엇다. 좀 tricky한 것들을 잘 하고 싶고 다양한 아이디어를 내놓고 싶다.

주절주절은 그만하고 이 thm의 간단한 응용을 보자.

의 유리수해를 찾을 것이다. (D는 square-free)

F/K를 f라 하자. 이라 setting하고 Hilbert thm 90을 이용하면,

을 얻는다. D가 1이면 (x,y)는 피타고라스 솔루션.