math – Pseudorandom Things

2021년의 아벨상 수상자: László Lovász와 Avi Wigderson

2021년 3월 21일Hhan댓글 남기기

아마 이 블로그의 독자들이라면 다른 경로를 통해 들었겠지만, (필즈상과 더불어) 수학의 노벨상이라고도 불리는 2021년 아벨상 수상자가 이론적 컴퓨터과학에 종사한 라슬로 로바스(László Lovász)와 아비 위그더슨(Avi Wigderson)으로 결정되었다. 아벨상 홈페이지와 Quanta 기사가 아주 좋은듯.

Quanta 기사에 인용된 Russell Impagliazzo 교수님의 말에 따르면 로바스는 수학의 입장에서 컴퓨터과학에, 위그더슨은 컴퓨터과학의 입장에서 수학에 영향을 주었다고 한다. 물론 서로 엄청난 영향을 주었지만.

내가 아는 대표적인 업적들을 정리해보면, 우선 로바스 교수님은

격자(Lattice)의 꽤 짧은 basis를 찾는 Lenstra-Lenstra-Lovász, 소위 LLL algorithm의 저자이다. 이 알고리즘의 따름정리로 임의의 유리수계수 다항식이 다항식시간 내에 인수분해가 됨을 증명했다. 정수의 소인수분해가 아직도 해결되지 않은 문제이고, 암호의 기반으로 쓰이는 것과 비교하면 좋다. 또한 이 알고리즘은 격자기반 암호나 다른 여러 암호의 분석에 여전히 잘 쓰이고 있다.
확률론적인 방법으로 어떤 조합적 대상의 증명을 보이는 확률론적 방법에서, 특히 여러 조건이 dependent할 때 존재성을 보이는 유일한 방법인 Lovász Local Lemma, 또다른 LLL을 제안하고 증명했다. 둘 다 LLL으로 불리는게 꽤 재밌다. 요즘에도 제목에 LLL으로 많이들 나온다 둘 다 -_-..
또한 Semidefinite Programming이나 Random walk, 초창기 버전의 PCP 정리에 기여하신듯.

위그더슨 교수님은 좀 더 컴퓨터과학 문제에 많이 접근하셨다. 예를 들어

확률론적으로 다항식시간에 해결되는 문제의 집합인 BPP와 결정론적으로 해결되는 P의 관계에 많이 연구했다. 특히 특정한 가정 하에 BPP와 P가 같다는, 다항식 시간의 문제들에는 확률론적 알고리즘이 도움이 되지 않을것이라는 Derandomization에 관한 여러 결과를 냈다.
P=NP을 증명하는게 어려운 이유중 하나인 Algebrization을 제안하였다.
마찬가지로 PCP정리에 기여하시고, 그래프의 Zig-Zag product나 expeander graph, 암호학적으로는 pseudorandomness나 Zero-knowledge proof에 많이 기여하셨다고.

라마누잔의 “가장 쉬운 공식”

2020년 11월 19일2021년 1월 16일Hhan댓글 한 개

John Baez 교수님의 블로그 Azimuth에 흥미로운 식이 올라와서 한번 요약해본다. 오랜만이 수학글 ㅋ

π는 3보다 약간 크고, e는 3보다 약간 작다. 그 평균은? 기하평균은 다음과 같다.

$\sqrt{\pi e}= 2.92228236...$

식 자체로는 딱히 흥미로워보이지 않는데, 라마누잔이 1914년 The Journal of the Indian Mathematical Society에 다음 식의 증명을 묻는 퍼즐을 냈다고 한다.

$\displaystyle \left(\frac 1 1 + \frac 1 {1\cdot 3} + \frac1{1 \cdot 3 \cdot 5} + \cdots\right) + \frac 1{1+\frac 1{1+\frac 2{1+\frac 3{1+ \frac 4{1+ \frac 5{\ddots}}}}}} = \sqrt{\frac{\pi e}2}$

