[퍼온글] 초등학생들의 꿈 - Farey Series

※ 출처 - http://bomber0.byus.net/index.php/2008/04/18/594

 http://bomber0.byus.net/index.php/2008/04/23/613

 http://bomber0.byus.net/index.php/2008/05/08/642

수학에는 Freshman's dream(대학생 1학년의 꿈)이라는 것이 있다. 일반적으로 $(a+b)^n = a^n + b^n$이라는 등식은 참이 아니지만, 표수(characteristic)가 p인 유한체(finite field)에서는 다음의 수식이 성립한다.

\[ (a+b)^p = a^p+b^p \]

이제 초등학교 시절로 돌아가 보자. 초등학생들이 분수의 덧셈을 처음 배울 때, 여러가지 어려운 점들이 등장하게 된다. 통분을 해야 하기 때문이다. 그런데 만약에 아래와 같은 분수의 덧셈이 참이라면 얼마나 좋을까?

\[ \frac{b}{a}\, \oplus \frac{d}{c}\, = \frac{b+d}{a+c} \]

연산 $\oplus$를 잠시 이곳에서는 '초등학생들의 꿈의 분수덧셈'이라고 부르자.

차수(order)가 $n$인 Farey Series $F_n$이라는 것은, $0$부터 $1$사이의 기약분수들 중에서, 분모가 $n$ 이하인 것들을 크기 순서대로 배열한 것이다. $F_n$의 처음 몇 항의 예를 들자면,

\[ \begin{aligned} F_1 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{1}\, \right\} \\ F_2 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{2}\,,\, \tfrac{1}{1}\, \right\} \\ F_3 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{3}\,,\, \tfrac{1}{2}\,,\, \tfrac{2}{3}\,,\, \tfrac{1}{1}\, \right\} \\ F_4 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{4}\,,\, \tfrac{1}{3}\,,\, \tfrac{1}{2}\,,\, \tfrac{2}{3}\,,\, \tfrac{3}{4}\,,\, \tfrac{1}{1}\, \right\} \\ F_5 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{5}\,,\, \tfrac{1}{4}\,,\, \tfrac{1}{3}\,,\, \tfrac{2}{5}\,,\, \tfrac{1}{2}\,,\, \tfrac{3}{5}\,,\, \tfrac{2}{3}\,,\, \tfrac{3}{4}\,,\, \tfrac{4}{5}\,,\, \tfrac{1}{1}\, \right\} \\ F_6 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{6}\,,\, \tfrac{1}{5}\,,\, \tfrac{1}{4}\,,\, \tfrac{1}{3}\,,\, \tfrac{2}{5}\,,\, \tfrac{1}{2}\,,\, \tfrac{3}{5}\,,\, \tfrac{2}{3}\,,\, \tfrac{3}{4}\,,\, \tfrac{4}{5}\,,\, \tfrac{5}{6}\,,\, \tfrac{1}{1}\, \right\} \\ F_7 & = \left\{ \tfrac{0}{1}\,,\, \tfrac{1}{7}\,,\, \tfrac{1}{6}\,,\, {\color{red}\tfrac{1}{5}\,,\, \tfrac{1}{4}\,,\, \tfrac{2}{7}\,},\, \tfrac{1}{3}\,,\, \tfrac{2}{5}\,,\, \tfrac{3}{7}\,,\, \tfrac{1}{2}\,,\, \tfrac{4}{7}\,,\, \tfrac{3}{5}\,,\, \tfrac{2}{3}\,,\, \tfrac{3}{4}\,,\, \tfrac{4}{5}\,,\, \tfrac{5}{6}\,,\, \tfrac{6}{7}\,,\, \tfrac{1}{1}\, \right\} \end{aligned} \]

위 항들을 잘 관찰해 보면, 재미있는 패턴들이 많이 숨어있다는 사실을 알 수 있는데, 오늘은 그 중 한 가지만 언급하고 넘어기로 한다. '초등학생들의 꿈'이라 부를만한 것은 바로 이것이다. "주어진 차수의 Farey series에 등장하는 연속된 세 수를 보면, 가운데 수는 언제나 인접한 두 수의 '초등학생들의 꿈의 분수덧셈'을 통해서 얻어진다." 예를 들어, 위에서 붉은색으로 표시한 세 분수를 보면,

