체 이론(Sieve theory)은 숫자 이론(number theory)에서 일반적인 기술의 집합으로, 정수의 체로-친 집합(sifted sets)의 크기를 세거나, 보다 현실적으로 추정하기 위해 설계되었습니다. 체로-진 집합의 원형적 예제는 어떤 규정된 극한 X까지의 소수의 집합입니다. 이에 상응하여, 체의 원형 예제는 에라토스테네스의 체(sieve of Eratosthenes) 또는 더 일반적인 르장드르 체(Legendre sieve)입니다. 이들 방법을 사용하는 소수에 대한 직접적인 공격은 오차 항의 누적이라는 방법으로 곧 분명히 극복할 수 없는 장애물에 도달합니다. 20세기 숫자 이론의 주요 흐름 중 하나에서. 체질이 무엇이어야 하는지에 대한 소박한 아이디어로 정면 공격의 어려움을 피하는 방법이 발견되었습니다.
한 가지 성공적인 접근 방식은 숫자의 특정 체로-친 집합 (예를 들어, 소수의 집합)을 전형적으로 원래 집합보다 다소 크고 분석하기에 더 쉬운 또 다른 간단한 집합 (예를 들어, 거의 소수의 집합)으로 근사화하는 것입니다. 보다 정교한 체는 역시 집합 자체로 직접 작동하지 않지만, 대신 이들 집합에서 신중하게 선택된 가중 함수(weight functions)에 따라 그것들을 셉니다 (이들 집합의 일부 원소에 다른 것보다 더 "가중"을 부여하는 선택 사항). 게다가, 일부 현대 응용에서, 체는 체로-친 집합의 크기를 추정하기 위해 사용되지 않고, 집합의 특성 함수(characteristic function)보다 분석하기 더 쉬운 반면 집합에서는 크고 집합 외부에서는 대부분 작은 함수를 생성하기 위해 사용됩니다.
Basic sieve theory
표기법에 대한 정보는 마지막 부분을 참조하십시오.
우리는 비-음의 숫자 \(\displaystyle \mathcal{A}=(a_n)\)의 일부 유한 수열(finite)로 시작합니다. 가장 기본적인 경우에서, 이 수열은 우리가 체질하기를 원하는 일부 집합 \(\displaystyle A=\{s:s\leq x\}\)의 지시 함수(indicator function) \(\displaystyle a_n=1_{A}(n)\)일 뿐입니다. 어쨌든, 이 추상화는 보다 일반적인 상황을 허용합니다. 다음으로 우리는 체로-친 범위(sifting range) \(\displaystyle \mathcal{P}\subseteq \mathbb{P}\)라고 불리는 일반적인 소수의 집합과 함수 \(\displaystyle P(z)=\prod\limits_{p\in\mathcal{P}, p<z}p\)로 \(\displaystyle z\)까지의 그것들의 곱을 도입합니다.
체 이론의 목표는 체질하는 함수(sifting function)를 추정하기 위한 것입니다:
\(\quad\displaystyle S(\mathcal{A},\mathcal{P},z)=\sum\limits_{n\leq x, (n,P(z))=1}a_n.\)
\(\displaystyle a_n=1_{A}(n)\)의 경우에서, 이것은 단지 \(\displaystyle P(z)\)의 소인 인수(prime factors)와 서로소(coprime)인 숫자의 부분집합 \(\displaystyle A_{\operatorname{sift}}\subseteq A\)의 카디널리티(cardinality)를 셉니다.
Legendre's identity
우리는 뫼비우스 함수와 \(\displaystyle \mathcal{P}\)의 원소에 의해 유도된 일부 함수 \(\displaystyle A_d(x)\)를 사용함으로써
\(\quad\displaystyle A_d(x)=\sum\limits_{n\leq x, n\equiv 0\pmod{d}}a_n\)
다음 르장드르의 항등식(Legendre's identity)으로 체질하는 함수를 다시 쓸 수 있습니다:
\(\quad\displaystyle S(\mathcal{A},\mathcal{P},z)=\sum\limits_{d\mid P(z)}\mu(d)A_d(x).\)
Example
\(\displaystyle z=7\)와 \(\displaystyle \mathcal{P}=\mathbb{P}\)라고 놓습니다. 뫼비우스 함수는 모든 각 소수에 대해 음수이므로, 다음을 얻습니다:
\(\quad\displaystyle \begin{align}
S(\mathcal{A},\mathbb{P},7)&=A_1(x)-A_2(x)-A_3(x)-A_5(x)+A_6+A_{10}+A_{15}-A_{30}.
\end{align}\)
Approximation of the congruence sum
그런-다음 \(\displaystyle A_d(x)\)가 다음과 같이 쓸 수 있다고 가정합니다:
\(\quad\displaystyle A_d(x)=g(d)X+r_d(x)\)
여기서 \(\displaystyle g(d)\)는 밀도(density)이며, 다음을 만족하는 곱셈 함수(multiplicative function)를 의미하고
\(\quad\displaystyle g(1)=1,\qquad 0\leq g(p)<1 \qquad p\in \mathbb{P}\)
\(\displaystyle X\)는 \(\displaystyle A_1(x)\)의 근사이고 \(\displaystyle r_d(x)\)는 일부 나머지 항입니다. 체질하는 함수는 다음이 됩니다:
\(\quad\displaystyle S(\mathcal{A},\mathcal{P},z)=X\sum\limits_{d\mid P(z)}\mu(d)g(d)+\sum\limits_{d\mid P(z)}\mu(d)r_d(x)\)
또는 짧게
\(\quad\displaystyle S(\mathcal{A},\mathcal{P},z)=XG(x,z)+R(x,z).\)
그런-다음 \(\displaystyle S\)에 대해 각각 \(\displaystyle G\)와 \(\displaystyle R\)을 위쪽 경계와 아래쪽 경계로 찾음으로써 체질하는 함수를 추정하려고 시도합니다.
체질하는 함수의 부분 합은 과대- 및 과소-계산을 번갈아 하므로, 나머지 항이 엄청날 것입니다. 이 방법을 개선하기 위한 브룬(Brun)의 아이디어는 체질하는 함수에서 \(\displaystyle \mu(d)\)를 제한된 뫼비우스 함수로 구성된 가중 수열 \(\displaystyle (\lambda_d)\)로 대체하는 것이었습니다. 두 개의 적절한 수열 \(\displaystyle (\lambda_d^{-})\)와 \(\displaystyle (\lambda_d^{+})\)를 선택하고 \(\displaystyle S^{-}\)와 \(\displaystyle S^{+}\)로 체질하는 함수를 나타내면, 원래 체질하는 함수의 위쪽 경계와 아래쪽 경계를 얻을 수 있습니다:
\(\quad\displaystyle S^{-}\leq S\leq S^{+}.\)
\(\displaystyle g\)는 곱셈적이기 때문에, 다음 항등식으로 작업할 수도 있습니다:
\(\quad\displaystyle \sum\limits_{d\mid n}\mu(d)g(d)=\prod\limits_{\begin{array}{c} p|n ;\; p\in\mathbb{P}\end{array}}(1-g(p)),\quad\forall\; n\in\mathbb{N}.\)
Notation: 표기법에 관한 주의 사항으로, 문헌에서 종종 수열 \(\displaystyle \mathcal{A}\)의 집합을 집합 \(\displaystyle A\) 자체와 동일시합니다. 이것은 수열 \(\displaystyle \mathcal{A}=(a_n)\)을 정의하기 위해 \(\displaystyle \mathcal{A}=\{s:s\leq x\}\)를 쓴다는 것을 의미합니다. 역시 문헌에서, 합 \(\displaystyle A_d(x)\)는 때때로 일부 집합 \(\displaystyle A_d(x)\)의 카디널리티 \(\displaystyle A_d(x)\)로 표기되고, 반면에 우리는 \(\displaystyle A_d(x)\)를 이미 이 집합의 카디널리티로 정의해 왔습니다. 우리는 소수의 집합을 표시하기 위해 \(\displaystyle \mathbb{P}\)를 사용했고 \(\displaystyle a\)와 \(\displaystyle b\)의 최대 공통 약수(greatest common divisor)에 대해 \(\displaystyle (a,b)\)를 사용했습니다.
Types of sieving
현대의 체는 브룬 체(Brun sieve), 셀베르그 체(Selberg sieve), 투란 체(Turán sieve), 큰 체(large sieve), 및 더 큰 체(larger sieve)를 포함합니다. 체 이론의 원래 목적 중 하나는 쌍둥이 소수 추측(twin prime conjecture)과 같은 숫자 이론에서 추측을 입증을 시도하는 것이었습니다. 체 이론의 원래 광범위한 목표는 여전히 대부분 달성되지 않았지만, 특히 다른 숫자 이론적 도구와 결합하여 일부 부분적인 성공이 있었습니다. 하이라이트는 다음과 같습니다:
- 브룬의 정리(Brun's theorem), 이것은 쌍둥이 소수의 역수의 합이 수렴한다는 것을 보여줍니다 (반면에 모든 소수의 역수의 합은 발산합니다);
- 천의 정리(Chen's theorem), 이것은 p + 2가 소수이거나 반-소수 (두 소수의 곱)임을 만족하는 무한하게 많은 소수 p가 있다는 것을 보여줍니다; 밀접하게 관련된 천 징룬(Chen Jingrun)의 정리는 모든 각 충분하게 큰 짝수는 소수와 소수 또는 반-소수인 또 다른 숫자의 합이라고 주장합니다. 이것들은 각각 쌍둥이 소수 추측(twin prime conjecture)과 골드바흐 추측(Goldbach conjecture)에 거의 근접한 것으로 고려될 수 있습니다.
- 체 이론의 기본 보조정리(fundamental lemma of sieve theory), 이것은 만약 우리가 N 개의 숫자의 집합을 체질하는 것이면, \(\displaystyle \varepsilon\)가 충분하게 작다는 조건으로 하여 \(\displaystyle N^\varepsilon\) 반복 후 체에 남아 있는 원소의 숫자를 정확하게 추정할 수 있다고 주장합니다 (여기서 1/10과 같은 분수가 매우 전형적입니다). 이 보조정리는 보통 소수 (일반적으로 \(\displaystyle N^{1/2}\) 반복과 같은 것이 필요함)를 걸러내기에는 너무 약할 수 있지만, 거의 소수(almost primes)와 관련하여 결과를 얻기에는 충분할 수 있습니다.
- 프리드랜더–이바니에츠 정리(Friedlander–Iwaniec theorem), 이것은 \(\displaystyle a^2 + b^4\) 형식의 무한하게 많은 소수가 있다고 주장합니다.
- 탕(Zhang)의 정리 (Zhang 2014), 이것은 경계진 거리 내에 무한하게 많은 소수의 쌍이 있음을 보여줍니다. Maynard–Tao 정리 (Maynard 2015)는 탕의 정리를 임의적으로 긴 소수 수열로 일반화합니다.
Techniques of sieve theory
체 이론의 기술은 꽤 강력할 수 있지만, 패리티 문제(parity problem)로 알려진 장애물에 의해 제한되는 것 같으며, 패리티 문제는 대략적으로 말하면 체 이론 방법은 소수 인수의 홀수를 갖는 숫자와 소수 인수의 짝수를 갖는 숫자 사이를 구별하는 데 극도로 어려움이 있다고 주장합니다. 이 패리티 문제는 아직 잘 이해되지 않았습니다.
숫자 이론에서 다른 방법과 비교된, 체 이론은 대수적 숫자 이론(algebraic number theory) 또는 해석적 숫자 이론(analytic number theory) 중 하나에서 정교한 개념을 반드시 필요로 하지 않는다는 점에서 비교적 기본적(elementary)입니다. 그럼에도 불구하고, 더 발전된 체는 여전히 매우 복잡하고 섬세할 수 있고 (특히 숫자 이론에서 다른 심층 기술과 결합될 때), 전체 교과서가 숫자 이론의 이 단일 하위-분야에 할애되었습니다; 고전적인 텍스트는 (Halberstam & Richert 1974)이고 보다 현대적인 텍스트는 (Iwaniec & Friedlander 2010)입니다.
이 기사에서 논의된 체 방법은 이차 체(quadratic sieve) 및 일반 숫자 필드 체(general number field sieve)와 같은 정수 인수분해(integer factorization) 체 방법과 밀접한 관련이 없습니다. 그것들의 인수분해 방법은 에라토스테네스의 체(sieve of Eratosthenes)의 아이디어를 사용하여 숫자의 목록의 어떤 구성원이 작은 소수로 완전하게 인수화될 수 있는지 효율적으로 결정합니다.
Literature
- Cojocaru, Alina Carmen; Murty, M. Ram (2006), An introduction to sieve methods and their applications, London Mathematical Society Student Texts, vol. 66, Cambridge University Press, ISBN 0-521-84816-4, MR 2200366
- Motohashi, Yoichi (1983), Lectures on Sieve Methods and Prime Number Theory, Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 72, Berlin: Springer-Verlag, ISBN 3-540-12281-8, MR 0735437
- Greaves, George (2001), Sieves in number theory, Ergebnisse der Mathematik und ihrer Grenzgebiete (3), vol. 43, Berlin: Springer-Verlag, doi:10.1007/978-3-662-04658-6, ISBN 3-540-41647-1, MR 1836967
- Harman, Glyn (2007). Prime-detecting sieves. London Mathematical Society Monographs. Vol. 33. Princeton, NJ: Princeton University Press. ISBN 978-0-691-12437-7. MR 2331072. Zbl 1220.11118.
- Halberstam, Heini; Richert, Hans-Egon (1974). Sieve Methods. London Mathematical Society Monographs. Vol. 4. London-New York: Academic Press. ISBN 0-12-318250-6. MR 0424730.
- Iwaniec, Henryk; Friedlander, John (2010), Opera de cribro, American Mathematical Society Colloquium Publications, vol. 57, Providence, RI: American Mathematical Society, ISBN 978-0-8218-4970-5, MR 2647984
- Hooley, Christopher (1976), Applications of sieve methods to the theory of numbers, Cambridge Tracts in Mathematics, vol. 70, Cambridge-New York-Melbourne: Cambridge University Press, ISBN 0-521-20915-3, MR 0404173
- Maynard, James (2015). "Small gaps between primes". Annals of Mathematics. 181 (1): 383–413. arXiv:1311.4600. doi:10.4007/annals.2015.181.1.7. MR 3272929.
- Tenenbaum, Gérald (1995), Introduction to Analytic and Probabilistic Number Theory, Cambridge studies in advanced mathematics, vol. 46, Translated from the second French edition (1995) by C. B. Thomas, Cambridge University Press, pp. 56–79, ISBN 0-521-41261-7, MR 1342300
- Zhang, Yitang (2014). "Bounded gaps between primes". Annals of Mathematics. 179 (3): 1121–1174. doi:10.4007/annals.2014.179.3.7. MR 3171761.
External links
- Bredikhin, B.M. (2001) [1994], "Sieve method", Encyclopedia of Mathematics, EMS Press
References