와 그냥 뭔가 싶다 -_-!! 이것이 바로 어릴 때 매료되었던 수학의 아름다움이 아닌가 ㅋㅋㅋ 라마누잔이 하디에게 자신을 처음 소개하는 글에 이 식도 있었다고.

John Baez 교수님은 이 식을 라마누잔의 “가장 쉬운 공식” (Ramanujan’s easiest formula)이라고 불렀다. 이 글에서는 이 식의 간략한 증명을 다루고자 한다.

계속 읽기 →

정다면체는 48개 있다

2020년 8월 22일2020년 8월 22일Hhan댓글 한 개

우리는 초~중학교때 쯤 정다면체가 정사면체, 정팔면체, 정십면체, 정십이면체, 정이십면체의 5개가 있다고 배운다. 그리고 그 사실을 “증명”까지 했던 것 같다! 굉장히 빈약한 논리이긴 했지만 ㅋ. 하지만 아래 유튜브 영상에 따르면 사실 정다면체가 48개나 있다고 한다!!!

그림도 그려가며 아주 재미있게 설명하니 앞부분 일부를 슥슥 뛰어가며 감상하는 것을 추천. 누군가 한글 자막도 달아주었다!!

어릴 때 한 “증명”은 사실 문제가 없고, 그 정의가 엄밀하지 않았던 것에 있다. 우리가 했던 증명을 따르려면 다면체는 항상 볼록이여야할거고, 겹치는 부분이 없고, 어쩌구 저쩌구… 이런저런 조건들이 많이 필요하다. 이 영상에서 (그리고 아마 역사적으로) 고려한 “정다면체”는 각 면이 정다각형인 것보다 약간 일반적인 정의를 생각한다.

우선 정다각형은 각 변의 길이/변 사이의 (방향)각이 같은 것으로 생각한다. 근데 사실 이게 한 점을 “다음” 점으로 옮기면서 다각형의 형태를 유지할 수 있다는 것을 말하는 것이고, 이것을 “정다각형”으로 정의한다.

마찬가지로 정다면체는 임의의 꼭짓점/변/면을 다른 꼭짓점/변/면으로 옮기며 형태를 유지한 변환하는 점/변-추이성이 유지되는 3차원 공간의 다면체로 정의한다. 다면체는 각 변이 정확히 두개의 면의 교집합이여야 하고.

그러면 여기서 새로운 정다면체는 어떤 것들이 있을까? 원래 우리가 아는 정다면체 5개를 먼저 세자.

“별 모양” 같은 것도 사실 정다각형으로 생각할 수 있고, 이걸로 정다면체를 만들 수 있다. (이게 4개라고 한다.)
정삼/사/육각형으로 평면을 가득 채우는 타일링도 사실 저 정의에서는 정다면체가 된다. (3개) 이처럼 공간에 무한히 뻗어가는 다른 정다면체들도 여러개 있다. (이런게 3개 더 있다고 한다)
사실 정다면체가 정다각형인 면으로 이루어 질 필요가 없다는 것을 관찰하면 (이름과는 조금 다르지만…….), 각 “면” 비슷한 것이 정다각형의 각 변을 꼬아서 만든 것으로 만들어서, 새로운 15개의 정다각형을 만들 수 있다고 한다.
이 다음부터는 더욱 더 복잡해지는듯 한데, 여러가지 테크닉, 예를 들어 정사각형을 위상수학에서 원의 covering space R을 생각하듯이…. 쭉 늘려서 새로운 3차원상의 정다각형을 만들고 이를 이용하는 방식으로 새로운 18개의 정다각형을 만들수 있다고 한다.

말로 설명하는 것보다 동영상이 훨씬 재밌을듯 하다. 그림을 그려주는 것에서 확실히 좋다 ㅎㅎ.

