그린-타오 정리

2.1. 기본 정리

$\backslash pi(N)$을 $N$보다 작거나 같은 소수의 개수라고 하자. $A$가 소수의 부분 집합이고 다음 조건을 만족한다고 가정하자.

: $\backslash limsup\_\{N\backslash rightarrow\backslash infty\}\; \backslash frac$

2.2. 점근 공식 (조건부)

그린과 타오는 일반화된 하디-리틀우드 추측을 가정하여, N보다 작거나 같은 소수들로 이루어진 길이 k인 등차 수열, 즉 을 만족하는 소수 튜플의 개수에 대한 다음 점근 공식을 조건부로 증명하고 제시했다.

$(\backslash mathfrak\{S\}\_k\; +\; o(1))\backslash frac\{N^2\}\{(\backslash log\; N)^k\}$

여기서 $o(1)$은 N이 무한대로 갈 때 0으로 수렴하는 항을 의미하며, $\backslash mathfrak\{S\}\_k$는 다음과 같이 정의되는 상수이다.

$\backslash mathfrak\{S\}\_k\; :=\; \backslash frac\{1\}\{2(k-1)\}\backslash left(\backslash prod\_\{p\; \backslash leq\; k\}\backslash frac\{1\}p\backslash left(\backslash frac\{p\}\{p\; -\; 1\}\backslash right)^\{\backslash !k-1\}\backslash right)\backslash !\backslash left(\backslash prod\_\{p\; >\; k\}\backslash left(1\; -\; \backslash frac\{k-1\}p\backslash right)\backslash !\backslash left(\backslash frac\{p\}\{p\; -\; 1\}\backslash right)^\{\backslash !k-1\}\backslash right)\backslash !.$

이 결과는 처음에는 조건부로 제시되었으나, 이후 그린-타오와 그린-타오-지글러에 의해 무조건부로 증명되었다.

2.3. 점근 공식 (무조건부)

그린과 타오는 일반화된 하디-리틀우드 추측에 대한 후속 연구에서, $N$ 이하의 소수로 이루어진 길이 $k$의 등차 수열, 즉 을 만족하는 소수 k-튜플의 개수에 대한 다음과 같은 점근 공식을 제시했다.

:$(\backslash mathfrak\{S\}\_k\; +\; o(1))\backslash frac\{N^2\}\{(\backslash log\; N)^k\}$

여기서 상수 $\backslash mathfrak\{S\}\_k$는 다음과 같이 정의된다.

:$\backslash mathfrak\{S\}\_k\; :=\; \backslash frac\{1\}\{2(k-1)\}\backslash left(\backslash prod\_\{p\; \backslash leq\; k\}\backslash frac\{1\}p\backslash left(\backslash frac\{p\}\{p\; -\; 1\}\backslash right)^\{\backslash !k-1\}\backslash right)\backslash !\backslash left(\backslash prod\_\{p\; >\; k\}\backslash left(1\; -\; \backslash frac\{k-1\}p\backslash right)\backslash !\backslash left(\backslash frac\{p\}\{p\; -\; 1\}\backslash right)^\{\backslash !k-1\}\backslash right)\backslash !.$

이 결과는 처음에는 조건부로 제시되었으나, 이후 그린-타오와 그린-타오-지글러의 연구를 통해 무조건부로 증명되었다.

3. 증명의 개요

그린-타오 정리의 증명은 다음 세 가지 주요 구성 요소로 이루어진다.

# 세메레디 정리: 양의 상부 밀도를 갖는 정수의 부분 집합은 임의로 긴 등차수열을 포함한다는 정리이다. 하지만 소수는 정수 전체에서 밀도가 0이기 때문에, 이 정리가 사전적으로 소수에 직접 적용되지는 않는다.
# 전달 원리: 세메레디 정리를 적절한 의미에서 의사랜덤한 정수의 부분 집합으로 확장하는 원리이다. 이러한 결과는 현재 상대적 세메레디 정리라고 불린다.
# 의사랜덤 부분집합 구성: 소수를 조밀한 부분 집합으로 포함하는 정수의 의사랜덤 부분 집합을 구성하는 단계이다. 이 집합을 구성하기 위해 그린과 타오는 소수 간격에 대한 골드스톤, 핀츠, 그리고 이을드름의 연구에서 아이디어를 사용했다.

이렇게 구성된 집합의 의사랜덤성이 확립되면, 전달 원리를 적용하여 증명을 완료할 수 있다.

원 논문의 주장에 대한 수많은 단순화가 발견되었다. 콘런(Conlon), 폭스(Fox), 자오(Zhao)는 2014년에 증명에 대한 현대적인 설명을 제공했다.

