헤일스-주에트 정리

헤일스-주에트 정리(Hales–Jewett theorem))^[1]는 수학 분야 중 조합론과 관련된 램지 이론의 근본적인 결과 중 하나로, 알프레드 W. 헤일스와 로버트 I. 주에트의 이름을 따서 명명되었다. 이 정리는 고차원 개체가 필연적으로 보여야 하는 어떤 조합적 구조의 정도에 관한 것이다.

정리의 비공식적인 기하학적 설명은 다음과 같다. 임의의 양의 정수 n과 c에 대해, 숫자 H가 존재하여 H차원 n×n×n×...×n 큐브의 셀을 c개의 색으로 색칠할 때, 길이가 n인 한 행, 열 또는 특정 대각선(자세한 내용은 아래 참조)이 모두 같은 색이어야 한다. 즉, n과 c가 고정되어 있다고 가정하면, n-행과 c명의 플레이어를 가진 틱택토 게임의 고차원 다중 플레이어 일반화는 아무리 n이 크더라도, 아무리 많은 사람 c가 플레이하더라도, 그리고 어떤 플레이어가 각 차례를 플레이하더라도, 충분히 높은 차원 H의 보드에서 플레이된다면 무승부로 끝날 수 없다. 표준적인 전략 훔치기 논증에 의해, 두 플레이어가 번갈아 플레이한다면, H가 충분히 클 때 첫 번째 플레이어는 승리 전략을 갖는다는 결론을 내릴 수 있지만, 이 전략을 얻기 위한 실용적인 알고리즘은 알려져 있지 않다.

공식적인 진술

큐브에서의 조합적 선

문자 n개로 된 알파벳으로 길이가 H인 단어의 집합을 WH
n라고 하자. 즉, 길이가 H인 {1, 2, ..., n}의 순서열 집합이다. 이 집합은 정리의 주제인 초입방체를 형성한다. WH
n 상의 변수 단어 w(x)는 여전히 길이가 H이지만, 하나 이상의 문자를 대신하여 특수 요소 x를 포함한다. 특수 요소 x의 모든 인스턴스를 1, 2, ..., n으로 대체하여 얻은 단어 w(1), w(2), ..., w(n)은 공간 WH
n에서 조합적 선을 형성한다. 조합적 선은 초입방체의 행, 열 및 (일부) 대각선에 해당한다. 헤일스-주에트 정리는 주어진 양의 정수 n과 c에 대해, n과 c에 의존하는 양의 정수 H가 존재하여, WH
n를 c개의 부분으로 분할할 때, 전체 조합적 선을 포함하는 부분이 적어도 하나 존재한다고 진술한다.

예를 들어, n = 3, H = 2, c = 2라고 하자. 이 경우 초입방체 WH
n는 표준 틱택토 보드로, 아홉 개의 위치를 갖는다.

11	12	13
21	22	23
31	32	33

일반적인 조합적 선은 단어 2x로, 선 21, 22, 23에 해당한다. 또 다른 조합적 선은 xx로, 선 11, 22, 33이다. (틱택토 게임에서는 유효한 선이지만 13, 22, 31은 조합적 선으로 간주되지 않는다.) 이 특정 경우, 헤일스-주에트 정리는 적용되지 않는다. 틱택토 보드를 두 집합, 예를 들어 {11, 22, 23, 31}과 {12, 13, 21, 32, 33}으로 나눌 수 있으며, 이들 중 어느 것도 조합적 선을 포함하지 않는다 (그리고 틱택토 게임에서 무승부에 해당할 것이다). 반면에 H를 8로 늘리면 (보드는 이제 3⁸ = 6561개의 위치를 가진 8차원이 된다), 이 보드를 두 집합("O"와 "X")으로 나누면, 두 집합 중 하나는 조합적 선을 포함해야 한다 (즉, 이 틱택토 변형에서는 무승부가 불가능하다). 증명은 아래를 참조하라.

헤일스-주에트 정리의 증명 (특수한 경우)

이제 위에서 논의된 특수한 경우 n = 3, c = 2, H = 8에 대해 헤일스-주에트 정리를 증명한다. 아이디어는 이 작업을 헤일스-주에트 정리의 더 간단한 버전 (이 특정 경우에서는 n = 2, c = 2, H = 2 및 n = 2, c = 6, H = 6의 경우)을 증명하는 작업으로 축소하는 것이다. 유사한 방법을 사용하여 수학적 귀납법을 사용하여 헤일스-주에트 정리의 일반적인 경우를 증명할 수 있다.

초입방체 W8
3의 각 요소는 1부터 3까지의 여덟 개의 숫자로 된 문자열이다. 예를 들어 13211321은 초입방체의 요소이다. 우리는 이 초입방체가 "O"와 "X"로 완전히 채워져 있다고 가정한다. 우리는 귀류법을 사용하여 O 집합이나 X 집합 모두 조합적 선을 포함하지 않는다고 가정할 것이다. 이러한 문자열의 처음 여섯 요소를 고정하고 마지막 두 요소를 변경하면 일반적인 틱택토 보드를 얻는다. 예를 들어 "132113??"은 이러한 보드를 제공한다. 각 보드 "abcdef??"에 대해 위치 "abcdef11", "abcdef12", "abcdef22"를 고려한다. 이들 각각은 O 또는 X로 채워져야 하므로, 비둘기집 원리에 의해 이들 중 두 개는 같은 기호로 채워져야 한다. 이들 위치 중 임의의 두 개는 조합적 선의 일부이므로, 그 선의 세 번째 요소는 반대 기호로 채워져야 한다 (조합적 선 중 어떤 것도 세 요소가 모두 같은 기호로 채워져 있지 않다고 가정했기 때문이다). 즉, "abcdef"의 각 선택 (6차원 초입방체 W6
3의 요소로 생각할 수 있다)에 대해 여섯 가지 (겹치는) 가능성이 있다.