임의의 평면위의 닫힌단순곡선, 혹은 Jordan curve에 대해서 그 위에 네 점을 적당히 잘 잡아서 정사각형을 만들수 있는지 묻는 문제가 바로 내접하는 정사각형(Inscribed square problem), 혹은 Square peg problem 등으로 불리는 문제이다. 혹은 Toeplitz’ conjecture로 부르기도 하는데, 이 문제는 Otto Toeplitz가 1911년 제안했다고 한다.

그런데 Herbert Vaughan가 1970년대 후반에 임의의 Jordan curve위의 직사각형이 있다는 결과를 밝히기 전까지 큰 진전이 없었고, 아직까지 굉장히 어려운 문제로 남아있다. Vaughan의 증명은 위상수학을 아주 멋지게 사용하는 간결한 방식인데, 딱히 출판하지는 않고 렉쳐노트로만 남아있는듯 하다. 그나마 최초의 남은 레퍼런스는 이거인거같은데, 여기서도 Vaughan의 1977 렉쳐를 인용하며 (?)표시를 남겨두었다 ㅋㅋㅋ. 3Blue1Brown의 아래 동영상과 Zariski님의 관련글에서 이 풀이를 소개하기도 했다. 몇 년 전에는 테렌스 타오도 시도를 해서 주어진 Jordan curve가 두개의 특정한 Lipschitz curve로 나누어지는 경우에 증명을 한듯.

3Blue1Brown, Who cares about topology? (Inscribed rectangle problem)

그런데 놀랍게도 이 내접하는 정사각형 문제가 임의의 부드러운(smooth) Jordan curve에 대해 풀렸다는 Quanta Magazine의 소식. 평소의 Quanta 글보다 좀 긴것 같은데, Arxiv에 올라온 그 풀이가 굉장히 짧고 방향성을 이해할만하기 때문인가보다. 심지어 정사각형 뿐만 아니라, 두 변의 길이의 비를 임의로 잡아도 그와 닮은 직사각형이 똑같이 내접한다고 한다!

저자인 조슈아 그린(Joshua Greene)과 앤드류 롭(Andrew Lobb)은 COVID-19때문에 락다운상태에 있다가 이 문제를 풀기로 결정한듯 ㅋㅋㅋ 나는 집에있으면 놀기만하게되던데…

여튼 위 Vaughan의 접근과 새로운 접근을 아주아주 간략하게 설명하면 곡선을 삼차원에 넣는 하나의 방법인 다음 embedding을 생각하는 것이다.

곡선위의 임의의 두 점에 대해 (중점의 x좌표,중점의 y좌표,두 점 사이의 길이)를 좌표로 갖는 점들을 모두 찍는다 (*)

그리고 이렇게 embedding한 3차원상의 곡면의 성질을 살피는 것.

이것을 2018년 프린스턴의 Cole Hugelmeyer라는 학생이 2018년 위 Vaughan의 embedding을 4차원으로 확장시키는 방식을 생각했는데, 대충 말해서 마지막 좌표로 각 두 점을 잇는 선분의 각을 포함하는 것이다. 이런 embedding을 생각하면 특정한 비율을 갖는 직사각형만 고려할 수 있게되고, 이 아이디어와 원래 Vaughan이 했던 위상수학적 아이디어를 합쳐서 두 변 사이의 비가 $1:\sqrt 3$ 인 특정한 직사각형이 내접함을 보였다.

또 2019년 같은 저자가 이 embedding을 더 잘 분석해서, 임의의 Jordan curve가 (대각선과 한 변이 이루는 각에 따른 measure에 대해) 1/3정도의 직사각형을 항상 포함하는것도 보였다는 결과도 냈다.

그러면 마지막으로 그린과 롭의 새로운 결과는? 거의 비슷한 embedding을 생각하는데, symplectic 구조를 보존하도록 (즉 symplectomorphism이 되도록) 약간 변경한다고 한다. 그리고 Möbius Strip 대신 Klein Bottle에 관한 논증을 한듯. 그러면 쉽게 풀린다는데….. 자세히는 모르겠다 ㅋㅋㅋ Hugelmeyer의 두 논문과 새로운 논문 모두 아주 짧으니 궁금하면 한번 보는것도 추천.

