onul.works
오늘의 업무 도구로 이동

소수 계량 함수

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

소수 계량 함수는 주어진 값보다 작거나 같은 소수의 개수를 세는 함수로, 정수론에서 소수의 분포를 연구하는 데 중요한 역할을 한다. 18세기 말 가우스와 르장드르는 소수 계량 함수 π(x)가 x/ln(x)에 근접한다고 추측했으며, 1896년 소수 정리가 증명되었다. 이 함수는 리만 가설과 밀접한 관련이 있으며, 리만 가설이 참일 경우 소수의 분포에 대한 오차 범위를 더욱 좁힐 수 있다. 소수 계량 함수는 폰 망골트 명시적 공식과 같은 다양한 공식을 통해 표현되며, 에라토스테네스의 체, 르장드르의 방법, 메이즐의 방법 등을 사용하여 계산할 수 있다. 또한, 라마누잔, 뒤사르, 액슬러 등에 의해 다양한 부등식이 제시되어 소수 계량 함수의 범위를 제한하고 있다. 리만의 소수 거듭제곱 계량 함수, 체비쇼프 함수 등과 같은 다른 소수 계량 함수들도 존재한다.

소수 계량 함수
일반 정보
함수 종류수론적 함수
기호π(x)
정의π(x)는 x보다 작거나 같은 소수의 개수를 나타내는 함수
정의역실수
공역자연수
발견자아드리앵마리 르장드르
상세 정보
성질π(1) = 0
π(10) = 4 (2, 3, 5, 7)
점근적 성질소수 정리에 의해 x가 무한대로 갈 때 π(x) ~ x / ln(x)
리만 함수와의 관계리만 제타 함수와 밀접한 관련을 가짐
활용소수의 분포를 연구하고, 암호학 등 다양한 분야에서 활용
관련 항목
관련 항목소수
소수 정리
리만 제타 함수
수론
📚 더 읽어볼만한 페이지
  • 해석적 수론 - 타원곡선
    타원곡선은 체 위에서 정의되고 특이점이 없으며 종수가 1인 사영 대수 곡선으로, 유리점을 가지며, 특정 형태의 방정식으로 표현되고, 실수체 위에서는 연결 성분 개수가 판별식에 따라 달라지며, 복소수체 위에서는 원환면과 위상적으로 동형이고, 점들 간에 군 연산이 정의되어 암호학 및 정수론에 활용된다.
  • 해석적 수론 - 리만 제타 함수
    리만 제타 함수는 복소수 s의 함수로, 실수부가 1보다 큰 영역에서 무한급수로 정의되고 s ≠ 1인 모든 복소수에서 유리형 함수로 해석적 연속이 가능하며 함수 방정식과 오일러 곱 공식을 만족하고, 영점 분포는 소수 분포와 관련이 있으며, 비자명 영점이 임계선 상에 있다는 리만 가설은 중요한 미해결 문제이다.
  • 소수 - 소수 (수론)
    소수는 1과 자기 자신만을 약수로 가지는 1보다 큰 자연수이며, 무한히 많고 정수론의 기본 정리에서 중요한 역할을 하며 다양한 분야에 응용된다.
  • 소수 - 디리클레 L-함수
    디리클레 L-함수는 디리클레 지표로 정의되는 복소함수로, 등차수열에 대한 디리클레 정리를 증명하기 위해 도입되었으며, 리만 제타 함수의 일반화이자 오일러 곱, 함수 방정식 등의 성질을 가지며, 모듈러 형식, 타원 곡선과 관련되어 수론적 L-함수 연구의 핵심이고 암호론, 컴퓨터 과학 등에 응용된다.
목차

2. 역사

정수론에서 소수 개수의 증가 속도는 매우 중요한 관심사였다. 18세기 레온하르트 오일러는 소수열의 역수의 합이 발산한다는 것을 보였다.(소수의 무한성 증명 참조) 제곱수의 역수의 합은 수렴하므로, 이것은 π(x)가 \sqrt{x}보다 빠르게 증가한다는 것을 나타낸다.