3.1. 세메레디 정리

세메레디 정리는 그린-타오 정리 증명의 세 가지 주요 구성 요소 중 하나이다. 이 정리는 양의 상부 밀도를 갖는 정수의 부분 집합은 임의로 긴 등차수열을 포함한다고 설명한다. 하지만 소수는 전체 정수 집합 내에서 밀도가 0이기 때문에, 세메레디 정리가 사전적으로 소수 집합에 직접 적용되지는 않는다.

그린-타오 정리의 원 논문 주장에 대한 여러 단순화가 이후 발견되었다. Conlon, Fox, Zhao는 2014년에 증명에 대한 현대적인 설명을 제공했다.

3.2. 전달 원리

그린-타오 정리 증명의 세 가지 주요 구성 요소 중 하나는 전달 원리이다. 이 원리는 세메레디 정리를 적절한 의미에서 의사랜덤한 정수의 부분 집합으로 확장하는 역할을 한다. 이러한 결과는 현재 상대적 세메레디 정리라고 불린다.

그린-타오 정리 증명 과정에서는 먼저 소수를 조밀한 부분 집합으로 포함하는 정수의 의사랜덤 부분 집합을 구성한다. 이 집합의 의사랜덤성이 확립되면, 전달 원리를 적용하여 증명을 완료한다.

원 논문의 주장에 대한 수많은 단순화가 발견되었다. Conlon, Fox, Zhao (2014)는 증명에 대한 현대적인 설명을 제공한다.

3.3. 의사랜덤 부분집합 구성

그린-타오 정리 증명의 세 가지 주요 구성 요소 중 하나는 소수를 조밀한 부분 집합으로 포함하는 정수의 의사랜덤 부분 집합을 구성하는 것이다. 이 집합을 만들기 위해 그린과 타오는 소수 간격에 대한 골드스톤, 핀츠, 그리고 이을드름의 연구에서 아이디어를 사용했다.

이렇게 구성된 집합의 의사랜덤성이 확립되면, 세메레디 정리를 의사랜덤 집합으로 확장한 전달 원리(상대적 세메레디 정리)를 적용하여 증명을 완료할 수 있다.

원래 증명이 발표된 이후, 주장에 대한 여러 단순화된 설명들이 나왔다. 콘런, 폭스, 자오는 2014년에 증명에 대한 현대적인 설명을 제공하기도 했다.

4. 수치적 연구

그린-타오 정리는 소수가 임의로 긴 산술 수열을 포함한다는 것을 수학적으로 증명했지만, 이는 존재 증명의 성격을 가지므로 실제로 그러한 수열을 어떻게 찾을 수 있는지 구체적인 방법을 제시하지는 않는다. 따라서 소수로 이루어진 긴 산술 수열을 실제로 찾아내기 위한 별도의 계산적 연구가 진행되었다.

그린-타오 정리 발표 당시(2004년)에는 마르쿠스 프린드(Markus Frind), 폴 언더우드(Paul Underwood), 폴 조블링(Paul Jobling)이 발견한 길이 23의 수열이 가장 긴 것으로 알려져 있었다. 이후 컴퓨터 성능 향상과 PrimeGrid와 같은 분산 컴퓨팅 프로젝트의 도움으로 더 긴 소수 산술 수열들이 지속적으로 발견되었다. 2007년에는 야로스와프 브로블레프스키(Jarosław Wróblewski)에 의해 길이 24의 수열이 발견되었고, 2008년에는 브로블레프스키와 라아난 체르모니(Raanan Chermoni)가 길이 25의 수열을 발견했다. 2010년에는 브누아 페리숑(Benoît Perichon)이 길이 26의 수열을, 2019년에는 롭 가한(Rob Gahan)과 PrimeGrid가 길이 27의 수열을 발견하며 기록이 갱신되었다. 발견된 수열들은 종종 소수 계승(primorial, 기호 '#')을 포함하는 형태로 표현된다.

4.1. 발견 사례

그린-타오 정리는 소수들이 임의로 긴 산술 수열을 포함한다는 존재 정리이지만, 실제로 이러한 수열을 찾는 방법을 제시하지는 않는다. 따라서 가장 긴 소수 산술 수열을 찾기 위한 별도의 계산 노력이 이어졌다.

그린-타오 정리 논문 발표 당시 알려진 가장 긴 소수 산술 수열은 길이가 23개였으며, 2004년 마르쿠스 프린드(Markus Frind), 폴 언더우드(Paul Underwood), 폴 조블링(Paul Jobling)이 발견했다.
: 56,211,383,760,397 + 44,546,738,095,860 · k, (k = 0, 1, ..., 22)