2020/6/29 P와의 얘기 이후 약간 추가: (맨 마지막 전까지 Möbius Strip얘기가 없어서..)

Vaughan의 증명을 좀 더 자세히 적으면, (*)에 정의된 함수는 곡선위의 두 점을 R^3로 보내는 함수이다. 근데 “곡선위의 두 점”은 위상수학적으로 보면 사실 (x,x), 즉 Jordan curve위의 점들이 경계가 되는 Möbius Strip이 된다. (Ordered 두 점이 $S^1 \times S^1$ 이 되는것을 생각하고, 여기서 order를 없애면 된다.)

근데 이 map의 이미지는 $\mathbb R^2 \times \mathbb R^+_0$ , 즉 z좌표가 0 이상이 되고 z=0인 부분은 정확히 Jordan curve가 된다. 즉, 문제는 Möbius Strip을 반공간에 넣으며, Möbius Strip의 경계가 반공간의 경계에 있도록 하는것이 가능하느냐의 문제. 근데 이것은 불가능함이 잘 알려져 있다. 조금 더 자세하게 보자면, Möbius Strip의 경계와 중간선은 R^3에 embedding했을 때 꼬여있는데, 이 중간선을 생각하면 z좌표가 음수인 부분이 있어야한다.

큰 숫자들 by Scott Aaronson

2020년 6월 1일2020년 7월 23일Hhan댓글 2개

이 글은 스콧 아론손(Scott Aaronson)이 블로그에 쓴 글 Big Numbers를 번역한 것이다. 아론손은 Festivaletteratura이라는 이탈리아에서 매년 열리는 축제에서 큰 수에 관한 이야기를 했고, 이를 다시 글로 정리했다고 한다. 이 글은 1999년 아론손이 스스로 쓴 글과도 많이 겹치는데, 집합론이나 논리학등 새로운 몇 부분을 추가했다고 한다. 가장 번역이 어려웠던 부분이다 -_-.. 하루를 꼬박 다 썼네. 혹시 이런쪽에 익숙한 분들중 자연스럽지 않은 부분을 발견하신 분은 말해주세요.

Festivaletteratura는 굉장히 특이한 문학축제인데, 문학 뿐만아니라 다양한 다른 분야의 사람들을 불러서 소규모 강연회를 개최하나보다. 신기하군..

계속 읽기 →

Playing pool with psi

2020년 5월 20일2020년 6월 26일Hhan댓글 한 개

3Blue1Brown에서 소개되어서 유명해진 충돌을 통해 pi를 계산하는 방법. 유닼님의 블로그에도 소개된적이 있다.

쉽게 말하면 $10^{2n}$ 의 질량을 갖는 공 A와 벽 사이에 $1$ 의 질량을 갖는 공 B를 두고, A를 B방향으로 이동시키면 마찰력이 없고 완전탄성충돌일 때 충돌횟수가 $pi$ 의 소숫점 $n$ 번째 자리까지 정확히 같다는것. 즉, A의 질량이 $M$ 일 때,

(충돌횟수) $= [\pi\sqrt{M}]$

이 된다는 것이다. 이게 Playing pool with \pi라는 논문의 결과.

근데, 혹시 양자알고리즘에 관심이 있다면 Grover algorithm이라는 것을 들어봤을 것이다. Indexing이 되어있는 데이터 $A=\{a_i\}_{1\le i \le N}$ 이 있을때 원하는 데이터 $x$ 를 $A$ 에서 찾는 문제가

고전적으로는 $a_i$ 를 하나하나 다 봐야하니 $\Omega(N)$ 번 데이터를 봐야하지만,
양자컴퓨터로 $\sum |a_i\rangle$ 처럼 데이터를 superposition의 형태로 보는것을 허용하면 데이터에 $\Theta(\sqrt N)$ 번의 접근만으로 원하는 데이터를 충분히 높은 확률로 찾을수 있다는것.

