MPR Ch4

Induction의 도움으로 기대하지도 않은 운이 따라주어서 새롭고도 아름다운 진실들이 수론에서 드러나기도 한다 - 가우스

제 4 장 : 수론에서의 Induction 의 사례

수론에서 Induction이 적용된 두가지 사례를 들어 비교한다. 이를 통해 수학적 발견에서 'Induction'이 차지하는 역할과 위상을 더 구체적으로 이해할 수 있을 것이다. 아울러 Induction 자체에 대해 다시 생각해보는 기회도 될 것이다.

피타고라스 세쌍수(triple)

피타고라스 정리 는 워낙 기초적이고 중요한 정리라 수학의 여러 분야에 영향을 주었다. 그 정리가 수론 분야에 영향을 준 것 중 가장 대표적인 것은 뭐니뭐니해도 피타고라스 세쌍수일 것이다. 피타고라스 정리는 직각삼각형에서 빗변과 나머지 두변의 관계를 정확하게 밝혔다. 그래서 자연수들 셋이 하나의 쌍을 이룰 때 그것이 직각삼각형의 변이 될 수 있는 것과 안되는 것으로 쪼개진다. 피타고라스 세쌍을 이루는 자연수 묶음은 몇개나 되는지 하는 문제와 그것들을 모두 알 수 있는 알고리듬을 찾는 것이 우선 드는 궁금증이다. 이 문제들은 이미 오래전에 풀렸다.^[1] 하지만, 그로부터 새로운 문제들도 따라 나올 수 있는데 그런 사례 중 하나가 아래에서 볼 라그랑쥐의 네 제곱수 정리 다. 우선 직각삼각형의 빗변이 될 수는 있는 수들을 보자. 그 전에 (3,4,5) 와 그것의 배수들인, 그래서 닮은 직각삼각형을 이루는 (6,8,10) , (9, 12, 15) 들과 같은 경우는 우리의 흥미를 끌지 않기 때문에 관심을 기울이지 않을 것이다.

피타고라스 정리로부터 직각삼각형이 될 수 있는 세쌍의 관계는 뻔하다.

c^{2}=a^{2}+b^{2}

이 중 아무 자연수나 한번 찍어서 다른 변들도 자연수일 수 있게 허용하는 빗변이 될 수 있나 보자 ^[2]. 예를들어 빗변이 12 라면?

12^{2}=144=a^{2}+b^{2}

이 참인 자연수 a, b 가 있을까?

144 보다 작은 제곱수를 다 볼 필요는 없다. 두 변 중 하나는 다른 변과 같거나 더 길고 빗변보다는 짧을 것이기 때문에, 일반적으로, $a\leq b\ll c$ 라 놓을 수 있고, 따라서 $144=a^{2}+b^{2}\leq 2b^{2}$ 이며, 이는 곧 $144\leq 2b^{2}$ 또는 $72\leq b^{2}$ 니까. 그래서 남은 후보는 81과 100밖에 없다. 12는 피타고라스 세쌍수 중 직각삼각형의 빗변이 될 자격이 없다. 그렇다면 13은? 된다. $84.5\leq b^{2}$ 이어서 가능한 후보로 100, 121, 144 중 144 가 25와 어울려 되니, 12가 b , 5 가 가장 짧은 변 a가 되면 된다. 좋다. 이런 식으로 처음부터 몇개를 짚어가보면, 우리가 관심을 가지고 있는 수들 중, 20보다 작은, 가능한 빗변들은,

5, 13, 17

이다. 모두 소수다. (소수만 될까?) ^[3] 우리의 관심을 소수에만 집중해보자. 앞의 세 수는 피타고라스 세쌍수 중 빗 변이 될 수 있는데, 이상하게도

3, 7, 11, 19

안 안된다. 이 둘의 심각한 차이는 무엇일까?

피타고라스 세쌍수의 빗변이 될 수 있는 소수는 4n + 1 꼴이다 !

과연 이것은 수를 계속 연장해서 봐도 그렇게 될까?^[4]

라그랑쥐 네 제곱수 정리

피타고라스 세쌍수에 대한 생각을 일반화 하면 궁금한 것이 떠오른다. 세쌍수 개념을 버리는 대신, 제곱수의 합의 개념을 남기고 그것을 일반화해보자.

두 제곱수의 합으로 표현할 수 있는 자연수는^[5] ? 그럴 수 없는 자연수는 ?

