세메레디의 정리 문서 원본 보기

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

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

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

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

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

{{토막글|수론}}

[[분류:수론 정리]]
[[분류:조합론 정리]]
[[분류:램지 이론]]