베르트랑 공준

수론에서, **베르트랑 공준**(), **베르트랑-체비쇼프 정리**(), 혹은 **베르트랑 가설**은 소수들의 분포에 관한 정리다. 이에 따르면, 두 자연수 n과 2n 사이에 적어도 하나의 소수가 존재한다.

## 정의
**베르트랑 공준**은 다음과 같다. 임의의 정수 n\ge2에 대하여,
:n
인 소수 p가 항상 존재한다.

## 증명
여러 가지 증명이 있으며, 다음은 대표적인 셋이다. 이 가운데 에르되시 팔의 증명은 해석학을 거의 사용하지 않는다는 데서 초등적이다.

### 체비쇼프의 증명의 개요
\pi(x)가 소수 계량 함수라고 하자. 그렇다면 베르트랑 공준은 다음과 같은 명제와 동치이다.
:\pi(2x)-\pi(x)>0\qquad\forall x\ge1
파프누티 체비쇼프는 다음을 만족시키는 양의 실수 a,b,x_0>0를 찾았다.
:a\frac x{\ln x}\le\pi(x)\le b\frac x{\ln x}\qquad\forall x\ge x_0
:b
(이는 소수 정리보다 약한 결과이지만, 증명은 여전히 복잡하다.) 이 경우, 임의의 x\ge x_0에 대하여
:\pi(2x)-\pi(x)\ge a\frac{2x}{\ln(2x)}-b\frac x{\ln x}\ge(2a-b)\frac x{\ln x}>0
이다. x인 경우는 직접 확인한다.

### 라마누잔의 증명
스리니바사 라마누잔의 증명은 감마 함수와 그 스털링 근사를 사용하며, 체비쇼프의 증명보다 단순하다. (괄호 속은 라마누잔이 생략한 내용이다.) 체비쇼프 함수
:\vartheta(x)=\sum_{p\le x}\ln p
:\psi(x)=\sum_{p^k\le x}\ln p
를 생각하자. 다음을 보이면 족하다.
:\theta(x)-\theta(x/2)\qquad\forall x\ge2

다음과 같은 항등식이 성립한다. (체비쇼프 함수 참고.)
:\psi(x)=\vartheta(x)+\vartheta(x^{1/2})+\vartheta(x^{1/3})+\cdots
:\ln\lfloor x\rfloor!=\psi(x)+\psi(x/2)+\psi(x/3)+\cdots
이에 따라
:\psi(x)-2\psi(x^{1/2})=\vartheta(x)-\vartheta(x^{1/2})+\vartheta(x^{1/3})-\cdots
:\ln\lfloor x\rfloor!-2\ln\lfloor x/2\rfloor!=\psi(x)-\psi(x/2)+\psi(x/3)-\cdots
이다. 그런데 두 체비쇼프 함수 모두 비감소 함수이므로, 특히
:\psi(x)-2\psi(x^{1/2})\le\vartheta(x)\le\psi(x)
:\psi(x)-\psi(x/2)\le\ln\lfloor x\rfloor!-2\ln\lfloor x/2\rfloor!\le\psi(x)-\psi(x/2)+\psi(x/3)
가 성립한다.

이제, 감마 함수의 로그 볼록성에 따라
:\ln\Gamma(x)-2\ln\Gamma((x+1)/2)\le\ln\lfloor x\rfloor!-2\ln\lfloor x/2\rfloor!\le\ln\Gamma(x+1)-2\ln\Gamma((x+1)/2)
이다. (증명: 두 부등식의 증명은 유사하므로 두 번째 부등식만을 증명한다. 이를 다음과 같이 다시 쓰자.
:2(\ln\Gamma((x+1)/2)-\ln\Gamma(\lfloor x/2\rfloor+1))\le\ln\Gamma(x+1)-\ln\Gamma(\lfloor x\rfloor+1)
만약 x/2-\lfloor x/2\rfloor\le1/2라면, 좌변은 0보다 작고 우변은 0보다 크므로 위 부등식은 참이다. 만약 x/2-\lfloor x/2\rfloor>1/2라면, x+1와 \lfloor x\rfloor+1의 차는 정확히 (x+1)/2와 \lfloor x/2\rfloor+1의 차의 2배이므로, 위 부등식은 단순히 \ln\Gamma(t)의 볼록성이다.)