1808년 아드리앵마리 르장드르는 다음과 같은 등식을 제시했다.

:\pi (N)=\pi (\sqrt{N} )-1+\sum_d \mu (d)\left[ \frac{N}{d} \right]

여기서 \mu(d)는 뫼비우스 함수, [x]는 가우스 기호이며, 합은 \sqrt{N} 이하의 모든 소수의 곱 P의 모든 양의 약수 d를 포함한다. 이 식으로부터,

:\lim_{x\to \infty} \frac{\pi(x)}{x} =0

이 유도된다.

18세기 말 카를 프리드리히 가우스와 아드리앵마리 르장드르는 소수 계량 함수 π(x)가 \frac{x}{\operatorname{ln} x}에 점근적으로 근사될 수 있다는 것, 즉

:\lim_{x\to \infty} \frac{\pi (x)}{x/\operatorname{ln} x} =1

이 성립할 것이라고 예측했다. 1850년 경 파프누티 체비쇼프는 이 등식의 좌변이 만약 극한을 가진다면, 그것은 1이어야 함을 보였다.

--

이후 이 예측은 오랫동안 증명되지 않았지만, 1896년에 자크 아다마르와 샤를장 드 라 발레푸생( 샤를장 드 라 발레푸생프랑스어)이 독립적으로 증명하였으며, 현재는 소수 정리라고 불린다. 그들의 증명은 1859년 베른하르트 리만이 도입한 리만 제타 함수의 성질을 이용한다.

오랫동안 해석학적 방법을 사용하지 않고는 소수 정리를 증명할 수 없다고 믿었지만, 1948년 경 아틀레 셀베르그와 에르되시 팔은 복소해석을 사용하지 않는 소수 정리의 증명을 (거의 독립적으로) 발견했다. 이러한 증명에서는 수론적 함수의 초등적 평가만을 사용했다.

2.1. 리만 가설과의 관계

리만은 1859년 제타 함수의 영점을 사용하여 π(x)를 나타내는 다음 식을 발견했다.

:\pi (x)=R(x)-\sum_{\rho} R(x^{\rho})

여기서 R(x)는,

:R(x)=\sum_{m=1}^{\infty} \frac{\mu (m)}{m} \operatorname{li} (x^{\tfrac{1}{m}})

로 정의되며, 합의 ρ는 제타 함수의 모든 영점을 통과한다.

리만 가설은 π(x)에 대한 추정 오차에 대해 훨씬 더 엄격한 경계를 의미하며, 따라서 소수의 보다 규칙적인 분포를 의미한다. 리만 가설과 다음 식이 옳다는 것은 동치이다.

:\pi (x)=\operatorname{li} (x)+O\left( \sqrt{x} \ln x\right)

여기서 O는 란다우 표기법이다.

리만 가설이 참일 경우, 다음 식이 성립한다.

:|\pi(x) - \operatorname{li}(x)| < \frac{1}{8\pi} \sqrt{x} \, \log{x}, \qquad \text{for all } x \ge 2657.

3. 명시적 공식

폰 망골트(von Mangoldt)는 다음 공식을 증명하였다.

:\psi(x) = x - \sum_{\rho\in S} \frac{x^\rho}{\rho} - \ln 2\pi - \frac12 \ln(1-x^{-2})

여기서
* S는 리만 제타 함수의 임계구역(critical strip)에 있는 영점들이다.
::S=\{\rho\in\mathbb C\colon \zeta(\rho)=0,\;0<\operatorname{Re}\rho<1\}
* 합 \sum_{\rho\in S}는 절대수렴하지 않는다. 이 경우 합은 |\operatorname{Im}\rho|의 순으로 계산하여 수렴하게 만든다.
* 위 공식은 x가 특정한 정수가 아니면서 1보다 큰 실수인 경우에 유효하다. 만약 x가 특정한 정수 (소수 및 소수의 자연수 거듭제곱)인 경우, 해당 점에서의 좌변의 좌극한과 우극한의 평균값이 우변과 같게 된다.