Grover search가 가장 좋은 알고리즘인것도 알려져 있다. 근데 Grover algorithm의 분석을 잘 살펴보면 데이터베이스 접근이

$[\frac 1 4 \pi \sqrt{N-1}]$

번일때 최적이 된다. 이게 신기하게 위의 충돌횟수와 비슷한데, Playing pool with \psi라는 논문에 따르면 이런 유사함이 우연이 아니라, Grover algorithm과 저 충돌 시뮬레이션 사이에 어떤 일종의 isomorphism이 존재한다는것.

(혹시 양자계산에 익숙하지 않은 독자가 있다면.. quantum state는 $\sum_x \alpha_x |x\rangle$ 으로 쓰는데, 사실 이건 $\sum_x |\alpha_x|^2=1$ 이 성립하는 unit vector $(\alpha_1,...,\alpha_N)$ 으로 볼 수 있고, 얘에 대한 Unitary operation만으로 계산을 진행하다 마지막에 measurement를 통해 $x$ 를 각각 $|\alpha_x|^2$의 확률로 얻는것이라고 이해하면…. 아래 설명은 이해할수 있을지도 모른다 -_-..)

Grover algorithm을 아주아주 간략하게 설명하면 다음과 같다.

uniform superposition $|s\rangle = \frac 1 {\sqrt N} \sum_{i=1}^N |i\rangle$ 을 준비한다. 우리가 찾고자하는건 $|x\rangle$ 이라 하자.
$s$ 에 대한 reflection $U_s=2|s\rangle \langle s|-I$ 를 적용한다.
$x$ 에 대한 reflection $U_x=2|x\rangle \langle x| - I$ 를 적용한다. (결과는 $|x\rangle$ 의 계수만 부호가 반대로 바뀐다.)
2,3의 과정을 $T=\frac 1 4 \pi \sqrt{N-1}$ 번 반복하고 measurement를 해서 결과를 본다.

이해가 가지 않을텐데, 설명을 대충한것이니 어쩔수없다 -_-…

여기서 저자가 발견한 isomorphism은 다음과 같다. 우선 충돌 실험에서 공을 A,B 두개만 둘것이 아니라 질량이 모두 같은 $1,...,N$ 번의 번호를 붙인 $N$ 개의 공을 두고, $N-1$ 개의 공을 A위치에 겹쳐서 두고, 하나의 공( $=x$ 번)만 B의 위치에 두자는 것. 그리고 $N$ 개의 공의 현재 속도가 $(v_1,...,v_N)$ 이 될것이다. 근데 운동에너지는 보존되므로

$v_1^2 + ....+v_N^2$

은 상수이고, 이걸 1이라고 둘 수 있다. 이 다음에 이런 quantum state를 생각하자.

$\sum_x v_x |x\rangle$

그러면 공 A가 B와 부딪히는것은 사실 $U_s$ 에 해당하고, B가 벽과 부딪히는것은 $U_x$ 에 해당한다는 것. 특히 $U_x$ 가 $|x\rangle$ 의 부호만 바꿨다는것을 기억하면 꽤나 그럴듯하다.

이런 관점에서 Grover algorithm과 위 충돌실험은 처음 state만 다를뿐, 완전히 같은 실험이라는것. 굉장히 신기하다.

이거 쓰다가 알게되었는데, $\LaTeX$ 코드와 링크삽입이 충돌해서 줄이 바뀌게 되는것같다 -_-…. 어떻게 해결 안되나?

The probability that two random integers are relatively prime.

2017년 2월 13일2020년 5월 8일Hhan댓글 한 개

영어공부를 하다 심심해서 오랜만에 기억나는 다음 정리를 다시 한번 증명해봤습니다.

(Theorem) The probability that two random positive integer are relatively prime is $1/\zeta(2)=6/\pi^2$ .

