Bertrand postulate

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

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

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

Proof.

(1)

for all real x>=2.

증명. 먼가 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배 해놓고는 그 미만 중 최대의 소수를 고른 것으로 보인다.

증명 끝.