\[ \frac{1}{5}\, \oplus \frac{2}{7}\, = \frac{1+2}{5+7}\, = \frac{3}{12}\, = \frac{1}{4} \]

어느 연속된 세 분수를 택해 계산을 해 보아도 이 결과가 여전히 성립한다. 가히 '초등학생들의 꿈'이라 부를만하지 않은가? 이제 이 사실을 증명해보자. 먼저 아래의 정리가 필요하다.

정리 1.

$F_n$의 인접한 두 분수 $\tfrac{b}{a}\, < \frac{d}{c}\,$ 사이에는 $ad-bc=1$라는 관계가 항상 성립한다.

증명. 먼저 문제를 기하학적으로 해석해 보자. $F_5$의 경우를 예를 들어 설명한다. 먼저 각각의 분수들에 대해, 좌표평면에 다음과 같은 방식의 대응관계 $\frac{y}{x} \leftrightarrow (x,\,y)$를 이용하여 좌표를 찾아 점을 찍는다. 그러면 아래와 같은 그림이 얻어진다.

다음으로 각각의 좌표를 원점과 잇는 선분을 그린다.

그러면 각각의 분수들은 이와 같이 얻어진 직선의 기울기와 같다는 것을 알 수 있다. 또한 인접한 두 분수는 인접한 두 직선으로 나타나고 있다. 이제 왜 인접한 $\tfrac{b}{a} < \tfrac{d}{c}\,$가 $ad-bc=1$를 만족시키는가를 이해해 보자. 예를 들어, $\tfrac{1}{2}\,$과 $\tfrac{3}{5}\,$는 인접해 있는데, $2 \times 3-1 \times 5=1$을 만족시키고 있다. 이 상황을 기하학적으로 이해해보자.

먼저 좌표평면 상에서 세 점 $(0,\, 0)$, $(a,\, b)$, $(c,\,d)$이 그리는 격자삼각형을 생각해보자. (예를 들어 $(0,\, 0)$, $(2,\,1)$, $(5,\,3)$의 경우를 구체적으로 생각해보면 좋을 것이다.) 세 점을 이어서 삼각형을 그리게 되면, 이 삼각형은 그 내부와 경계에 $(0,\, 0)$, $(a,\, b)$, $(c,\,d)$를 제외한 다른 격자점들을 가지고 있지 않다. 이 관찰이 매우 중요하므로, 이것이 왜 참인지, $F_n$의 정의를 가지고 곰곰이 생각해보면 좋겠다.

이제 이 삼각형의 넓이를 $A$라 하자. 또한 삼각형의 내부와 경계에 있는 격자점의 개수를 각각 $I$, $B$라 하면, 픽의 정리(Pick's Theorem)에 의해, 삼각형의 넓이는 다음과 같이 주어진다.

\[ A = I + \frac{B}{2} -1. \]

따라서 삼각형의 넓이는 ($I=0$, $B=3$이므로) $\tfrac{1}{2}\,$가 된다.

한편 이 삼각형의 넓이 $A$를 ($(a,\,b,\,0)$와 $(c,\,d,\,0)$의 벡터곱을 이용하여) 다음과 같이 구할 수도 있다.

\[ A = \frac{|ad-bc|}{2} \]

하지만 문제의 조건에 따라 $ad-bc>0$이므로, 언제나 $ad-bc=1$이 성립한다.

이제 목표했던 대로, 다음의 정리를 서술하고 증명해 보자.

정리 2.

주어진 차수의 Farey series에 등장하는 연속된 세 수를 보면, 가운데 수는 언제나 인접한 두 수의 '초등학생들의 꿈의 분수덧셈'을 통해서 얻어진다.

증명. $F_n$의 인접한 세 수를

\[ \frac{b}{a}\, <\frac{x}{y}\, < \frac{d}{c} \]

라고 하면, 정리 1에 의하여 다음 식들을 얻게 된다.

\[ ax-by=1, \quad dy-bx=1 \]

이제 위 두 식을 서로 빼고 정리하면,

\[ 0 = (ax-by)-(dy-cx) = (a+c)x-(b+d)y \]

따라서,

\[ \frac{x}{y}\, = \frac{b+d}{a+c} \]

즉, 초등학생들의 꿈의 덧셈은 참임을 알 수 있다.