2016 10월 – Pseudorandom Things

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]

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

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

피카츄

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

kakaotalk_20161028_221924701

일본에서 돌아온 이후로 일본에서 구입한 피카츄샤프를 사용한다. 귀여워서 마음에 든다. 한 번 그려보고 싶어서, 몇 번을 그렸는데 기괴한 피카츄만 나와서 슬펐는데 이제 드디어 피카츄같이 생긴게 그려지기 시작한다. 귀여운걸 보고 그리면 약간 마음이 안정되는 것 같다. 가끔 그려야지.

수학 글을 쓰고싶은데, 논문 리뷰나 정리/알고리즘 소개는 쓰는데 시간이 너무 많이 들어서 잘 안하고 있다. 좀 더 여유로우면 좋을텐데.

가을이 왔다

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

퇴근하던 길에서 낙엽이 떨어지는 것을 봤다. 하루종일 무기력했는데 조금 기분이 좋아졌다.

kakaotalk_20161027_214336095 — 집에 오던 길에 찍은 사진; 그 스스로 잎같이 생겨 프랙탈이 생각났다.

눈으로 볼 때는 더 예뻤는데 사진으로 담으니 그와 같지 않아서 조금 슬펐다. 그래도 확대해보니 약간 그림을 그린 것 같은 느낌이 들었다. 이런 느낌의 필터도 있을텐데, 어떻게 만드는지 궁금해졌다. 생각나는 아이디어는 이것저것 있는데 코딩을 안한지 꽤 오래돼서 실제로 어떻게 될지 확인은 할수나 있을지 잘 모르겠다.

재미있는 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$ 의 자명하지 않은 자연수 해는 유한하다.

이는 cyclotomic extension 등을 직접적으로 적용하기 어려워 보이는데.. 쉽지 않은 문제인 것 같습니다.

Reference

Daems, Jeanine. “A cyclotomic proof of Catalan’s conjecture.” (2003): 21-46.

https://en.wikipedia.org/wiki/Catalan%27s_conjecture

중국집 ‘련’

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

아쉽게도 사진이 없습니다..

오늘 친구들과 가볍게 밥과 술을 하려 ‘련’을 방문했습니다. 원래는 일식집을 가려 했지만, 일본풍의 가게들 답게 월요일에는 다들 쉬나봅니다.

음식은 과일탕수육, 물만두, 군만두, 이과두주 1병, 칭따오(작은병) 3병, 사천 굴탕면, 깐풍기를 시켰습니다. 총 가격은 6만 5천원이여서 각각 16000원, 17000원을 냈습니다.

맛있었습니다. 이과두주는 56%의 도수라고 했는데, 그렇게 높은 도수의 술 중에서 이렇게 깔끔하게 마신 술은 굉장히 오랜만인 것 같습니다. 속은 조금 쓰렸습니다만.. 모든 음식과 술을 맛있게 먹었습니다. 위치가 약간 구석이라 아쉽지만, 괜찮습니다. 아주 좋습니다. 다음에는 사진을 찍어야겠습니다.

가격 : 식사 6~8000원, 요리 12000원~
영업시간 : 매일 11:30~22:00, 휴식시간 월~목 15:00~17:00