math – 페이지 2 – Pseudorandom Things

Non-cooperative games and prisoner’s dilemma

2016년 11월 8일2020년 5월 8일Hhan댓글 2개

현동훈교수님의 대수기하학 개론 수업의 한 작은 토픽으로 존 내쉬(John Nash)의 논문 비협력 게임(Non-cooperative games)을 읽게 되었습니다.

비협력 게임은 수학에서 최고의 저널로 치는 annals of mathematics에 실린 논문입니다. 내쉬는 이 논문을 통해 노벨 경제학상을 받았다고 합니다. 사실 수학적으로는 어렵거나 한 내용은 아닙니다. 유명한 수학자(이자 컴퓨터공학자이기도 하고, 이것저것 많이 하신) 폰 노이만(Von Neumann)은 내쉬의 결과를 “trivial”하다고 평가하기도 했습니다.

하지만 당연히 좋은 논문입니다. 수학자들에게 내쉬의 최고의 업적을 물으면 여러가지로 분분히 갈리겠지만, 일반적으로는 분명히 위대한 논문이고, 8000번 넘게 인용이 된 게임이론의 한 획을 그은 논문임은 분명합니다.

이 논문은 다음과 같이 요약됩니다 : 서로 협력 없는 게임에서 각자가 전략들을 잘 선택한 상태가 있어서, 그 상태에서 어떤 한 사람이 전략을 바꾸면 그 사람이 항상 손해를 보는 상태가 존재합니다. 즉, 비협력 게임에는 내쉬 균형점(Nash equilibrium point)이 항상 존재합니다.

과연 이게 무슨 말일까요? 이제부터 알아봅시다.

계속 읽기 →

Dreams of Mathematics Students

2016년 10월 31일2020년 5월 8일Hhan댓글 남기기

수학을 공부하는 학생들은 항상 계산을 하기 싫어합니다.(저만 그럴 수도 있습니다만.) 그래서 다음과 같은 “꿈”을 주장하곤 합니다.

$(x+y)^n = x^n + y^n$
[Freshman’s Dream]

물론 이런 식이 항상 참일리가 없습니다. 우리는 이항전개라는 결과를 교과서에서 수도 없이 많이 배우고 써왔습니다. 그런데, 꿈은 이루어진다고들 하죠. 가끔 Freshman’s Dream이 참이 되는 경우가 있습니다! 바로 $x,y$ 가 characteristic p인 field $F$ 의 원소이고, p가 n의 약수일 때죠. 여기서 field의 characteristic이 p란 말은 임의의 원소를 p번 더하면 0이 된다는 말입니다. Freshman’s Dream은 학부의 현대대수학 수업에서 배울 수 있습니다.

당연히 수학을 공부하는 학생들은 이것으로 만족할 수 없습니다. 다른 편한 결과를 찾고 싶습니다. 그러한 꿈은 다음과 같은 재미있는 식으로 달성됩니다.

$\displaystyle \int_0^1 \frac{1}{x^x} dx = \sum_{n=1}^{\infty} \frac{1}{n^n}$
[Sophomore’s Dream]

참 예쁜 식입니다. 증명은 해석학적인 약간의 지식이 필요합니다만, 약간의 갭을 허용하면 미적분학정도의 지식으로도 확인은 가능합니다.

풀이는 위키피디아에서 보실 수 있습니다.

재미있는 Topology 문제

2016년 10월 27일2020년 5월 8일Hhan댓글 남기기

카페 At PANINI에서 공부를 하던 도중, 친구 L의 질문

질문1 : 왜 클라인 병이 두 개의 뫼비우스의 띠의 합인가? 와 왜 클라인 병이 두 개의 뫼비우스의 띠와 하나의 보통 띠(꼬이지 않은 띠)의 합인가?

(클라인 병과 뫼비우스의 띠의 띠는 링크를 참조하시면 됩니다.)

을 받았습니다. 여기서 띠는 벨트처럼 생긴 넓이는 있지만 부피는 없는 친구라고 생각합시다. 뫼비우스의 띠는 한 번 꼬인 띠겠지요.

