세메레디의 정리

2.2. 유한 버전

이 정리의 자주 사용되는 동치 유한 버전은 모든 양의 정수 k와 실수 $\backslash delta\; \backslash in\; (0,\; 1]$에 대해 다음을 만족하는 양의 정수

:$N\; =\; N(k,\backslash delta)$

가 존재하여, 크기가 $\backslash delta\; N$ 이상인 집합 {1, 2, ..., N}의 모든 부분 집합은 길이 k의 등차 수열을 포함한다는 것이다.

2.3. 점근적 경계

함수 r_k(N)은 길이 k의 등차 수열을 갖지 않는 집합 {1, 2, ..., N}의 가장 큰 부분 집합의 크기로 정의된다. 세메레디 정리는 다음과 같은 점근적 경계와 동치이다.

:$r\_k(N)\; =\; o(N).$

이는 r_k(N)이 N과 거의 선형적으로 증가함을 의미한다.

3. 역사

1927년 반 데르 바르덴 정리가 세메레디 정리의 전신으로 증명되었다. 1936년 에르되시 팔과 투란 팔이 가설을 세웠고, 1975년 세메레디 엔드레가 복잡한 조합론적 방법을 이용해 증명에 성공하였다. 1977년 힐렐 퓌르스텐베르크는 에르고딕 이론의 문제로 치환하는 놀라운 발상에 착안해 색다른 증명을 만들었다.

k = 3인 경우는 1953년 클라우스 로스가 하디-리틀우드 원법을 변형하여 증명했다. 세메레디는 조합론을 통해 k = 4의 경우를 증명했다. 로스는 1972년에 k = 3의 경우에 사용했던 접근 방식과 유사한 방식으로 k = 4에 대한 두 번째 증명을 제시했다.

일반적인 경우는 1975년에 세메레디가 해결했는데, 그는 이전에 k = 4에 대해 사용했던 조합론적 논증을 독창적이고 복잡하게 확장했다. 이는 에르되시에 의해 "조합적 추론의 걸작"이라고 불렸다. 현재 몇 가지 다른 증명들이 알려져 있는데, 가장 중요한 것은 1977년 힐렐 퍼스텐버그와 2001년 푸리에 해석과 조합론을 모두 사용하면서 현재 거워스 노름이라고 불리는 것을 도입한 티모시 가워스에 의한 증명이다. 테렌스 타오는 세메레디의 정리의 다양한 증명을 서로 다른 수학 분야를 연결하는 "로제타석"이라고 불렀다.

4. 정량적 경계

r_k(N)의 정확한 성장률을 결정하는 것은 여전히 미해결 문제이다. 현재 알려진 일반적인 경계는 다음과 같다.

:$CN\backslash exp\backslash left(-n2^\{(n\; -\; 1)/2\}\backslash sqrt[n]\{\backslash log\; N\}\; +\; \backslash frac\{1\}\{2n\}\backslash log\; \backslash log\; N\backslash right)\; \backslash leq\; r\_k(N)\; \backslash leq\; \backslash frac\{N\}\{(\backslash log\; \backslash log\; N)^\{2^\{-2^\{k\; +\; 9\}\}\}\},$

여기서 $n\; =\; \backslash lceil\; \backslash log\; k\backslash rceil$이다. 하한은 베렌트, 랭킨, 및 엘킨의 연구를 기반으로 한 O'Bryant에 의해 제시되었다. 상한은 가워스에 의해 제시되었다.

작은 k의 경우, 일반적인 경우보다 더 좁은 경계가 존재한다. k = 3일 때, 부르갱, 히스-브라운, 세메레디, 샌더스, 및 블룸은 점진적으로 더 작은 상한을 설정했으며, 블룸과 시삭은 "로그 장벽"을 깬 최초의 경계를 증명했다. 현재 최상의 경계는 다음과 같다.

:$N\; 2^\{-\backslash sqrt\{8\backslash log\; N\}\}\; \backslash leq\; r\_3(N)\; \backslash leq\; N\; e^\{-c(\backslash log\; N)^\{1/9\}\}$, 어떤 상수 $c>0$에 대해,

각각 O'Bryant,와 블룸과 시삭에 의해 제시되었다.

k = 4의 경우, 그린과 타오는 다음을 증명했다.

:$r\_4(N)\; \backslash leq\; C\backslash frac\{N\}\{(\backslash log\; N)^c\}$

2023년 k=5 및 2024년 k≥5의 경우 Leng, Sah 및 Sawhney는 다음을 증명했다.

:$r\_k(N)\; \backslash leq\; CN\backslash exp(-(\backslash log\backslash log\; N)^c)$

5. 확장 및 일반화

힐렐 퍼스텐버그와 이츠하크 카츠넬슨은 에르고딕 이론을 사용하여 세메레디 정리의 다차원 일반화를 증명하였다. 이후 티모시 가워스, 보이테흐 뢰들과 요제프 스코칸, 브렌든 네이글, 뢰들, 마티아스 샤흐트, 테렌스 타오는 조합론적 증명을 제시했다.

알렉산더 라이브만과 비탈리 베르겔슨은 세메레디 정리를 다항식 진행으로 일반화하였다. 이는 $A\; \backslash subset\; \backslash mathbb\{N\}$이 양의 상한 밀도를 가진 집합이고 $p\_1(n),p\_2(n),\backslash dotsc,p\_k(n)$가 $p\_i(0)\; =\; 0$인 정수 값 다항식이면, 모든 $1\; \backslash leq\; i\; \backslash leq\; k$에 대해 $u\; +\; p\_i(n)\; \backslash in\; A$인 무한히 많은 $u,\; n\; \backslash in\; \backslash mathbb\{Z\}$가 존재한다는 내용이다. 라이브만과 베르겔슨의 결과는 다차원 설정에서도 적용된다.

세메레디 정리의 유한 버전은 유한체 위의 벡터 공간을 포함한 유한 가산군으로 일반화될 수 있다. 유한체 유사체는 자연수에서의 정리를 이해하는 모델로 사용될 수 있다.

그린-타오 정리는 소수가 임의로 긴 등차 수열을 포함한다는 내용을 담고 있다. 소수는 자연수에서 밀도가 0이므로, 이는 세메레디 정리에 의해 직접적으로 도출되지 않는다.

에르되시 산술 진행에 대한 추측은 세메레디 정리와 그린-타오 정리를 모두 일반화하는 더 강력한 추측이다.

5.1. 캡 집합 문제

$\backslash mathbb\{F\}\_3^n$에서 세메레디 정리의 k=3인 경우의 경계를 얻는 문제는 캡 집합 문제로 알려져 있다.

5.2. 상대적 세메레디 정리

벤 그린과 테렌스 타오는 증명의 일부로, 특정 유사랜덤성 조건을 만족하는 정수의 부분 집합(밀도가 0인 경우 포함)에 적용되는 "상대적" 세메레디 정리를 도입했다. 데이비드 콘론, 제이콥 폭스, 유페이 자오는 더 일반적인 상대적 세메레디 정리를 제시했다.