이제, 감마 함수에 대한 스털링 근사
:\ln\Gamma(x)=x\ln x-x+\frac12\ln\frac{2\pi}x+r(x)
:|r(x)|\le\frac{1}{12x}
를 사용하면 위 부등식으로부터
:\ln\lfloor x\rfloor!-2\ln\lfloor x/2\rfloor!0
:\ln\lfloor x\rfloor!-2\ln\lfloor x/2\rfloor!>\frac23x\qquad\forall x>300
을 얻는다. (증명: 둘의 증명은 유사하므로 첫 번째만 증명한다. 위 스털링 근사에 따라
:\begin{align}
\ln\Gamma(x+1) & -2\ln\Gamma((x+1)/2)-3x/4 \\
& =(x+1)\ln(x+1)-(x+1)+\frac12\ln\frac{2\pi}{x+1}+r(x+1) \\
& \phantom{=}{}-2\left(\frac{x+1}2\ln\frac{x+1}2-\frac{x+1}2+\frac12\ln\frac{4\pi}{x+1}+r\left(\frac{x+1}2\right)\right) \\
& =\left(\ln2-\frac34\right)x-\frac12\ln\frac{2\pi}{x+1}+r(x+1)-2r\left(\frac{x+1}2\right) \\
& 
이다. 마지막 식을 f(x)라고 하자. 그렇다면
:f'(x)=-\frac{43}{768}+\frac1{2(x+1)}-\frac5{12(x+1)^2}
는 0일 때 0보다 크고 x>7일 때 0보다 작다. 따라서
:f(x)\le f(7)=-0.2\cdots0
이다.)

위 부등식들에 따라
:\psi(x)-\psi(x/2)0
:\psi(x)-\psi(x/2)+\psi(x/3)>\frac23x\qquad\forall x>300
이다. 첫 번째 부등식의 x를 x,x/2,x/4,x/8,\dots로 대체하여 모두 합하면
:\psi(x)0
를 얻는다. (x/2^n인 경우 \psi(x/2^n)=0이다.)

끝으로, 위 부등식들로부터 다음을 얻는다.
:\begin{align}
\vartheta(x)-\vartheta(x/2) & \ge\psi(x)-2\psi(x^{1/2})-\psi(x/2) \\
& >2x/3-\psi(x/3)-2\psi(x^{1/2}) \\
& >x/6-3x^{1/2} \\
& \ge0\qquad\forall x\ge324
\end{align}

2\le x인 경우는 직접 확인한다. (소수로 이루어진 열 2, 3, 5, 7, 11, 17, 31, 59, 107, 211, 401의 각 소수는 이전 소수의 2배보다 작다. 따라서 위 부등식은 2\le x\le401인 경우에도 참이며, 특히 2\le x인 경우 참이다. 이를 **란다우 계략**()이라고 한다.)

### 에르되시의 증명
에르되시의 증명은 중심 이항 계수의 초등적인 성질을 사용한다. 먼저 몇 가지 준비가 필요하다.

중심 이항 계수
:\binom{2n}n=\frac{(2n)!}{(n!)^2}
를 생각하자. 그렇다면, 임의의 정수 n\ge1에 대하여,
:\binom{2n}n\ge\frac{4^n}{2n}
이다. 왜냐하면
:2n\binom{2n}n\ge2+\sum_{i=1}^{2n-1}\binom{2n}i=(1+1)^{2n}=4^n
이다.

임의의 정수 n\ge1와 소수 p에 대하여, p^a\mid n!인 최대의 정수 a는
:a=\sum_{i=1}^\infty\lfloor n/p^i\rfloor
이다. (계승 (수학) 참고.)

임의의 정수 n\ge3와 소수 2n/3에 대하여,
:p\nmid\binom{2n}n
이다. 왜냐하면, 이 경우 p^a\mid(2n)!인 최대의 정수 a는 2이며, p^a\mid n!인 최대의 정수 a는 1이다.