그에 대한 대답은 (대수)위상을 이용해서 할 수 있지요. 그림 1의 큰 사각형에서 각 변의 같은 화살표들을 같은 방향끼리 붙도록 잘 합쳐주면 클라인 병이 되고, 그걸 위에 그려진 선을 따라 자르면 진한 회색은 보통의 띠가 되고, 옅은 회색과 흰색은 각각 뫼비우스의 띠가 됩니다. 진한 회색부분을 없애면 두 개의 뫼비우스의 띠의 합으로 만들 수 있겠지요. 그런데, 정말일까요?

물론 정말입니다.. 단, up to homeomorphic으로 말이죠. 그런데 보통은 클라인 병을 생각하면 4차원에 embedding시킨 모습을 상상하는데, 음… 거기서도 옳은 말일까요? 위에서 찾은 보통 띠가 사실은 2번 꼬여있는 띠는 아닐까요?

질문2 : 임의의 homeomorphic한 두 띠는 3차원에 아무렇게나 넣어도 homotopic 할까요? 4차원에서는 어떤가요?

(비전공자를 위한 설명 : 홀수 번 꼬인 띠는 그 경계선이 하나의 원이 되고, 짝수 번 꼬인 띠는 그 경계선이 두 개의 원이 되어 서로 같은 모양으로 만들 수 없음을 알고 있어요. 그렇다면 임의의 홀짝성이 같도록 꼬인 띠들은 3/4차원에서 정말 같은 띠일까요?)

이러한 궁금증이 생겨 같이 공부하고 있던 P와 토론한 결과 다음과 같은 질문들을 생각하고 (많은 대수위상의 문제들이 그렇듯이, 약간은 rough하게) 해결했습니다.

질문3 : 3차원에서 꼬여있는 두 끈(그림 2 참조 : 넓이가 없는 닫힌 곡선)을 4차원에 자연스럽게(그러니까 4번째 축의 좌표가 모두 0이게) 넣으면 과연 이 두 끈은 homotopic하게(그러니까 적당히 늘리고 옮겨가면서) 꼬임을 풀 수 있을까요?
임의의 끈들이 꼬여있는 것은 어떨까요?

질문4 : 그렇다면 4차원에서 뭔가가 꼬일 수 있을까요? 예를 들어 3차원 구의 면과 끈이 꼬이는게 가능할까요?

대수위상을 배웠는데도 이런 내용을 잘 모르네요 ㅎㅎ. 아마 일반적인 얘기가 있을 것 같네요. 호모토피그룹과도 조금 관계가 있을까요?

[추가]
아무래도 이 이야기 자체가 호모토피의 시작과도 같지않을까, 라는 생각이 들었습니다. 내용 대부분이 호모토피그룹을 그대로 구하면 되는거니까요.

How to compute greatest common divisor fast?

2016년 10월 26일2020년 5월 8일Hhan댓글 남기기

임의의 자연수는 소인수분해가 유일하고, 크기순서가 잘 주어져 있기 때문에, 다음과 같은 greatest common divisor를 정의할 수 있습니다.

(Definition)For two positive integer $a,b$ , the greatest common divisor $g$ is the largest positive number that divides $a,b$ without remainder.

짧게는 $\gcd(a,b)$ 로 씁니다. 다르게는 정수 $x,y$ 에 대하여 $ax+by$ 의 음아닌 최솟값으로 정의할 수도 있지요. 수학을 전공하지 않은 분들도 이를 계산하는 다음 유클리드 알고리즘은 한 번씩 교과서에서 보셨을 것 같습니다.

[Algorithm] ${\rm Euclidean-Gcd}(a,b)$
input : $a,b \in \mathbb{N}$
output : $\gcd(a,b)$

If $b>a$ , return ${\rm Euclidean-Gcd}(b,a)$ .
If $b=0$ , return $a$ .
Otherwise return ${\rm Euclidean-Gcd}(b,a\mod b)$ .

이 알고리즘은 시간이 얼마나 걸릴까요? $a,b$ 가 n bit size정도 되는 경우 $O(n^2)$ 정도의 시간복잡도를 가짐을 증명할 수 있습니다.

$\gcd(a,b)$ 의 계산방법은 유클리도 알고리즘이 가장 쉽고 좋은 방법일까요? 그렇다면 이런 글을 쓸 필요도 없고, 질문을 할 필요도 없었겠지요. 유클리드 알고리즘은 3번 과정에서 $a \mod b$ 의 연산을 필요로 하고, 이 연산 때문에 시간복잡도에 곱하기 항이 생기게 됩니다. 우리가 더하기나 빼기는 좀 잘하는데, 곱하기, 나누기는 글쎄요… 이를 피하기 위한 다음과 같은 알고리즘도 있습니다.

