세메레디의 정리

3. 역사

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

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

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

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$이다. 하한은 베렌트,^[12] 랭킨,^[13] 및 엘킨의 연구를 기반으로 한 O'Bryant에 의해 제시되었다.^[14][15] 상한은 가워스에 의해 제시되었다.^[9]

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

:$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,^[11]와 블룸과 시삭에 의해 제시되었다.^[23]

''k'' = 4의 경우, 그린과 타오^[25][26]는 다음을 증명했다.

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

2023년 ''k''=5 및 2024년 ''k''≥5의 경우 Leng, Sah 및 Sawhney는 다음을 증명했다.^[27][28][29]

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

5. 확장 및 일반화

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

알렉산더 라이브만과 비탈리 베르겔슨은 세메레디 정리를 다항식 진행으로 일반화하였다.^[36] 이는 $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\}$가 존재한다는 내용이다. 라이브만과 베르겔슨의 결과는 다차원 설정에서도 적용된다.

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

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

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

5. 1. 캡 집합 문제

5. 2. 상대적 세메레디 정리

참조

_[1] 논문 On some sequences of integers http://www.renyi.hu/[...]
_[2] 논문 On certain sets of integers
_[3] 논문 On sets of integers containing no four elements in arithmetic progression
_[4] 논문 Irregularities of sequences relative to arithmetic progressions, IV
_[5] 논문 On sets of integers containing no ''k'' elements in arithmetic progression http://matwbn.icm.ed[...]
_[6] 서적 Springer
_[7] 논문 Ergodic behavior of diagonal measures and a theorem of Szemerédi on arithmetic progressions
_[8] 논문 The ergodic theoretical proof of Szemerédi's theorem
_[9] 논문 A new proof of Szemerédi's theorem http://www.dpmms.cam[...]
_[10] 서적 Proceedings of the International Congress of Mathematicians Madrid, August 22–30, 2006 European Mathematical Society
_[11] 논문 Sets of integers that do not contain long arithmetic progressions http://www.combinato[...]
_[12] 논문 On the sets of integers which contain no three terms in arithmetic progression
_[13] 논문 Sets of integers containing not more than a given number of terms in arithmetical progression
_[14] 논문 An improved construction of progression-free sets
_[15] 서적 Additive Number Theory Springer
_[16] 논문 On triples in arithmetic progression
_[17] 논문 Roth's theorem on progressions revisited
_[18] 논문 Integer sets containing no arithmetic progressions
_[19] 논문 Integer sets containing no arithmetic progressions
_[20] 논문 On Roth's theorem on progressions
_[21] 논문 A quantitative improvement for Roth's theorem on arithmetic progressions
_[22] 간행물 Breaking the logarithmic barrier in Roth's theorem on arithmetic progressions
_[23] 간행물 An improvement to the Kelley-Meka bounds on three-term arithmetic progressions
_[24] 간행물 Strong Bounds for 3-Progressions
_[25] 서적 New bounds for Szemeredi's theorem, II: A new bound for r_4(N) Cambridge University Press
_[26] 논문 New bounds for Szemerédi's theorem, III: A polylogarithmic bound for r₄(N)
_[27] 간행물 Improved Bounds for Szemerédi's Theorem 2024
_[28] 간행물 Improved bounds for five-term arithmetic progressions 2023
_[29] 웹사이트 Grad Students Find Inevitable Patterns in Big Sets of Numbers https://www.quantama[...] 2024-08-05
_[30] 논문 An ergodic Szemerédi theorem for commuting transformations
_[31] 논문 Hypergraph regularity and the multidimensional Szemerédi theorem
_[32] 논문 Regularity lemma for k-uniform hypergraphs
_[33] 논문 Applications of the regularity lemma for uniform hypergraphs http://www.math.emor[...]
_[34] 논문 The counting lemma for regular k-uniform hypergraphs
_[35] 논문 A variant of the hypergraph removal lemma
_[36] 논문 Polynomial extensions of van der Waerden's and Szemerédi's theorems
_[37] 논문 A density version of the Hales–Jewett theorem
_[38] 논문 Finite field models in arithmetic combinatorics—ten years on
_[39] 논문 A relative Szemerédi theorem
_[40] 논문 An arithmetic transference proof of a relative Szemerédi theorem