아래의 증명은 (아마도) Niven책[1]에서 처음 본 것 같습니다. 조금 다르더라도 이런 방식의 정의와 증명을 처음 본 건 Niven이 맞으니까 뭐 저기서 인용했다고 칩시다.

계속 읽기 →

A toy problem

2016년 12월 30일2020년 5월 8일Hhan댓글 남기기

얼마전에 (크리스마스날!) 학원 수업 대타를 하루 했습니다. 이제 다시는 학원수업을 하지 않을줄 알았는데.. 오랜만에 올림피아드 문제좀 풀어볼까 하고 잠시 시간을 내어 수업을 했습니다. 그런데 그 전후로 너무 바빠서 생각보다 힘들었습니다..

그날 수업을 위해 준비한 문제중 다음과 같은 문제가 있습니다.

There are $n$ positive integer $a_1,\cdots , a_n$ , need not to be different, in the blackboard. In each “step”, we can erase two numbers $a,b$ and write greatest common divisor and least common multiple of $a,b$ in the blackboard. The “meaningful step” is a step which change the set of integers in the blackboard.

Prove that the possible number of meaningful steps is finite.
Regardless of the way we do steps, if we cannot do any meaningful steps, the possible set of integers in the blackboard is unique.

원래 문제는 1번만 있었는데, 너무 쉬워서 내지 말까 고민했었습니다. 근데 왠지 더이상 할 수 없는 상태가 유일하지 않을까 싶어서 이리저리 고민해보니 적당한 난이도로 해결이 되고, 재미있는 toy problem인 것 같아서 출제했습니다. 풀이는 비밀로 ㅎㅎ.

요즘의 관심사

2016년 12월 15일2020년 5월 8일Hhan댓글 남기기

요즘은 시험기간이여서 글도 많이 쓰지 못하고, 다른 공부도 거의 하지 못합니다. 기말이 있는 과목은 복소다양체(Complex Manifold)와 대수기하학 개론(Introduction to Algebraic Geometry)입니다. 대수기하학 개론은 Take-home exam으로 시험 문제를 일주일간 푸는 시험이고, 복소다양체는 기말 과제로 각자가 정한 주제로 발표하는 시험입니다.

대수기하학 개론에 대해서는 별로 할 말이 없습니다. 재미있긴 한 과목이지만 요즘 다루는 툴이나 이론들이 그렇게 끌리지는 않아서요.. 그래도 Grobner basis는 참 재미있는 툴인 것 같고, 대수기하 과목이 열리면 듣긴 할겁니다 ㅎㅎ

복소다양체의 기말 과제로는 Kenkichi Iwasawa의 “Sheaves for Algebraic Number Fields”를 읽고 발표하기로 결정했는데.. 좀 웃깁니다. 복소다양체보다 정수론을 매일 공부하고 있습니다. 정확하게는 Weiss의 Algebraic Number Theory 책을 읽고 있는데, 지난번의 포스팅도 그 책에서 발견하고 올린겁니다 ㅎㅎ.
재미는 있습니다만 결국 복소다양체에 대해서는 하나도 배우지 못할 것 같습니다.. 수업도 많이 빠졌고.. TeX파일로 정리해서 파일을 제출하고 발표하는 과제이기에 그 파일을 여기 올리거나, 혹은 전후 문제들과 내용들을 간략하게 정리해서 이 블로그에 올릴 수도 있을 것 같습니다.

시험이 끝나고는 Quantum Computation에 대해 공부해보려고 합니다.
일전에 P. Shor의 Quantum polytime에 Factorization과 Discrete Logarithm을 푸는 논문을 예전에 읽은 적이 있는데, 그 때는 대충 이상한 점들도 넘어갔었습니다. 최근에 이것저것 찾아보면서 다시 읽었더니 빈 곳들이 메꿔지는 느낌입니다. 정말로 양자컴퓨터가 실현화 가능할지는 의문이긴 하지만, 그래도 꽤나 재미있는 주제라 약간은 공부해보려 합니다.

-끝-