세메레디의 정리

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

세메레디의 정리(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년 에르되시 팔투란 팔이 가설을 세웠고, 세메레디 엔드레1975년에 복잡한 조합론적 방법을 이용해 증명에 성공하였다. 힐렐 퓌르스텐베르크1977년에 세메레디의 정리를 에르고딕 이론의 문제로 치환하는 놀라운 발상에 착안해 색다른 증명을 만들었다.