세 제곱수의 합으로 표현할 수 있는 자연수는 ? 그럴 수 없는 자연수는? ^[6]

두 개의 제곱수로 표현할 수 없는 자연수는 당장 3이 떠오른다. 6도 안될 것이고 7 도 안된다. 그랬던 3과 6도 1+ 1 + 1 과 4 +1 + 1 로 세 개의 제곱수로 표현해낼 수 있다. 하지만 7은 세 개의 제곱수의 합으로도 표현할 수 없다. 이것을 더 일반화해가면 마침내 중요한 일반적인 정리에 이른다.

'몇 개의 제곱수의 합으로 표현할 때 모든 자연수를 표현할 수 있을까? '

다음을 보자.

1=1,\ 2=1+1,\ 3=1+1+1,\ 4=2+2,\ \dots ,\ 10=9+1,\ 11=9+1+1,\ 12=9+1+1+1,\ 13=9+4,\dots

이와 같이, 이 문제를 최초로 언급한, 바쉐는 직접 합할 제곱수들을 찾아갔다. 325까지 찾아가고 내린 Induction 방법으로 이를 드러냈는데 그 문장은 이렇다. ^[7]

(라그랑쥐 네 제곱수 정리) : 어떤 자연수도 네 제곱수의 합으로 나타낼 수 있다.

이 말을 기호로 쓰면 더 분명해지고 아울러 나중에 우리가 볼 가우스 정리와도 비교해서 보기 쉽다.

\forall N\in \mathbb {N} \exists x_{1},x_{2},x_{3},x_{4}\in \mathbb {N} \ (x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2}=N)

네 홀수 제곱의 합 : 가우스 정리

앞에서는 $N,x_{i}$ 들이 모두 자연수인 경우에 대해 통하는 법칙을 보았다. 이제 범위를 조금 좁혀보자. 다름아닌,

네 제곱수의 합으로 만든 수들만 보기는 보는데, 단 이때 참여하는 수들 모두가 홀수로 제한한다.

어떤 자연수도 네 제곱수의 합으로 나타낼 수 있다. 이제 제곱수로 참여하는 수를 홀수 자연수로 제한 한다면 어떤 일이 일어날까? 당연히 모든 자연수를 나타낼 수 없을 것이다. 조금 작위적이긴 하지만, 식도 아래와 같이 바꾼다.^[8]

\forall x_{1}^{2},x_{1}^{2},x_{1}^{2},x_{1}^{2}\in \mathbb {N} _{odd}\ (4N=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})

이 참인 홀수 N 들을 하나씩 나열해보자.^[9] 참가하는 수들을 쌍으로 묶어 $(x_{1}^{2},x_{2}^{2},x_{3}^{2},x_{4}^{2})$ 로 나타내기로 한다. 먼저 N 이 1 이면 ? (1, 1, 1, 1) , 다음 N 이 3 이면 (1,1,1,3). 이것만 있는 게 아니다. 이 네쌍의 수들의 순서도 고려해보자. 그렇다면 N이 3 일 때 다른 가능한 경우는 (1,1,3,1) , (1, 3, 1, 1) , (3, 1, 1, 1) 이다. N 이 5 면 (1,1,9,9) 가능하다. 물론 9가 둘, 1이 둘 참여하면서 순서를 바꾸는 경우도 모두 고려할 수 있다. 나머지에 대해서는 책 원문의 '표 1' 을 보라. 어떤 흥미로운 사실들을 '뽑아' 낼 수 있을까? 문제는 우리의 관심을 어디에 집중할까에 달려있다.

홀수 N 을 네 홀수 제곱의 합으로 나타내는 경우의 수 와 N 의 관계에 집중하자.

N에 대해 그렇게 표현 가능한 경우의 수를 $\psi (N)$ 으로 나타내기로 한다. 과연 이런 함수 $\psi$ 의 규칙성(알고리듬)을 찾아낼 수 있을까? 차근차근 나열해보자.

$N$	1	3	5	7	9	11	13	15	17	21	23	25
$\psi (N)$	1	4	6	8	13	12	14	24	18	20	24	31

이 표를 봐서는 바로 눈에 들어오는 규칙은 없다. 과연 그럴까? 도대체 무엇이 숨어져 있을까? 이것을 관찰하기 위해 위의 수를 분류해보자. 자연수의 가장 기초적인 분류인 소수와 소수 아닌 것들로 나눠보자. 진하게 써 있는 것이 소수다.