두 번째 체비쇼프 함수 \psi에 대한 표현은 다음과 같다.

:\psi_0(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \log 2\pi - \frac{1}{2} \log\left(1-x^{-2}\right),

여기서

: \psi_0(x) = \lim_{\varepsilon \to 0} \frac{\psi(x - \varepsilon) + \psi(x + \varepsilon)}{2}.

여기서 \rho는 임계 띠에 있는 리만 제타 함수의 영점이며, \rho의 실수 부분은 0과 1 사이이다. 이 공식은 1보다 큰 x 값에 유효하다. 근의 합은 조건부 수렴하며, 허수 부분의 절댓값이 증가하는 순서로 취해야 한다.

4. π(x), x/ln x, 및 li(x)의 수치적 계산 결과

👆
좌우로 밀어서 보기
xπ(x)π(x) − x / ln xli(x) − π(x)x / π(x)
104−0.32.22.500
102253.35.14.000
10316823105.952
1041 229143178.137
1059 5929063810.425
10678 4986 11613012.740
107664 57944 15833915.047
1085 761 455332 77475417.357
10950 847 5342 592 5921 70119.667
1010455 052 51120 758 0293 10421.975
10114 118 054 813169 923 15911 58824.283
101237 607 912 0181 416 705 19338 26326.590
1013346 065 536 83911 992 858 452108 97128.896
10143 204 941 750 802102 838 308 636314 89031.202
101529 844 570 422 669891 604 962 4521 052 61933.507
1016279 238 341 033 9257 804 289 844 3933 214 63235.812
10172 623 557 157 654 23368 883 734 693 2817 956 58938.116
101824 739 954 287 740 860612 483 070 893 53621 949 55540.420
1019234 057 667 276 344 6075 481 624 169 369 96099 877 77542.725
10202 220 819 602 560 918 84049 347 193 044 659 701222 744 64445.028
102121 127 269 486 018 731 928446 579 871 578 168 707597 394 25447.332
1022201 467 286 689 315 906 2904 060 704 006 019 620 9941 932 355 20849.636
10231 925 320 391 606 803 968 92337 083 513 766 578 631 3097 250 186 21651.939

--

위 표는 소수 계량 함수 π(x)와 두 근사 함수 x / ln x, li(x)의 값을 10의 거듭제곱에서 비교한 결과를 보여준다. x가 증가함에 따라 π(x)는 x / ln x와 li(x)에 점근적으로 가까워진다.

5. π(x) 계산 알고리즘

에라토스테네스의 체를 사용하여 $x$ 이하의 소수를 생성한 다음 그 수를 세는 것은 $\pi(x)$를 찾는 간단한 방법이다.

르장드르는 포함-배제 원리를 사용하여 $\pi(x)$를 찾는 더 정교한 방법을 제시했다. 주어진 $x$에 대해, $p_1, p_2, \dots, p_n$이 서로 다른 소수라면, $p_i$로 나누어 떨어지지 않는 $x$ 이하의 정수의 개수는 다음과 같다.

:\lfloor x\rfloor - \sum_{i}\left\lfloor\frac{x}{p_i}\right\rfloor + \sum_{i

(여기서 $\lfloor x \rfloor$는 바닥 함수를 나타낸다). 이 수는 $p_1, p_2, \dots, p_n$이 $x$의 제곱근 이하의 소수일 때 다음과 같다.

:\pi(x)-\pi\left(\sqrt{x}\right)+1

에른스트 마이즐은 1870년과 1885년 사이에 발표된 일련의 논문에서 $\pi(x)$를 평가하는 실용적인 조합적 방법을 설명하고 사용했다. $p_1, p_2, \dots, p_n$을 처음 $n$개의 소수라고 하고, $\Phi(m,n)$을 $m$보다 크지 않고 모든 $i \le n$에 대해 $p_i$로 나누어지지 않는 자연수의 개수로 나타낸다. 그러면

:\Phi(m,n)=\Phi(m,n-1)-\Phi\left(\frac m {p_n},n-1\right).

자연수 $m$이 주어지고, $n = \pi(\sqrt[3]{m})$이고 $\mu = \pi(\sqrt{m}) - n$이면,

:\pi(m) = \Phi(m,n)+n(\mu+1)+\frac{\mu^2-\mu} 2 - 1 - \sum_{k=1}^\mu\pi\left(\frac m {p_{n+k}}\right) .

이 방식을 사용하여 메이즐은 $x$가 $5 \times 10^5$, $10^6$, $10^7$, 그리고 $10^8$일 때 $\pi(x)$를 계산했다.

데릭 헨리 레머는 1959년에 메이즐의 방법을 확장하고 단순화했다. 실수 $m$과 자연수 $n$과 $k$에 대해, $P_k(m,n)$을 $m$보다 크지 않고 정확히 $k$개의 소인수를 가지며, 모두 $p_n$보다 큰 숫자의 개수로 정의한다. 또한, $P_0(m,n) = 1$로 설정한다. 그러면

:\Phi(m,n) = \sum_{k=0}^{+\infty} P_k(m,n)

여기서 합은 실제로 유한 개의 0이 아닌 항만 갖는다. $\sqrt[3]{m} \le y \le \sqrt{m}$이고 $n = \pi(y)$인 정수 $y$를 나타냅니다. 그러면 $P_1(m,n) = \pi(m) - n$이고 $k \ge 3$일 때 $P_k(m,n) = 0$이다. 따라서,

:\pi(m) = \Phi(m,n) + n - 1 - P_2(m,n)

$P_2(m,n)$의 계산은 다음과 같이 얻을 수 있다.

:P_2(m,n) = \sum_{y < p \le \sqrt{m} } \left( \pi \left( \frac m p \right) - \pi(p) + 1\right)

여기서 합은 소수를 대상으로 한다.

한편, $\Phi(m,n)$의 계산은 다음 규칙을 사용하여 수행할 수 있다.

# \Phi(m,0) = \lfloor m\rfloor
# \Phi(m,b) = \Phi(m,b-1) - \Phi\left(\frac m{p_b},b-1\right)

레머는 그의 방법과 IBM 701을 사용하여 $\pi(10^9)$의 정확한 값을 계산할 수 있었고, $\pi(10^{10})$의 정확한 값에서 1만큼 차이가 났다.

이 방법에 대한 추가 개선은 라가리아스, 밀러, 오들리즈코, 들레글리즈, 그리고 리바에 의해 이루어졌다.

6. 부등식

Pierre Dusart영어가 2010년에 제시한 부등식은 다음과 같다.

: \frac {x} {\log x - 1} < \pi(x) < \frac {x} {\log x - 1.1}\quad \text{for }x \ge 5393 \text{ and }x \ge 60184,\text{ respectively.}

뒤사르는 최근 다음 부등식을 증명했다.

:\frac{x}{\log x} \left( 1 + \frac{1}{\log x} + \frac{2}{\log^2 x} \right) \le \pi(x) \le \frac{x}{\log x} \left( 1 + \frac{1}{\log x} + \frac{2}{\log^2 x} + \frac{7.59}{\log^3 x} \right)

이 부등식은 각각 와 에 대해 성립한다.

번째 소수 에 대한 부등식은 다음과 같다.

: n (\log n + \log\log n - 1) < p_n < n (\log n + \log\log n)\quad \text{for } n \ge 6.

왼쪽 부등식은 에 대해 성립하며, 오른쪽 부등식은 에 대해 성립한다.

2010년에 뒤사르는 다음 부등식을 증명했다.

: n \left( \log n + \log \log n - 1 + \frac{\log \log n - 2.1}{\log n} \right) \le p_n \le n \left( \log n + \log \log n - 1 + \frac{\log \log n - 2}{\log n} \right)

이 부등식은 각각 와 에 대해 성립한다.

피에르 데저트는 2010년에 다음 6개의 부등식을 제시했다.

*\frac{x}{\ln x} (1+\frac{1}{\ln x}) <\pi (x) (단, x ≥ 599)
*\pi (x)<\frac{x}{\ln x} (1+\frac{1.2762}{\ln x}) (단, x ≥ 1)
*\frac{x}{\ln x-1} <\pi (x) (단, x ≥ 5393)
*\pi (x)<\frac{x}{\ln x-1.1} (단, x ≥ 60184)
*\frac{x}{\ln x} (1+\frac{1}{\ln x}+\frac{2}{\ln^2 x}) <\pi (x) (단, x ≥ 88783)
*\pi (x)<\frac{x}{\ln x} (1+\frac{1}{\ln x}+\frac{2.334}{\ln^2 x}) (단, x ≥ 2953652287)

7. 기타 소수 계량 함수

리만의 소수 거듭제곱 계량 함수는 보통 $\Pi_0(x)$ 또는 $J_0(x)$로 표기한다. 이 함수는 소수 거듭제곱 $p^n$에서 $\frac{1}{n}$의 점프를 가지며, $\pi(x)$의 불연속점에서 양쪽 값의 중간 값을 취한다. 이러한 세부 사항은 함수가 역 멜린 변환으로 정의될 수 있기 때문에 사용된다.

공식적으로, $\Pi_0(x)$를 다음과 같이 정의할 수 있다.
:\Pi_0(x) = \frac{1}{2} \left( \sum_{p^n < x} \frac{1}{n} + \sum_{p^n \le x} \frac{1}{n} \right)\
여기서 각 합의 변수 $p$는 지정된 한계 내의 모든 소수를 나타낸다.

또한 다음과 같이 쓸 수 있다.
:\Pi_0(x) = \sum_{n=2}^x \frac{\Lambda(n)}{\log n} - \frac{\Lambda(x)}{2\log x} = \sum_{n=1}^\infty \frac 1 n \pi_0\left(x^{1/n}\right)
여기서 $\Lambda$는 폰 망골트 함수이고

:\pi_0(x) = \lim_{\varepsilon \to 0} \frac{\pi(x-\varepsilon) + \pi(x+\varepsilon)}{2}.

뫼비우스 반전 공식은 다음을 제공한다.
:\pi_0(x) = \sum_{n=1}^\infty \frac{\mu(n)}{n}\ \Pi_0\left(x^{1/n}\right),
여기서 $\mu(n)$는 뫼비우스 함수이다.

리만 제타 함수의 로그와 폰 망골트 함수 $\Lambda$ 사이의 관계를 알고, 페론 공식을 사용하면 다음을 얻는다.
:\log \zeta(s) = s \int_0^\infty \Pi_0(x) x^{-s-1}\, \mathrm{d}x
체비쇼프 함수는 소수 또는 소수 거듭제곱 $p^n$에 $\log p$의 가중치를 부여한다.

:\begin{align}
\vartheta(x) &= \sum_{p\le x} \log p \\
\psi(x)&=\sum_{p^n \le x} \log p = \sum_{n=1}^\infty \vartheta \left( x^{1/n} \right) = \sum_{n \le x}\Lambda(n) .
\end{align}

$x \ge 2$에 대해,
:\vartheta(x) = \pi(x)\log x - \int_2^x \frac{\pi(t)}{t}\, \mathrm{d}t
이고
:\pi(x)=\frac{\vartheta(x)}{\log x} + \int_2^x \frac{\vartheta(t)}{t\log^{2}(t)} \mathrm{d} t .