임의의 정수 n\ge1와 소수 p와
:p^a\mid\binom{2n}n
인 최대의 정수 a에 대하여,
:p^a\le2n
이다. 왜냐하면, a'이 p^{a'}\le2n인 정수라고 하였을 때
:\begin{align}
a & =\sum_{i=1}^\infty\lfloor2n/p^i\rfloor-2\sum_{i=1}^\infty\lfloor n/p^i\rfloor \\
& =\sum_{i=1}^{a'}\lfloor2n/p^i\rfloor-2\sum_{i=1}^{a'}\lfloor n/p^i\rfloor \\
& =\sum_{i=1}^{a'}(\lfloor2n/p^i\rfloor-2\lfloor n/p^i\rfloor) \\
& \le a'
\end{align}
이다.

임의의 정수 n\ge2에 대하여,
:\prod_{p\le n}p\le 4^n
이다. 수학적 귀납법을 사용하여, n 미만인 정수에 대하여 위 부등식이 참이라고 가정하자. 만약 n이 짝수라면,
:\prod_{p\le n}p=\prod_{p\le n-1}p\le4^{n-1}\le4^n
이다. 만약 n=2k+1이 홀수라면,
:\begin{align}
\prod_{p\le n}p & =\prod_{p\le k+1}p\cdot\prod_{k+2\le p\le 2k+1}p \\
& \le4^{k+1}\binom{2k+1}k \\
& \le4^{k+1}4^k \\
& =4^n
\end{align}
이다. 위 식에서,
:\prod_{k+2\le p\le 2k+1}p\le\binom{2k+1}k
는 임의의 소수 k+2\le p\le 2k+1에 대하여
:p\mid\binom{2k+1}k
이기 때문이며,
:\binom{2k+1}k\le4^k
는
:2\binom{2k+1}k=\binom{2k+1}k+\binom{2k+1}{k+1}\le\sum_{i=0}^{2k+1}\binom{2k+1}i=2^{2k+1}
때문이다.

이제 베르트랑 공준을 증명하자. 귀류법을 사용하여, n\ge3가 정수이며, n인 소수 p가 존재하지 않는다고 가정하자. 그렇다면, 중심 이항 계수
:\binom{2n}n
의 모든 소인수는 2n/3이하이며, 이 가운데 \sqrt{2n}보다 큰 것들의 지수는 1이다. 따라서,
:\begin{align}
\binom{2n}n & \le(2n)^{\sqrt{2n}-1}\prod_{\sqrt{2n}
이다. 따라서, 부등식
:\frac{4^n}{2n}\le(2n)^{\sqrt{2n}-1}4^{2n/3}
이 성립한다. 이는 부등식
:\sqrt{2n}\ln2-3\ln(2n)\le0
과 동치이다.
:f(x)=x\ln2-6\ln x\qquad\forall x>0
라고 하자. 그렇다면
:f'(x)=\ln2-\frac6x>0\qquad\forall x\ge30
이므로,
:f(x)\ge f(30)=0.3\cdots>0\qquad\forall x\ge30
이다. 즉, n이다. 그런데 소수의 열 2, 3, 5, 7, 13, 23, 43, 83, 163, 317, 631 속의 각 소수는 이전 소수의 2배보다 작으므로, n인 경우 항상 n인 소수 p가 존재한다. (이를 **란다우 계략**()이라고 한다.) 이는 모순이다. 즉, 베르트랑 공준은 참이다.

## 역사
프랑스의 수학자 조제프 베르트랑()이 1845년에 처음으로 추측하여 **베르트랑 추측**이라는 이름을 얻었다. 베르트랑이 처음으로 이 명제에 대한 추측을 내놓았을 때 그는 3백만보다 작은 모든 자연수에 대한 계산을 덧붙였으나 증명은 하지 못했다.

5년 뒤 1850년에 파프누티 체비쇼프가 이 명제를 완전하게 증명하였다. 그럼에도 불구하고 관례적으로 '베르트랑 공준'이라 불린다. 1919년에 스리니바사 라마누잔이 감마 함수를 사용하여 더 간단한 증명을 발표하였고, 1932년에 에르되시 팔은 이항계수와 체비쇼프 함수를 사용한, 라마누잔 증명보다 더 간단한 증명을 발표하였다.

## 확장된 결과들
* 영국의 수학자 제임스 조지프 실베스터는 k개의 연속된 k보다 큰 정수들의 곱은 적어도 하나의 k보다 큰 소수로 나누어떨어진다는 명제를 증명했다. 이를 실베스터 정리라고 한다.
* 1934년에 헝가리의 수학자 에르되시 팔은 임의의 자연수 k에 대하여, 적당한 자연수 N이 존재하여 N보다 큰 임의의 자연수 n과 2n 사이에는 적어도 k개의 소수가 존재한다는 명제를 증명했다. 이를 에르되시 정리라고 한다.
* 1952년에 일본의 수학자 나구라 지쓰로는 24보다 큰 모든 자연수 n에 대하여 n과 \frac{6}{5}n 사이에는 적어도 하나의 소수가 존재한다는 명제를 증명했다.
* 1998년에 프랑스의 수학자 피에르 뒤자르(Pierre Dusart)는 2010760보다 큰 모든 자연수 n에 대하여 n과 \frac{16598}{16597}n 사이에 적어도 하나의 소수가 존재한다는 명제를 증명했다.

## 참고 문헌

* 

## 외부 링크
* 
* 

## 같이 보기
* 소수 간극

분류:소수에 관한 정리
분류:대수학 정리