$N$	1	'3'	'5'	'7'	9	'11'	'13'	15	'17'	21	'23'	25
$\psi (N)$	1	4	6	8	13	12	14	24	18	20	24	31

소수들만 보면 규칙성이 금방 그러났다. 다름아닌 N이 p 일 때, $\psi (N)$ 는 p + 1이다 ! 그렇다면 나머지 수들은 ? 소수들의 제곱만으로 이루어진 수들은 어떨까? 그렇다. 소수가 p 일 때 N 이 p^{2} 이라면 $\psi (N)$ 는 p(p+1) 이다 ! 이것들은 무엇을 말하고 있을까? 바로 N 의 약수들을 더한 결과다 ! 과연 나머지 수들에 대해서도 그럴까? 이것들보다 조금 '복잡하게' 구성된 나머지 수들을 보자, 15 나, 21 과 같은 수들을. 그것을 구성하는 소수 p , q 에 대해 약수들을 모두 더하면 (p+1)(q+1) 일 것이다. 정말 그런가? 그렇다 !

지금까지 관찰을 해온 것을 바탕으로 이 관찰 대상들을 관통하고 있는 법칙을 뽑아내면 이렇게 간단한 '일반적' 법칙이 나온다.

홀수 네 제곱으로 합이 4 N 라면, 4 N을 나타낼 수 있는 가능한 경우의 수 $\psi (N)$ 는 N 의 약수들의 합과 같다.

되돌아보기

지금까지 무엇을 해오고 있고 무엇을 얻었나 되돌아보자. 바로 앞의 정리는 가우스 정리로 불린다. 이 성질을 유추해내는데 우리가 해온 것은, 물론, 아직 증명이 아니다. 사실, 증명을 위한 어떤 열쇠도 드러나지 않았다. 다만 '그럴듯한' 짐작을 해본 것이다. 그렇다고 아무런 의미도 없는 것일까, 과연 ? 아니다, 우리는 흩어져 있는 어떤 구체적인 사실들을 모아 그것들 속에 숨겨진 채 관통하는 어떤 '총체적 사실 하나'를 찾아낸 것이다. 그 총체성이 모든 자연수 영역까지 확장될 것이라고 짐작하는 것은 무리일까? 과연 이 성질을 100% 믿을 수 있을까? 아니면 90% ? 도대체 어떤 사실을 '믿는다'라고 하는 것은 무엇일까?

앞에서 우리가 Induction 으로 유추해 낸 사실을 두고 어떤 사람은 더 믿고 어떤 사람은 덜 믿을 수 있다. 그렇다면 그런 '믿음'은 주관적인 것일까? 철저하게 객관적인 것이라면 그것을 평가해서 수치로 환산할 수 있을까? 이미 질문했듯 100 % 또는 90% 와 같은 방식으로? 실제로 말끔하게 해진 증명을 보았다면 더 믿게 될 것이다. 그런데 더 믿기 위해 더 많은 지식이 필요할지 모른다. 이 말은 곧 믿음은 어떤 선행 지식이나 정보에 따라 좌지우지 된다는 것을 뜻한다. Induction으로 얻은 결과와 어느정도의 선행 정보를 평가해서 믿을 수 있는 정도를 수량으로 바꿀 수 있지 않을까? ^[10]

우리의 논의가 바쉐가 했던 추측보다 못할게 사실은 없다. 바쉐의 추측과 우리의 추측을 비교해보면 알 수 있다.

바쉐는 325개의 구체적 사실로부터 추측했지만 우리는 13개의 구체적 사실만 놓고 추측했다.
바쉐의 추측은 네 개 의 자연수의 제곱으로 모든 자연수를 표현할 수 있다고 말했다. 하지만 이 때의 '넷' 은 그뒤에 구체적 사실이 바뀌면 언제든 '다섯'이 될 수도, '여섯'이 될 수도 있다. 하지만 우리의 추측에서는 바뀔 게 없다. ^[11]
바쉐의 추측에서는 어떤 자연수를 합으로 나타낼 수 있는 제곱수들이 하나거나, 둘이거나, 셋이거나, 넷이지만, 여기서는 홀수 하나에 '정확하게' 하나의 값을 정해놓았다.