[Algorithm] ${\rm Binary-Gcd}(a,b)$
input : $a,b \in \mathbb{N}$
output : $\gcd(a,b)$

If $b>a$ , return ${\rm Binary-Gcd}(b,a)$ .
If $b=0$ , return $a$ .
If $a$ and $b$ are both even, retrun $2 \cdot {\rm Binary-Gcd}(a/2,b/2)$ .
If $a$ is even and $b$ is odd, return ${\rm Binary-Gcd}(a/2,b)$ .
If $a$ is odd and $b$ is even, return ${\rm Binary-Gcd}(a/2,b)$ .
Otherwise return ${\rm Binary-Gcd}((a-b)/2,b)$ .

Binary-gcd는 유클리드 알고리즘과 달리 나누기 연산을 피해갔습니다. Asymptotic time complexity는 같습니다만, 실제 알고리즘은 조금 더 빨리 작동합니다. 그렇다면 이게 최적의 알고리즘일까요? 물론 아닙니다!

계속 읽기 →

Mihăilescu’s Theorem

2016년 10월 25일2020년 5월 8일Hhan댓글 남기기

혹은 Catalan Conjecture라는 이름으로도 알려져 있습니다. 2002년에 Mihăilescu가 증명을 완료한 것으로 알고 있는데, 간단하게 말해 연속한 거듭제곱수는 8=2^3과 9=3^2밖에 없다는 정리입니다. 정확하게 말하면 다음과 같겠죠.

[Mihăilescu’s Theorem/Catalan’s Conjecture]

$x^m-y^n=1$ 을 만족하는 자연수 해 $(x,y,m,n)$ 은 $(3,2,2,3)$ 으로 유일하다.

이렇게 간단한 문제가 21세기가 되도록 풀리지 않았습니다! 사실 정수론의 큰 문제인 골드바흐의 추측이나 쌍둥이 소수 추측이 정말 수년 전에 크게 진전을 이룬 것이나 수학자들을 한참을 괴롭힌 페르마의 마지막 정리가 최근에 증명된 것을 생각하면.. 뭐 그럴수도 있겠다, 싶습니다.

이 정리의 증명에는 정말 많은 수학적 진보가 얽혀 있습니다(혹은 그런 것처럼 보입니다). 오일러가 $x^2-y^3 =1$ 의 해가 $(3,2)$ 로 유일한 것을 보이는 데에 타원곡선의 아이디어를 적용했고, $m,n$ 중 하나가 2인 나머지 경우는 Gaussian integer 등의 quadratic integer와 관계가 있습니다. $m=2$ 인 경우의 증명은 LLL lattice reduction으로 유명한 Hendrik Lenstra가 증명을 하기도 했다는군요. 증명을 마무리한 Mihăilescu는 이 Lenstra의 제자이기도 합니다. Mihăilescu가 마무리 한 나머지 경우는 cyclotomic extension과 관계가 있는 것 같은데, 아직 증명을 읽어보지는 않았습니다. 여유가 나면 읽어보겠는데.. 사실 그것보다 영어공부를 먼저 해야합니다…

여기서는 이와 관련된 올림피아드 스타일의 문제를 하나 소개해보겠습니다. 사실 저는 Mihăilescu’s Theorem의 보조정리로 알았는데, 실제로 그런지는 잘 모르겠습니다. 아마 거짓인 것 같은데..

$x^2-y^n=1$ 을 만족하는 자연수 $(x,y,n)$ 은 $y$ 은 $n>3$ 일 때 $y$ 의 소인수의 개수가 $n$ 의 소인수의 개수보다 2개 이상 더 많다.

증명은 재미있습니다. Mihăilescu’s Theorem에 따르면 해가 없으니 아무 것도 말하지 않는 명제지만. 올림피아드 스타일의 증명은 개인적으로 참 좋아하는 증명입니다. 나중에 혹시 기회가 되면 소개를 드리도록 하고.. Mihăilescu’s Theorem과 관계된 conjecture를 하나 소개하고 이 글을 마치도록 하죠.

임의의 자연수 $N$ 에 대하여 $x^m-y^n=N$ 의 자명하지 않은 자연수 해는 유한하다.