코시-대븐포트 정리(Cauchy-Davenport theorem)

코시-대븐포트 정리(Cauchy-Davenport theorem)는 코시(Augustin-Louis Cauchy)와 대븐포트(Harold Davenport)의 이름이 붙어있는 정리입니다. 더하기 정수론(Additive Number Theory) 혹은 더하기 조합론(Additive Combinatorics)에서  등장하는 기본적이고 중요한 정리 가운데 하나입니다. 수학적으로, 코시-대븐포트 정리는 아래와 같이 표현됩니다.

p가 소수일 때, \mathbb{Z}/p\mathbb{Z}의 공집합이 아닌 부분집합 A,B에 대해 다음 부등식이 성립합니다.

\displaystyle |A+B| \geq \min\{|A|+|B|-1 , p\}

여기서 A+BAB더하기 집합(sumset)으로, A+B:=\{a+b \vert a\in A, b\in B\}로 정의됩니다. 그리고 \mathbb{Z}/p\mathbb{Z}는 크기가 p인 순환군(cyclic group)을 의미합니다. 간단히 “p로 나눈 나머지들의 집합”으로 생각할 수 있습니다.

즉, 쉽게 말해서 코시-대븐포트 정리는 소수 크기의 유한 순환군에서 더하기 집합의 크기가 최소한 얼마 이상은 된다는 내용의 정리입니다. 코시-대븐포트 정리를 증명하기 전에, 코시-대븐포트와 매우 비슷하지만 훨씬 간단한 정리를 소개하겠습니다. \mathbb{Z}/p\mathbb{Z}에서 p가 엄청나게 커지면 사실상 \mathbb{Z}, 그러니까 정수집합과 매우 비슷해집니다. 정수의 부분집합 A, B에 대해서는, 다음과 같은 부등식이 성립합니다.

\displaystyle |A+B| \geq |A|+|B|-1

매우 간단한 정리입니다. 만약 A의 원소를 a_1 < a_2 < \cdots < a_i, B의 원소를 b_1 < b_2 < \cdots < b_j라 한다면, a_1+b_1 < a_1+b_2 < \cdots < a_1 + b_j < a_2 + b_j < \cdots < a_i + b_j이며, 그래서 A+B는 최소한 |A|+|B|-1개의 원소를 가지게 됩니다. 원소 개수에 대한 위 부등식에서 등호가 성립하기 위해서는, AB가 같은 공차를 가진 유한 등차수열(arithmetic progression)이어야 한다는 것도 쉽게 확인할 수 있습니다.

코시-대븐포트 정리는 방금 보였던 간단한 정리와 거의 같은 꼴인데, 대신 |A+B|가 전체 집합의 크기인 p보다 클 수 없기에 하한이 \min\{|A|+|B|-1 , p\}와 같이 주어집니다. 방금 전에 정수의 부분집합에 대해 보였던 간단한 정리는, 원소의 크기 비교를 통해 쉽게 증명 할 수 있었던 반면, 코시-대븐포트 정리는 \mathbb{Z}/p\mathbb{Z}의 부분집합을 다루기 때문에 좀 더 어려워집니다. [1]을 바탕으로 하여 증명을 소개합니다. (참고로 아래 증명에서 A-B := \{a-b \vert a\in A, b\in B\}, x+A:= \{x\}+A입니다.)

우선, p \leq |A|+|B|-1인 경우, 즉 |A|+|B|>p인 경우를 생각해봅시다. x\in A+B \Leftrightarrow (x-A) \cap B \neq \emptyset인데, 비둘기집의 원리(pigeonhole principle)에 의해 이는 항상 성립합니다. 따라서 A+B = \mathbb{Z}/p\mathbb{Z} (전체 집합)이며, |A+B|=p가 되어 이 경우 부등식이 성립합니다.

그리고, p > |A|+|B|-1인 경우, |A+B|<|A|+|B|-1인 반례가 있다고 가정해봅시다. A,B가 그런 반례 중에서 |A|가 최소가 되는 반례라고 합시다. 이제, 이 증명에서 핵심이 되는 다이슨 e-변환(Dyson e-transform)이 등장합니다. 어떤 원소 e에 대해, 다이슨 e-변환이란, A,BA'=A \cap (B+e), B'=B \cup (A - e)으로 바꿔주는 변환을 의미합니다. (쉽게 말해, 평행이동을 한 뒤, 교집합과 합집합을 취하는 것입니다.) 그런데, 다이슨 변환의 중요한 성질이, |A'|+|B'| = |A|+|B|면서 A'+B' \subseteq A+B라는 것입니다. 그래서, 만약 A, B가 반례고 A\cap (B+e) \neq \emptyset라면 A', B' 역시 반례가 됩니다. 그런데 아까 |A|가 최소가 되도록 정했고, A' \subseteq A이므로 A' = A여야 합니다. 즉, A\cap (B+e) \neq \emptyset이 성립하는 모든 e에 대해 A \subseteq B+e여야 합니다. A, B가 각각 원소 개수가 2 이상이고, 전체 집합이 될 수도 없으므로, 이것이 불가능합은 쉽게 확인할 수 있습니다. (p가 소수이기 때문입니다!) 따라서 모순이 발생하고, 증명이 끝납니다.

코시-대븐포트 정리는 몇가지 응용이 있는데, 예를 들어 에어디쉬-긴즈버그-지브 정리(Erdős-Ginzburg-Ziv theorem)를 쉽게 증명할 수 있습니다. 코시-대븐포트 정리의 등호조건은 바스퍼의 정리(Vosper’s theorem)로 알려져 있습니다. 또 코시-대븐포트 정리를 유한 가환군으로 일반화 한 것이 크네저의 정리(Kneser’s theorem)입니다.


참고문헌:

[1] Melvyn B. Nathanson, Additive Number Theory: Inverse Problems and the Geometry of Sumsets, Springer-Verlag


더 읽을거리:

  1. 더하기 정수론에 대해 더 알고 싶다면 Melvyn B. Nathanson의 책을 추천합니다. 코시-대븐포트의 일반화 혹은 이와 관련된 내용은 Additive Number Theory: Inverse Problems and the Geometry of Sumsets이 잘 쓰여 있습니다. 같은 저자의 다른 책으로 Additive Number Theory – The Classical Bases가 있는데, 이 책은 더하기 정수론을 약간 다른 관점에서 서술하고 있습니다.
  2. Terrence Tao의 Additive Combinatorics 강의노트는 무료로 공개되어 있는데, 이것도 굉장히 재미있어 보입니다.

Advertisements

One thought on “코시-대븐포트 정리(Cauchy-Davenport theorem)

  1. 이 내용을 한국어로 보는 건 여기가 처음인 것 같네요. 영어증명 읽기싫어서 항상 그냥 넘어갔는데ㅋㅋㅋ 잘 읽고갑니다.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s