결론적으로 바쉐의 추정 방식과 우리의 추론을 비교해보면 서로 장단점이 있지, 무엇이 더 믿을 만하고 무엇이 덜 믿을 만하다고는 말할 수 없다.

Note

↑ 이에 대해서는 피타고라스 세쌍수
↑ 이 문제를 아래 문제들과 비교하기 좋게 기호로 나타내보자.
$\forall N\in \mathbb {N} \exists x_{1},x_{2}\in \mathbb {N} \ (N^{2}=x_{1}^{2}+x_{2}^{2})$
↑ 아니다. 이것은 바로 거부할 수 있다. 앞에서 했던 '20보다 작은' 이라는 제약을 넘어서자 마자 바로 알 수 있게 된다. 왜냐하면 (7, 24, 25) 도 피타고라스 세쌍수다.
↑ 그렇다. 페르마는 이 사실을 친구에게 보낸 편지에 썼고 거기에 증명의 밑그림만 그려두었다. 오일러는 이 편지를 바탕으로 증명했고 그 뒤에도 다른 증명들이 나왔다. 페르마-오일러 정리 참고.
↑ 이것을 기호로 쓰면,
$\{N\ |\ x_{1}^{2}+x_{2}^{2}=N,\ x_{1},x_{2},N\in \mathbb {N} \}$
또는
$\forall x_{1},x_{2}\in \mathbb {N} \ \exists N\in \mathbb {N} \ (x_{1}^{2}+x_{2}^{2}=N)$
이 참인 자연수 N.
↑ 본문에서도, 예제 2 에서도 제기한 문제, "이런 수들의 기하학적인 해석을 해보면 무엇을 뜻할까?"
↑ 모든 자연수에 대해 일반적으로 증명한 것은 아니므로 그냥 '바쉐의 추측(가설)' 이라고 부르자. 바쉐는 디오판테스의 '산술'을 최초로 그리스어에서 라틴어로 번역한 사람으로 유명한데 그 책에 이 문제와 헤론의 삼각수 에 대한 언급이 있다. 이 정리는 페르마가 최초로 증명한 것으로 보이나 친구에게 보낸 편지에 밑그림만 나와 있을 뿐이고 오일러도 증명했다고 하지만 완전하게 증명되어 공개된 최초의 증명은 라그랑쥐가 했다. 그래서 보통 라그랑쥐의 네 제곱수 정리 라고 부른다.
↑ 생각해보면 이것이 그렇게 작위적이지도 않다. 제곱수로 참가하는 수들이 모두 홀수 이므로 이 수들은 4의 배수일 테니까. 그리고 홀수들로만 된 수 넷을 제곱해서 합한 수를 4로 나누면 홀 수밖에 나올 수 없을테니까.
Q .과연 모든 홀수들이 다 될까?
따라서 이 문제는 바쉐가 가설을 생각해낸 것을 '뒤집어' 생각하면서 특수화 라고 봐도 된다. 다름아닌 어떤 수를 놓고 그것을 만드는 제곱수들을 생각한 것이 아니라, 더하기에 참가하는 제곱수들를 홀수로 제한하고 그때 만들 수 있는 수들을 생각해보는 방식이라 할 수 있는.
↑ 다시말해 이런 집합.
$\{N\ |\ \forall x_{1}^{2},x_{1}^{2},x_{1}^{2},x_{1}^{2}\in \mathbb {N} _{odd}\ (4N=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\}$
↑ 여기서는 여기서도 f : Inductive result 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \times} Information 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \rightarrow} \mathbb{R} 인 함수적 관계에 대해 말한다고 볼 수 있고, 그럴 때 이런 f를 우리가 과연 추정해 낼 수 있을까라는 질문인 것 같은데... 이 말을 더 확장해가면 '증명'이란 무엇인가? 라는 본질적인 질문까지 간다. 그것을 더 나아가면 '믿는 것' '인식하는 것' 일반에 대해서까지 확장되어 갈 수 밖에 없다.
↑ 하지만 여기서의 논의도 만약 새로운 사실이 '약수들의 합'이라는 정확한 값을 거부한다면 버려야만 한다. 정확하기 때문에 완전히 버려야 하는 사태에 직면하게 된다. 따라서 Induction으로 정확한 어떤 갑을 추정하는 것이 반드시 장점이라고는 할 수 없다.

[1] 이에 대해서는 피타고라스 세쌍수

