세메레디의 정리

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

무한형태: A가 자연수집합 ${\displaystyle \mathbb {N} }$의 부분집합이고 이 집합의 밀도가 0보다 크면, 즉 ${\displaystyle \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년 에르되시 팔과 투란 팔이 가설을 세웠고, 세메레디 엔드레가 1975년에 복잡한 조합론적 방법을 이용해 증명에 성공하였다. 힐렐 퓌르스텐베르크가 1977년에 세메레디의 정리를 에르고딕 이론의 문제로 치환하는 놀라운 발상에 착안해 색다른 증명을 만들었다.