1. abcdef11과 abcdef12는 O; abcdef13은 X이다.
2. abcdef11과 abcdef22는 O; abcdef33은 X이다.
3. abcdef12와 abcdef22는 O; abcdef32는 X이다.
4. abcdef11과 abcdef12는 X; abcdef13은 O이다.
5. abcdef11과 abcdef22는 X; abcdef33은 O이다.
6. abcdef12와 abcdef22는 X; abcdef32는 O이다.

따라서 우리는 6차원 초입방체 W6
3을 위의 여섯 가지 가능성 각각에 해당하는 여섯 개의 클래스로 분할할 수 있다. (요소 abcdef가 여러 가능성을 충족하는 경우, 임의로 하나를 선택할 수 있다. 예를 들어 위 목록에서 가장 높은 것을 선택한다).

이제 W6
3의 일곱 가지 요소 111111, 111112, 111122, 111222, 112222, 122222, 222222를 고려한다. 비둘기집 원리에 의해 이들 요소 중 두 개는 같은 클래스에 속해야 한다. 예를 들어 111112와 112222가 클래스 (5)에 속한다고 가정하면, 11111211, 11111222, 11222211, 11222222는 X이고 11111233, 11222233은 O이다. 그러나 이제 위치 11333233을 고려하라. 이 위치는 X 또는 O로 채워져야 한다. X로 채워져 있다면, 조합적 선 11xxx2xx는 완전히 X로 채워져 우리의 가설에 모순된다. 대신 O로 채워져 있다면, 조합적 선 11xxx233는 완전히 O로 채워져 다시 우리의 가설에 모순된다. 마찬가지로 W6
3의 위의 일곱 요소 중 다른 두 개가 같은 클래스에 속한다면 마찬가지이다. 모든 경우에 모순이 있으므로 원래 가설은 거짓이어야 한다. 따라서 완전히 O 또는 완전히 X로 구성된 조합적 선이 적어도 하나 존재해야 한다.

위의 논증은 다소 낭비적이었다. 사실 H = 4에서도 같은 정리가 성립한다.^[2] 위의 논증을 n과 c의 일반적인 값으로 확장하면, H는 매우 빠르게 증가한다. c = 2 (2인 틱택토에 해당)일 때조차 위의 논증에서 주어진 H는 아커만 함수만큼 빠르게 증가한다. 첫 번째 원시 재귀 함수 경계는 사하론 셸라흐의 결과이며,^[3] 일반적인 헤일스-주에트 수 H = H(n, c)에 대해 여전히 가장 잘 알려진 경계이다.

다른 정리와의 연결

위 논증은 또한 다음의 따름정리를 제공한다. 모든 자리가 1, 2, 3인 여덟 자리 숫자의 집합을 A라고 하자 (따라서 A는 11333233과 같은 숫자를 포함한다). 그리고 A를 두 가지 색으로 색칠하면, A는 길이가 3인 십진법 표기법으로 된 등차수열 중 하나를 포함한다. 이 등차수열의 모든 요소는 같은 색이다. 이는 헤일스-주에트 정리의 위 증명에 나타나는 모든 조합적 선이 십진법에서 등차수열을 형성하기 때문이다. 이 논증의 더 일반적인 공식화는 헤일스-주에트 정리가 반 데르 바르던의 정리를 일반화한다는 것을 보여주는 데 사용될 수 있다. 실제로 헤일스-주에트 정리는 훨씬 더 강력한 정리이다.

반 데르 바르던의 정리에 세메레디의 정리라는 더 강력한 밀도 버전이 있는 것처럼, 헤일스-주에트 정리에도 밀도 버전이 있다. 이 강화된 버전의 헤일스-주에트 정리에서, 전체 초입방체 WH
n를 c개의 색으로 색칠하는 대신, 주어진 밀도 0 < δ < 1을 가진 초입방체 WH
n의 임의의 부분 집합 A가 주어진다. 이 정리는 H가 n과 δ에 따라 충분히 크다면, 집합 A는 필연적으로 전체 조합적 선을 포함해야 한다고 말한다.

밀도 헤일스-주에트 정리는 원래 퓌르스텐베르크와 카첼슨이 에르고딕 이론을 사용하여 증명했다.^[4] 2009년에 폴리매스 프로젝트(Polymath Project)는 코너스 정리(corners theorem) 증명에서 나온 아이디어를 바탕으로 밀도 헤일스-주에트 정리의 새로운 증명을 개발했다.^[5][6] 도도스, 카넬로풀로스, 티로스는 Polymath 증명의 간소화된 버전을 제시했다.^[7]

헤일스-주에트 정리는 그레이엄-로스차일드 정리에 의해 일반화된다. 이 정리는 고차원 조합적 큐브에 관한 것이다.