[2] 이 문제를 아래 문제들과 비교하기 좋게 기호로 나타내보자.
$\forall N\in \mathbb {N} \exists x_{1},x_{2}\in \mathbb {N} \ (N^{2}=x_{1}^{2}+x_{2}^{2})$

[3] 아니다. 이것은 바로 거부할 수 있다. 앞에서 했던 '20보다 작은' 이라는 제약을 넘어서자 마자 바로 알 수 있게 된다. 왜냐하면 (7, 24, 25) 도 피타고라스 세쌍수다.

[4] 그렇다. 페르마는 이 사실을 친구에게 보낸 편지에 썼고 거기에 증명의 밑그림만 그려두었다. 오일러는 이 편지를 바탕으로 증명했고 그 뒤에도 다른 증명들이 나왔다. 페르마-오일러 정리 참고.

[5] 이것을 기호로 쓰면,
$\{N\ |\ x_{1}^{2}+x_{2}^{2}=N,\ x_{1},x_{2},N\in \mathbb {N} \}$
또는
$\forall x_{1},x_{2}\in \mathbb {N} \ \exists N\in \mathbb {N} \ (x_{1}^{2}+x_{2}^{2}=N)$
이 참인 자연수 N.

[6] 본문에서도, 예제 2 에서도 제기한 문제, "이런 수들의 기하학적인 해석을 해보면 무엇을 뜻할까?"

[7] 모든 자연수에 대해 일반적으로 증명한 것은 아니므로 그냥 '바쉐의 추측(가설)' 이라고 부르자. 바쉐는 디오판테스의 '산술'을 최초로 그리스어에서 라틴어로 번역한 사람으로 유명한데 그 책에 이 문제와 헤론의 삼각수 에 대한 언급이 있다. 이 정리는 페르마가 최초로 증명한 것으로 보이나 친구에게 보낸 편지에 밑그림만 나와 있을 뿐이고 오일러도 증명했다고 하지만 완전하게 증명되어 공개된 최초의 증명은 라그랑쥐가 했다. 그래서 보통 라그랑쥐의 네 제곱수 정리 라고 부른다.

[8] 생각해보면 이것이 그렇게 작위적이지도 않다. 제곱수로 참가하는 수들이 모두 홀수 이므로 이 수들은 4의 배수일 테니까. 그리고 홀수들로만 된 수 넷을 제곱해서 합한 수를 4로 나누면 홀 수밖에 나올 수 없을테니까.
Q .과연 모든 홀수들이 다 될까?
따라서 이 문제는 바쉐가 가설을 생각해낸 것을 '뒤집어' 생각하면서 특수화 라고 봐도 된다. 다름아닌 어떤 수를 놓고 그것을 만드는 제곱수들을 생각한 것이 아니라, 더하기에 참가하는 제곱수들를 홀수로 제한하고 그때 만들 수 있는 수들을 생각해보는 방식이라 할 수 있는.

[9] 다시말해 이런 집합.
$\{N\ |\ \forall x_{1}^{2},x_{1}^{2},x_{1}^{2},x_{1}^{2}\in \mathbb {N} _{odd}\ (4N=x_{1}^{2}+x_{2}^{2}+x_{3}^{2}+x_{4}^{2})\}$

[10] 여기서는 여기서도 f : Inductive result 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \times} Information 구문 분석 실패 (SVG를 사용하되 미지원 시 PNG 사용 (브라우저 플러그인을 통해 MathML 활성화 가능): "https://wikimedia.org/api/rest_v1/" 서버에서 잘못된 응답 ('Math extension cannot connect to Restbase.'):): {\displaystyle \rightarrow} \mathbb{R} 인 함수적 관계에 대해 말한다고 볼 수 있고, 그럴 때 이런 f를 우리가 과연 추정해 낼 수 있을까라는 질문인 것 같은데... 이 말을 더 확장해가면 '증명'이란 무엇인가? 라는 본질적인 질문까지 간다. 그것을 더 나아가면 '믿는 것' '인식하는 것' 일반에 대해서까지 확장되어 갈 수 밖에 없다.

[11] 하지만 여기서의 논의도 만약 새로운 사실이 '약수들의 합'이라는 정확한 값을 거부한다면 버려야만 한다. 정확하기 때문에 완전히 버려야 하는 사태에 직면하게 된다. 따라서 Induction으로 정확한 어떤 갑을 추정하는 것이 반드시 장점이라고는 할 수 없다.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]