세메레디의 정리

세메레디의 정리(Szemerédi's theorem)는 정수의 밀도와 등차수열의 발생의 관계에 관한 조합론적 정수론 정리이다. 이 정리는 다음과 같은 두 가지 형태가 있다.

무한형태 : A가 자연수집합 $\mathbb{N}$의 부분집합이고 이 집합의 밀도가 0보다 크면, 즉 $\limsup_{n\to\infty}\# (A\cap\{1,\ldots,n\})/n > 0$ 이면 A는 임의로 긴 길이의 등차수열을 포함한다.

유한형태 : 임의의 0 < d < 1 와 임의의 자연수 k에 대해서 그에 해당하는 자연수 N(d,k)가 존재하여 다음의 성질을 만족한다 : {1, ..., n}의 부분집합 A의 원소의 갯수가 dN이상이고 n > N(d,k)이면 A는 길이가 k인 등차수열을 포함한다.

물론 무한형태와 유한형태가 동치임을 쉽게 보일 수 있다.

역사

1936년 폴 에르되시와 투란(Turán)이 가설을 세웠고, 세메레디(Szemerédi)가 1975년에 복잡한 조합론적 방법을 이용해 증명에 성공하였다. 퍼스턴버그(Hillel Furstenberg)가 1977년에 세메레디의 정리를 ergodic theory의 문제로 치환하는 놀라운 발상에 착안해 색다른 증명을 만들었다.