저번 언젠가 T_n을 number of trees on [n]이라 할때 다음 항등식이 성립한다고 햇다.

난 올림피아드를 하지 않앗는데도 Schur란 이름이 올림피아드나 경시문제 쪽에서 이름이 많이 들린다.

정확히 어떤 분야를 햇는지는 몰라도 대단한 사람인듯.

여튼 Schur는 다음을 증명햇다.

모든 자연수 n>1와 충분히 큰 prime p에 대해

를 만족하는 nontrivial root (x,y,z)가 항상 잇다. FLT의 합동식 버전처럼 보인다.

보통 2차일 땐 일반적인 꼴은 Hilbert symbol의 도움을 받아서 해결할 수 잇다(더 나아가서 일반적으로 n개의 변수에 대해, 정수해가 잇는지 없는지 판별해주는 알고리즘이 잇다. n이 5이상일때는 정수해가 항상 잇엇던가...)

(Actual) Schur`s theorem

다시 본론으로 돌아가서, 집합 를 n개로 분할하자. 만약 어떤 a,b,c가 하나의 분할안에 있어서 a+b=c를 만족하면 이를 Schur triple이라 부른다. 그러면 모든 자연수 n에 대해, [S(n)]를 n개의 클래스로 어떻게 분할하든 Schur triple이 존재하게 하는 S(n)이 존재한다.

증명은 Ramsey thm의 간단한 응용. n개의 분할하는 것을 n개의 색으로 칠한다고 생각한다. complete graph K_k의 edge를 n개의 색으로 칠할때 단색 삼각형이 존재하게 되는 k가 항상 잇다. 이러한 k를 고정하고, vertex set [k]를  로 색칠한다. 다시 edge set 에 edge (i,j)를 로 coloring한다. k의 choice에 따라, 단색 삼각형 (m,n,l)이 잇고 이때 a=n-m, b=l-n, c=l-n로 놓으면 증명 끝.

이 정리를 이용하면 저 위의 nontrivial root의 존재성은 multiplicative group 의 subgroup 으로 생성되는 coset들을 생각함으로써 corollary로 따라온다.

자동차가 1부터 n까지 잇고 주차구역 1부터 n까지 잇다. 각 자동차 i는 선호구역 p(i)가 잇다. 자동차 1부터 n까지 차례대로 들어간다. 만일 자신의 구역 p(i)가 비어잇으면 그곳에 주차하고 이미 주차되잇으면 다음자리 p(i)+1이 비어잇는지 조사하고 또 차잇으면 또 넘어가고 이런 식으로 모든 차가 주차한다. 만약 n개의 차가 모두 주차에 성공하면 이때 p를 parking function (on [n])이라 한다.

이제부터 하려는 것은 parking function on [n]과 rooted forest on [n]사이의 bijection을 만드는 것이다.

parking function 881233146이 잇다고 하자(예를 들면 p(5)=3). 얘네들은 각각 891234567로 주차가 가능하다.

하나 주목할 것은 만약 아무도 자리 1을 선호하지 않으면 절대 parking function이 될수없다. 그럼 이제 1의 개수가 대응될 forest의 component의 개수라 보고 1을 좋아하는 애를 root라 하는 것이 자연스럽다.

예에서 1을 좋아하는 애는 3과 7.

그다음 2를 좋아하는 애를 조사한다. 여기서 생각할 것은 만일 2가 없고 3부터 쭉 잇다면 3 이상인 수들은 1들과 independent하기 때문에 첫번째 root에다가 3부터 다 달아버리면 될 것이다. 2는 1에 영향을 받으니(2를 좋아하는 애가 3 1 두개때문에 밀려서 3에 주차한다) 두번째 root에 4를 달아버린다.

계속 이런 원리로 recursively 구성해나가면 된다. 계속 해보면 3을 좋아하는 애가 5와 6인데 얘네 둘은 2에 영향을 받진 않는다(받긴 받지만 이는 1을 좋아하는 애들때문에 오는셈이다). 그러니 4밑에 5와 6을 단다. 4를 좋아하는 8이고 얘는 3이 두개이기 때문에 한번 더 밀린다. 따라서 두번째로 3을 좋아하는 애인 6밑에 8을 단다. 5를 좋아하는 애는 없고, 6을 좋아하는 9번차를 보면 얘는 7에 앉는다. 근본적으로 1 좋아하는 애들때메 영향을 받은 것이기에 첫번째 3을 좋아하는 5번차 밑에 단다. 7 좋아하는 애는 없고, 8 좋아하는 1번 2번 차는 각각 구역 8, 9에 주차한다. 기존의 1때문에 아무런 영향을 받지 않은 것이니 첫번째 1을 좋아하는 3번 차 밑에 1과 2를 달아버리면 끝.

만약 rooted forest가 주어지면 위 알고리즘을 토대로 이에 대응하는 parking function을 만들수 잇다.

이거 푼다고 꽤 오래 걸렷는데 이게 저번 조합개론 기말 기출이다 ㅡㅡ

따라서 #parking function on [n] = #rooted forest on [n]

그리고 #rooted forest on [n] = #trees on [n+1](둘 사이에 자연스러운 bijection이 잇다)

#trees on [n+1]은 Cayley formula에 의해 (n+1)^(n-1)개 잇으므로 #parking function on [n] = (n+1)^(n-1)

만약 parking function을 Cayley formula에 의존하지 않고 따로 셀수잇다면 Cayley formula를 증명하게 되는 셈이다.

수학자 Pollak은 이를 다음과 같이 counting하엿다.

주차구역이 1부터 n까지 잇으면 가상의 자리 n+1을 하나 더 만든다. 만일 n+1을 좋아하는데 n+1에 자리가 차잇으면 다시 1번 자리를 조사하는, 원형 구조를 띠게 규칙을 정한다. 이렇게 되면 [n]에서 [n+1]으로 가는 (n+1)^n개의 모든 function은 주차가 가능하다. 자리가 하나씩 비게 되는데 이 빈자리가 n+1일 확률은 정확히 1/(n+1)이다. 따라서 우리가 구하고자 하는 parking function의 개수는 (n+1)^(n-1).

이건 정말 확률론을 이용한 우아한 증명 중의 하나이다. 확률론이 가지는 힘은 정말 큰 듯하다. 눈에 정확히 보이지는 않지만 주어진 구조나 object들의 행동패턴를 이용하여 counting을 하고 어떨 때는 극한값을 계산하기도 하고 존재성을 증명하기도 한다. 확률론도 우아한 매력을 지닌듯하다.

다음은 대한수학회 kms에서 퍼온 것이다.

(http://www.kms.or.kr/board/list.html?num=2468&start=0&sort=top desc,main desc,reg_dt desc&code=notice&tcode=&key=&keyword=)

-

2014년 8월 13일부터 21일까지 서울 코엑스에서 열리는 세계수학자대회(International Congress of Mathematicians, ICM)에 한국인 수학자 6명이 기조강연자와 초청강연자로 선정되었습니다.

선정되신 분들께 축하의 말씀을 드립니다.

   <기조강연>
         - 황준묵 교수(고등과학원)

   <초청강연>
         - 김병한 교수(연세대학교, Section 1-Logic and Foundations)
         - 강석진 교수(서울대학교, Section 2-Algebra)
         - 김범식 교수(고등과학원, Section 4-Algebraic and Complex Geometry)
         - 이기암 교수(서울대학교, Section 10-Partial Differential Equations)
         - 하승열 교수(서울대학교, Joint Section-Mathematical Physics(Section 11)
                                            & Mathematics in Science and Technology(Section 17))

이번에 한국인 수학자가 세계수학자대회의 기조강연자로 선정된 것은 사상 처음이며,
또한 한 대회에 한국인 초청연사가 5명씩이나 선정된 것도 우리나라 수학의 위상을 반영하는 매우 경사스런 일입니다.

-

특히 기조강연의 황준묵 교수님은 변형불변성에 대해서 연구한 공로로(당연히 먼진 모르겟지만) 이미 2006 ICM에서 초청강연을 하신 바 잇다(2014년도 예정된 분들을 제외하면 ICM에서 강연하신 한국인 수학자는 황준묵 교수님을 포함해 총 3명)

우리학교에도 한 번 오셔서 Mathclub에서 강연을 하신 적이 잇다 그때 들엇는데 본인은 주로 침대에 누워서 기하학을 한다고 하신다 ㅋㅋ 하버드 대학원생시절에 complex manifold에 심취햇다고 하신다 기억에 남는 어구는 '눈 먼 화가'

수학계에는 수학을 하는 나라를 다섯 개의 그룹으로 분류한다 그룹5이 제일 수학강국으로 미국 러시아 헝가리 등등이 잇다 우리나라가 그룹2에 잇엇는데 2000년대로 오면서 그룹4로 승격햇다 이렇게 한번에 두단계나 승격하는 경우는처음이라고 한다

실제로 위원회단장님이신 박형주 교수님도 이 점을 강조해서 서울로 유치하는데에 성공하신거라 한다

다른 선진국에 비하면 국내에서는 수학계에 대한 인식이 부족하다고들 하는데 정말 이 말이 사실이라면 위 같은 성취를 계기로 수학을 바라보는 분위기가 바뀌엇으면 하는, 그저 수학을 공부하는 학부생으로서, 바램이 잇다

여튼 한국수학의 위상을 드높이는 한국 수학자들이 존경스러울 뿐이다.

Hilbert는 그 유명한 1900년도 파리 국제수학자대회에서 23개의 중요한 문제들을 발표하엿다

그중 3번째 문제가 다음과 같다

부피가 같은 두 다면체에 대하여, 하나를 유한개의 조각으로 자른 뒤에

이들을 붙여 다른 하나를 만드는 것이 항상 가능한가?

이에 Hilbert의 제자 Dehn이 몇 개월도 채 안되서 그렇지 않다는 증명을 내놓고

그 증명에서 쓰인 개념이 Dehn invariant다

주로 어떤 상태에서 다른 상태로 바뀔수 없음을 보일때

불변량, 즉 그 상태가 가지고 잇는 고유한 값을 찾아서 증명한다

이 이외에 방법론은 들어보지 못햇다

다면체 P가 잇다고 하자

과 는 -vector space이고 이 둘의 tensor product를 생각한다 이제 P에 대해 Dehn invariant를 라 정의한다 저 summation은 P의 edge를 돌고, l(e)은 e의 길이, 알파(e)는 e의 이면각을 말한다

저 양이 cut and paste에 관해서 불변량임을 보이는 것은 어렵지 않다

로 분할됏다고 하면 임을 증명하면 된다

만약 우변의 edge가 기존의 P의 것이라면 그대로 냅두고 나머지 edge, 자르는 과정에서 생긴 edge과 관한 tensor 곱이 0임을 보이면 충분하다 edge가 P의 face를 자를때 생긴 것이라면 우변에서 이면각을 더한 합이 pi가 되고 edge가 P 내부에서 생긴 것이면 우변 이면각의 합이 2*pi가 되어 에서 0이므로 증명끝.

그럼 이제 반례를 부피가 같은 cube C와 tetrahedron T로 둔다

C의 모든 edge에 대해 이면각은 1/2*pi이므로 Dehn 양은 zero. T의 모든 edge에 대해 이면각은 arccos(1/3)인데, (1/pi)*arccos(1/3)은 무리수이므로(당연히 증명이 필요하다) Dehn 양은 nonzero

따라서 변환할 수 없다

비슷한 문제로 넓이가 같은 두 직사각형이 잇을때, 하나를 유한개의 직사각형으로 잘라 붙여서 다른 하나를 만드는 것이 항상 가능한가? 를 생각해볼수 잇는데 이도 Dehn 불변량 비슷한 아이디어로 풀린다(저 개념을 알고잇음에도 쉽지는 않앗다) 만약 유한개의 삼각형으로 자를수잇다고, 사각형에서 삼각형까지 허용한다면, 항상 바꿀수 잇다

division ring은 모든 nonzero element가 역수를 가지는 좋은 ring이다

대표적 예로 field가 잇고 field가 아닌 예로는 사원수가 잇다

제목이 말하는 바는 division ring이 finite하다면 무조건 field일수밖에 없다는 것이다

처음으로 증명한 사람은 Wedderburn thm으로 유명한 Wedderburn(세가지 증명을 제시햇다고 한다 ㅎㄷㄷ)이고 여기서 소개할 증명은 학부 수준의 algebra로 이해할수 잇는 Witt의 증명이다

우선 finite division ring R의 nonzero set 는 그 ring의 곱셈에 대해서 group을 이룬다(강ㅋ력ㅋ)

다시 zero를 포함한 ring에서 에 대해s의 stabilizer를 라 하고 를 R의 center라 하자

Z는 field를 이룬다. size를 q라 하자 R과 C_s는 Z를 base field로 해서 vector space를 이룬다(vector space 공리확인같은게 중요하다고 느끼는 요즘이다. 일단 된다고 합시다. 머 체크하는 것도 어렵지 않을테니) 여기서 각 dimension을 n, n_s라 하자

R이 field가 아니라고 가정하면 어떤 s에 대해서는이다. s를 포함하는 conjugacy class를 라 하자 그러면 이고 우리의 가정은 어떤 s에 대해서 라는 것이다

orbit-fixer counting formula에 의해, 모든 s에 대해

이고 이는 정수이다

원소를 두개 이상가지는 conjugacy class를 라 하자. 가정에 의해 t는 1 이상이다

class equation를 써보면

       또는       

을 이용하면 모든 i에 대해 n_i는 n을 나눈다(같지 않음도 쉽게 안다)

자 이제 을 n번째 cyclotomic polynomial이라 하자(정의와 기본적인 성질은 이쪽 참고, n-th root of unity를 공부하는데 많이 쓰이는 다항식이다)

이 다항식들은 놀랍게도 모두 정수계수 다항식들이다 정의에 의해 이다

증명을 위해 더 나아가면, 모든 i에 대해

따라서

         and        

class equation으로부터

하지만 이럴 수는 없다

왜냐하면 R과 Z에 다르다는 가정에서 n>1이고 따라서 의 각 product term들의 절댓값은 q-1보다 크기 때문이다. 기하학적으로 생각하면 쉽다(아직 블로그 포스팅 스킬이 부족해 그림까지는...쿨럭)

이로써 증명 끝.

다른 분야의 용어가 하나로 섞이면 먼가 아름답다는 느낌을 주는데 이것도 그렇다

앞으로 할 증명은 기본 토대만 주면 그리 어렵지는 않다

우선 전체 집합을 정수집합으로 하고

basis를 양쪽으로 뻗어나가는 등차수열의 집합으로 준다(여기서 공차는 nonzero)

즉 open set들은 저런 basis들의 arbitrary union로 정의된다

topology를 이루는 이유는 먼저 등차를 1로 놓으면 전체집합이 나오고

두 등차수열의 intersection은 공집합이거나 두 공차의 lcm을 공차로 갖는 등차수열의 집합이기 때문이다

여기서 노트할 것은 한 등차수열집합은 (당연히) open이면서 closed인 것이다

그리고 모든 nonempty open set은 infinite set이다

자 이제 소수가 유한하다고 하고 를 0을 포함하고 등차가 p인 수열집합이라 하자

절대값이 1보다 큰 각 정수는 소수의 유한곱으로 표시된다(가 UFD이기 때문...)

(이 사실은 소수가 무한히 많고 안많고랑은 무관하다)

따라서 는 플러스 마이너스 1 뿐이다(여기서 union은 가정에 의해서 finite union)

그러나 저 union은 closed set의 finite union이어서 closed이다

따라서 그 complement는 open이므로 무한집합이어야 하는데 플러스마이너스 1은 그렇지 않다 모순!

여기서 말은 위상이라고 햇지만 소수의 무한성 다른 증명을 보다보면 비슷한 원리를 이용햇을 듯한 느낌을 받을것만 같다

출처 : Proofs from THE BOOK

A를 n by n skew-symmetric matrix, Pf(A)를 A의 Pfaffian(정의는 이쪽 참고)이라 하자

그러면 다음이 성립한다

굉장히 놀랍지 않은가!

Pfaffian의 정의에서도 보듯이, 만일 각 성분들이 문자들이엇다면 determinant는 그 문자들의 다항식의 제곱으로 나타난다는 것이다

더군다나 Pfaffian은 조합론에서도 쓰인다

정의에서 보면, 두개씩 짝지은것이 꼭 그래프에서 perfect matching을 연상시키게 하고

역시 matching을 조사하는데 쓰인다

이 모두는 다 Lovasz책에 소개되어 잇다

(정말 좋은책이라 생각한다. 저자가 헝가리 수학자로 조합론의 대가라고 한다...ㅋㅋ)

이 책의 특징은 서너문제가 하나의 스토리로 연결되어 잇는게 굉장히 많다는 것이다

(스토리를 천천히 따라가다 보면 왠만해선 풀수잇다)

여기에서도 스토리가 잇는데 저 위의 파격적인 등식을 증명하는게 스토리의 시작이다

시작부터 매우 골때린다 ㅋㅋㅋ증명하는데 하루를 넘기고 이틀 넘어가기전에 증명햇던거 같다

여튼 스토리의 끝은 다음과 같다

2n by 2n 체스보드를 두칸까지 블럭으로 채우는 경우의 수를 이라고 햇을때 다음이 성립한다

따라나오는 것으로 의 증가속도를 estimate할수 잇다

저 값이 구체적으로 무엇인지는 적분시도를 안해봐서 모르겟지만

적어도 상수인건 아니까 머...

코사인이 왜 나오는지는 chebyshev polynomial(참고)의 eigenvalue를 조사하면 된다

그나저나 위에 쓰여진 식들이 마구잡이로 쓴 식들이 아니라

다 조합론적으로 의미가 잇는 살아잇는 식들이라 참 놀랍고 아름답다고 느낄 뿐이다

Selberg sieve method와 그 응용에 관한 거엿는데

완전히 elementary한데 못봐오던 논리로 전개를 해나간다...

어떻게 -parameter를 정의할 생각을 햇지...

임의의 에 대해서 성립하기 때문에 조절할 여유가 생긴다

엄청나게 독창적이다 ㅋㅋ

(참고로 Selberg는 elementary한 방법으로 소수정리를 증명하여 필즈상을 받앗다)

그 응용도 약간 소수정리를 떠올리게끔 하는 문제엿다

문제 자체만 써보면 이렇다(출처는 Lovasz책)

충분히 큰 에 대하여 수열 안에 잇는 소수의 개수가

G를 simple digraph on labeled n-set, 변이 m개 잇다고 하고

n by m 행렬 A을 G의 incidence matrix라고 하자

여기서 n번째 row를 제거한 것을 , 라 하자

그러면 Matrix Tree theorem이 말하는것은

the number of spanning trees of the underlying graph of G가 라는 것이다...

여기서 생각해 볼점은 왜 n번째 row를 빼는가이다

증명은 Cauchy Binet formula의 직접적인 도움을 받는다

굉장히 놀랍지 않은가.

이로써 꽤 대칭적으로 정의되는 그래프들의 spanning tree의 개수를 determinant로도 생각해볼수 잇게 되엇

예를 들어 이라 하고 각 선분의 방향은 임의로 주어졋다고 하자 그러면 spanning tree의 개수는

가 된다. 여기서 행렬의 size는 n-1 by n-1이 되겟다

이 행렬의 determinant는 무엇인가?

row operation으로도 어렵지 않게 구할수 잇으나 eigenvalue를 이용해 구해보자

이렇게 대칭적으로 정의된 matrix를 eigenvector와 eigenvalue로 분석하는 것은 자주 쓰이는 테크닉이다

먼저 n-1 by 1 column vector 는 eigenvalue를 1로 갖는 eigenvector이다 그리고 n-2개의 column vector는 eigenvalue를 n으로 가지고 서로 linearly independent하다 따라서 determinant는 가 나오고 Cayley`s formula가 증명이 된다