이후 더 긴 소수 산술 수열들이 발견되었다.

* 길이 24: 2007년 1월 18일, 야로스와프 브로블레프스키(Jarosław Wróblewski)가 발견했다.
*: 468,395,662,504,823 + 205,619 · 223,092,870 · n, (n = 0, 1, ..., 23)
*: 여기서 상수 223,092,870은 23 이하의 모든 소수의 곱으로, 소수 계승 (23#)이라고 한다.

* 길이 25: 2008년 5월 17일, 브로블레프스키와 라아난 체르모니(Raanan Chermoni)가 발견했다.
*: 6,171,054,912,832,631 + 366,384 · 23# · n, (n = 0, 1, ..., 24)

* 길이 26: 2010년 4월 12일, 브누아 페리숑(Benoît Perichon)이 분산 컴퓨팅 프로젝트인 PrimeGrid에서 브로블레프스키와 제프 레이놀즈(Geoff Reynolds)의 소프트웨어를 사용하여 발견했다.
*: 43,142,746,595,714,191 + 23,681,770 · 23# · n, (n = 0, 1, ..., 25)

* 길이 27: 2019년 9월, 롭 가한(Rob Gahan)과 PrimeGrid가 발견했다.
*: 224,584,605,939,537,911 + 81,292,139 · 23# · n, (n = 0, 1, ..., 26)

5. 확장 및 일반화

세메레디 정리의 확장 중 다수는 소수에도 적용된다. 그린-타오 정리는 발표 이후 여러 방향으로 확장되고 일반화되었다.

주요 확장으로는 다차원 공간으로의 일반화가 있으며, 이는 이후 폭스와 자오에 의해 증명이 단순화되기도 했다.

또한 2006년, 타오와 지글러는 이 정리를 다항식 수열의 경우까지 확장하여, 특정 조건을 만족하는 다항식 값들이 동시에 소수가 되는 경우가 무한히 많음을 보였다. 이는 기존의 등차수열 결과를 특수한 경우로 포함한다.

더 나아가 타오는 가우스 소수에 대해서도 그린-타오 정리와 유사한 결과가 성립함을 증명했다.

5.1. 다차원 일반화

세메레디 정리의 확장 중 상당수는 소수 집합에도 적용될 수 있다.

독립적으로, 타오와 지글러, 그리고 쿡, 머자르, 티치체트라쿤은 그린-타오 정리를 다차원으로 일반화하는 결과를 얻었다. 타오와 지글러가 제시한 증명은 이후 폭스와 자오에 의해 더 간결하게 다듬어졌다.

2006년에는 타오와 지글러가 그린-타오 정리를 다항식 수열의 형태로 확장했다. 더 자세히 설명하면, 상수항이 모두 0인 임의의 정수 계수 다항식 $P\_1(m),\; \backslash ldots,\; P\_k(m)$에 대해, $x\; +\; P\_\{1\}\; (m),\; \backslash ldots,\; x\; +\; P\_\{k\}\; (m)$이 모두 동시에 소수가 되는 정수쌍 $x,\; m$이 무한히 많이 존재한다는 것이다. 만약 여기서 다항식을 $m,\; 2m,\; \backslash ldots,\; km$으로 특별히 선택하면, 이는 길이 $k$인 소수의 등차수열이 무한히 존재한다는 원래의 그린-타오 정리를 포함하는 결과가 된다.

타오는 또한 가우스 소수에 대해서도 그린-타오 정리와 유사한 결과가 성립함을 증명했다.

5.2. 다항식 수열

2006년, 타오와 지글러는 그린-타오 정리를 다항식 수열까지 확장했다. 구체적으로, 미지수 $m$에 대한 임의의 정수 계수 다항식 $P\_1,\; \backslash ldots,\; P\_k$가 주어졌을 때 (단, 모든 다항식의 상수항은 0이어야 한다), $x\; +\; P\_\{1\}\; (m),\; \backslash ldots,\; x\; +\; P\_\{k\}\; (m)$ 형태의 항들이 모두 동시에 소수가 되는 정수 $x$와 $m$ 쌍이 무한히 많이 존재한다는 것을 증명했다.

이 정리는 다항식이 특별히 $m,\; 2m,\; \backslash ldots,\; km$인 경우를 포함한다. 이 경우, 수열은 $x\; +\; m,\; x\; +\; 2m,\; \backslash ldots,\; x\; +\; km$ 형태가 되는데, 이는 길이가 $k$인 소수의 등차수열이 무한히 많이 존재한다는 기존의 그린-타오 정리 내용과 일치한다.

5.3. 가우스 소수

타오는 가우스 소수에 대한 그린-타오 정리의 유추를 증명했다.