라틴방진의응용과 최석정 9 차직교라틴방진 2018. 9.7 KAIST 수리과학과최석정강의실현판식및기념강연회 송홍엽 연세대학교전기전자공학부 1
말하는순서 시작하면서오래전시작된이야기라틴방진의응용최석정의 9차직교라틴방진의특성우리에게남겨진숙제 2
2008 년 5 월연세대학교학술정보원전시회자료 3
Handwritten copy ( 필사본, early 1700?) Library of Yonsei University 갑, 을, 병. ( 정 은소장본없음 ) 4
( 목판본, 1700?) 연세대학교학술정보원 건 ( 갑, 을 ), 곤 ( 병, 정 ) 5
Korean Translate, 2006. [4] 6
(목판본) 연세대학교 학술정보원 7
오래전부터시작된 이야기 8
오래전에 ( 약 300 년전?) 최석정 ( 崔錫鼎 ) (1646 년 ~1715 년 ) 영의정 : 1701-1710 구수략 저술. 1710~1715(??) 마방진을만들기위하여직교라틴방진을생성함 Leonhard P. Euler (1707 년 1783 년 ) 스위스출생. 러시아와독일에서활동. 1715(?) 67 년 (?) 61 년 (?) 1782 논문발표 1776 구두발표 그리고약 60 년후에 9
그리고약 210 여년이흘렀습니다. 송홍엽은 1984 년부터미국 USC 에서 전기과대학원공부를시작합니다. 박사과정지도교수 S.W.Golomb 하바드수학박사 (1957) 이면서 JPL 에서디지털통신의기초를세우고 USC 에부임 (1963) 전기과 / 수학과겸직교수 University of Southern California 1986 년석사졸업사진 Jet Propulsion Lab ~1991 송홍엽 (USC, EE-SYSTEMS 박사과정 ) Solomon W. Golomb 교수 ( 송홍엽지도교수 ) 헝가리수학자 Jószef Dénes (1932-2002) 는 USC 를자주방문 - Latin Squares and Their Applications, 1974 - Latin Squares New Developments in the Theory and Applications, 1991 10
~1993 한상근교수 (KAIST 수학과 ) - 구수략사본 ( 곽도영교수로부터 ) - 한국수학교육학회지 series A 에최석정의 9 차직교라틴방진과마방진에관한내용을발표 11
1994 Dinitz 교수 (U. Vermont) - 아리조나주립대의 Colbourn 교수와함께 CRC Handbook of Combinatorial Designs 을준비시작. - 초판은 1996 년발행 송홍엽 (Senior Engineer at Qualcomm, San Diego) - CRC Handbook of Combinatorial Designs 초판에논문을게재 - Dr. Taylor 추천 12
1997 송홍엽교수 ( 연세대학교전자공학과 ) 독일에서 IEEE ISIT 참석중 Dr. Denes 가찾아와서한국의수학저널에게재된논문한편을찾아달라고요청 한상근교수님의논문을처음접하다 - Dr. Denes 에게발송 - 한상근교수님과최초연락 한상근, " 최석정과그의구수략," 한국수학교육학회소식지, 1998 년 4 월호 Martin BAČA 교수슬로바키아기술대학응용수학과 2002 Dr. Denes (Hungary) has passed away. - 최석정의직교라틴방진에관한내용을공식적으로발표할예정일까 (?) - 이루어지지못하고잊혀짐 13
2005 송홍엽교수 ( 연세대학교전기전자공학부 ) Dr. Dinitz 로부터 CRC Handbook of Combinatorial Designs 2 판을위한논문 update 를요청받음 2 판에 history of combinatorial designs 가추가된것을확인하고 그간의모든기록을정리하여 Dr. Dinitz 에게발송 2007 2008 월간과학동아 8 월호 강석기기자 14
The page of the book (2007) Showing Choi s POLS of order 9 15
The page of the book (2007) showing Choi s birth place and year. 16
2008 H.-Y. Song, Choi's orthogonal Latin Squares is at least 67 years earlier than Euler's, 2008 Global KMS International Conference, 2008. 10. JEJU ICC, KOREA. 2010 2011 송홍엽, Choi's orthogonal Latin Squares is at least 61 years earlier than Euler's, 서울대학교수리과학부 ε강연, 2011년 3월. - 천정희교수초청 - 김도한교수를처음뵙다. 17
2013 김도한교수 ( 서울대수리과학부 ) 대한민국과학기술명예의전당에최석정추천 송홍엽, 최석정선생, 오일러를최소 61 년앞서직교라틴방진을만들다, 대한수학회소식지, 2013 년 9 월호. 송홍엽, 특별기고 : 오일러를앞선최석정의오일러방진, 한국통신학회지, 정보와통신, 2013 년 10 월호. 송홍엽, 한국수학사학회가을학술발표회기조연설, 2013 년 11 월. 2016 송홍엽교수 KBS 스페셜 - 다큐멘터리 2017 송홍엽교수 대한수학회공로상수상 2018 KAIST 수학과 최석정강의실오픈기념워크샵 18
최석정 http://www.genealogy.ams.org/id.php?id=46582 9 차직교라틴방진 L. P. Euler 곽도영 한상근 M. Baca J. Denes 송홍엽 S. Golomb H. Taylor Z. Dinitz 천정희 김도한 김영욱 Handbook of Combinatorial Design, 2 nd edition, CRC Press 2013 과학기술명예의전당추천 19
라틴방진의응용 마방진생성 마방진을생성하는다양한방법중한가지 오일러의 original motivation 이동통신시스템채널코드설계 군통신용코드설계 Tuscan/Florentine 방진 통신시스템의성능극대화 병열접속네트워크스위치설계 컴퓨터시스템의성능 실험설계 자연과학 / 사회과학의다양한실험방법론 스도쿠퍼즐 Recreational game 20
마방진의구성 pp 1 2 3 4 3 4 1 2 4 3 2 1 2 1 4 3 1 2 3 4 4 3 2 1 2 1 4 3 3 4 1 2 Pair of orthogonal latin squares double-diagonal qq 4(pp 1) + qq Magic square (34) 1 6 11 16 12 15 2 5 14 9 8 3 7 4 13 10 row-sum semi-magic column-sum LR-diagonal-sum RL-diagonal-sum Theorem: Such a map constructs a semi-magic square. Sufficient conditions for a magic square are: either both latin squares are double-diagonal or n=odd and one diagonal is constant with (n+1)/2 and the other diagonal is a permutation, for both squares example? 21
월간과학동아, 2008 년 8 월호, 강석기기자 n=odd=9 and two of the four diagonals of the squares are constant and equal to (n+1)/2 = 5 22
이동통신시스템의채널코드설계 Dae-Son Kim, Hyun-Young Oh, and Hong-Yeop Song, "Collision-free Interleaver composed of a Latin Square Matrix for Parallel-architecture Turbo Codes," IEEE Communications Letters, vol. 12, Issue 3, pp. 203-205, March 2008. Interleaver == Scrambler, Permutation 23
군통신용코드설계 Hong-Yeop Song, "Total Number of Tuscan Squares of order n," The R. C. Bose Memorial Conference on Statistical Design and related Combinatorics, Colorado State University, in Fort Collins, Colorado, June 7-11, 1995. Hong-Yeop Song and Jeffrey H. Dinitz, "Tuscan Squares," Part IV, Chapter 48 of CRC Handbook of Combinatorial Designs, edited by Charles J. Colbourn and Jeffrey H. Dinitz, CRC Press, pp. 480-484, 1996. 24
병열접속네트워크스위치설계 transpose Kichul Kim and Viktor K. Prasanna, Latin Squares for Parallel Array Access," IEEE Transactions and Parallel and Distributed Systems, vol. 4, Issue 4, pp. 361-370, April 1993. perfect = both Sudoku and double-diagonal self-orthogonal = orthogonal to transpose doubly self-orthogonal = orthogonal to transpose and also to anti-transpose anti-transpose Theorem For all nn = 22 kk mm 22, kk 22, mm odd, there exists a perfect latin square of order nn 2, which is also doubly self-orthogonal. 25
실험설계 2 blocks CARs Drivers 1 2 3 4 I A B D C II D C A B III B D C A IV C A B D Additives A,B,C,D Box, Hunter, and Hunter, Statistics for Experimenters, Wiley, 2005 Want to see ONLY the difference between additives remove the effect of different CARs and of different Drivers (by averaging out the scores) 2 blocks single latin square 3 blocks POLS (pair). 3 blocks 26
스도쿠퍼즐 France late 19 th. not exactly of this form USA - 1979 by Dell Magazines as Number Place. 건축가하워드간즈 (Howard Garns) 가소개했다. Japan 1984. 니코리사의잡지 < 퍼즐통신니코리 > 에서스도쿠라는이름을붙여수록하면서대중화되었다. 명칭은数字は独身に限る ( 숫자는한번씩만쓸수있다 ) 에서유래했다. 27
최석정 9 차직교라틴방진의특성 28
마방진을생성한다 29
월간과학동아, 2008 년 8 월호, 강석기기자 n=odd=9 and two of the four diagonals of the squares are constant and equal to (n+1)/2 = 5 30
Example of POLS that construct only a semi-magic square, not magic. 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 1 2 3 4 3 4 1 2 4 3 2 1 2 1 4 3 11 2 2 3 3 4 4 23 1 4 4 1 3 2 34 4 3 1 2 2 1 42 3 1 2 4 1 3 4(p-1)+q 1 6 11 16 7 4 13 10 12 15 2 5 14 9 8 3 column-sum = row-sum = 34 = magic constant LR-diagonal-sum = 1+4+2+3 = 10 RL-diagonal-sum = 13+14+15+16 = 58 Sufficient conditions for a magic square are: either both latin squares are double-diagonal or n=odd and one diagonal is constant with (n+1)/2 and the other diagonal is a permutation, for both squares 31
Palindrome 대칭성 32
최석정의 9 차직교라틴방진 5 6 4 8 9 7 2 3 1 4 5 6 7 8 9 1 2 3 6 4 5 9 7 8 3 1 2 2 3 1 5 6 4 8 9 7 1 2 3 4 5 6 7 8 9 3 1 2 6 4 5 9 7 8 8 9 7 2 3 1 5 6 4 7 8 9 1 2 3 4 5 6 9 7 8 3 1 2 6 4 5 1 3 2 7 9 8 4 6 5 3 2 1 9 8 7 6 5 4 2 1 3 8 7 9 5 4 6 7 9 8 4 6 5 1 3 2 9 8 7 6 5 4 3 2 1 8 7 9 5 4 6 2 1 3 4 6 5 1 3 2 7 9 8 6 5 4 3 2 1 9 8 7 5 4 6 2 1 3 8 7 9 Corresponding rows are palindromes. Therefore, one square is a mirror-image of the other 33
Kim & Prasanna 의 직교라틴방진과사실상같다 34
Choi s POLS of order 9 (1715, KOO-SOO-RYAK) for magic square 5 6 4 8 9 7 2 3 1 4 5 6 7 8 9 1 2 3 6 4 5 9 7 8 3 1 2 2 3 1 5 6 4 8 9 7 1 2 3 4 5 6 7 8 9 3 1 2 6 4 5 9 7 8 8 9 7 2 3 1 5 6 4 7 8 9 1 2 3 4 5 6 9 7 8 3 1 2 6 4 5 1 3 2 7 9 8 4 6 5 3 2 1 9 8 7 6 5 4 2 1 3 8 7 9 5 4 6 7 9 8 4 6 5 1 3 2 9 8 7 6 5 4 3 2 1 8 7 9 5 4 6 2 1 3 4 6 5 1 3 2 7 9 8 6 5 4 3 2 1 9 8 7 5 4 6 2 1 3 8 7 9 Kim and Prasanna s POLS of order 9 (1993, IEEE Trans P.D.S) for parallel access 0 1 2 3 4 5 6 7 8 3 4 5 6 7 8 0 1 2 6 7 8 0 1 2 3 4 5 2 0 1 5 3 4 8 6 7 5 3 4 8 6 7 2 0 1 8 6 7 2 0 1 5 3 4 1 2 0 4 5 3 7 8 6 4 5 3 7 8 6 1 2 0 7 8 6 1 2 0 4 5 3 0 3 6 2 5 8 1 4 7 1 4 7 0 3 6 2 5 8 2 5 8 1 4 7 0 3 6 3 6 0 5 8 2 4 7 1 4 7 1 3 6 0 5 8 2 5 8 2 4 7 1 3 6 0 6 0 3 8 2 5 7 1 4 7 1 4 6 0 3 8 2 5 8 2 5 7 1 4 6 0 3 palindromic pair NOT Sudoku singly diagonal (not doubly) Leads to a magic square by the canonical map perfect symmetric pair Sudoku - Any 3 x 3 main window is a permutation. doubly diagonal Leads to a magic square by the canonical map 35
PROOF that Choi s and K&P s are not essentially different Start with this (CHOI) 5 6 4 8 9 7 2 3 1 4 5 6 7 8 9 1 2 3 6 4 5 9 7 8 3 1 2 2 3 1 5 6 4 8 9 7 1 2 3 4 5 6 7 8 9 3 1 2 6 4 5 9 7 8 8 9 7 2 3 1 5 6 4 7 8 9 1 2 3 4 5 6 9 7 8 3 1 2 6 4 5 4 5 3 7 8 6 1 2 0 3 4 5 6 7 8 0 1 2 5 3 4 8 6 7 2 0 1 1 2 0 4 5 3 7 8 6 0 1 2 3 4 5 6 7 8 2 0 1 5 3 4 8 6 7 7 8 6 1 2 0 4 5 3 6 7 8 0 1 2 3 4 5 8 6 7 2 0 1 5 3 4 Row permutation: 0 1 2 3 4 5 6 7 8 3 4 5 6 7 8 0 1 2 6 7 8 0 1 2 3 4 5 2 0 1 5 3 4 8 6 7 5 3 4 8 6 7 2 0 1 8 6 7 2 0 1 5 3 4 1 2 0 4 5 3 7 8 6 4 5 3 7 8 6 1 2 0 7 8 6 1 2 0 4 5 3 Symbol substitution: 1 0 2 1 3 2 4 3 5 4 6 5 7 6 8 7 9 8 End up with this (K&P) Thus, they are NOT essentially different!!! 36
Local(?) 구조를지닌다 37
최석정의 9 차직교라틴방진의 local 구조 5 6 4 8 9 7 2 3 1 4 5 6 7 8 9 1 2 3 6 4 5 9 7 8 3 1 2 2 3 1 5 6 4 8 9 7 1 2 3 4 5 6 7 8 9 3 1 2 6 4 5 9 7 8 8 9 7 2 3 1 5 6 4 7 8 9 1 2 3 4 5 6 9 7 8 3 1 2 6 4 5 1,2,3 A 4,5,6 B 7,8,9 C B C A A B C C A B 38
최석정의 9 차직교라틴방진의 local 구조 1 3 2 7 9 8 4 6 5 3 2 1 9 8 7 6 5 4 2 1 3 8 7 9 5 4 6 7 9 8 4 6 5 1 3 2 9 8 7 6 5 4 3 2 1 8 7 9 5 4 6 2 1 3 4 6 5 1 3 2 7 9 8 6 5 4 3 2 1 9 8 7 5 4 6 2 1 3 8 7 9 1,2,3 A 4,5,6 B 7,8,9 C A C B C B A B A C 39
최석정의 9 차직교라틴방진의 local 구조 51 63 42 87 99 78 24 36 15 43 5261 79 88 97 16 25 34 62 41 53 98 77 89 35 1426 27 39 1854664581 93 72 19 28 37465564738291 38 17 296544569271 83 84 96 75 21 3 12 57 69 48 76 85 94 132231 49 58 67 95 74 86 32 11 23 68 47 59 B A C C A B A C B B C A C B A A B C 3차직교라틴방진 1,2,3 A 4,5,6 B 7,8,9 C B C A A B C C A B A C B C B A B A C 40
우리의숙제는 검색어 최석정 Google - 총 48800 건 급격히증가 Naver 블로그 - 총 2264 건 Naver 지식인 총 759 건질문 기타 미디어동영상 (YTN 싸이언스, KBS, EBS, ) 대학수업의프로젝트보고서 중고등학교수행평가서 Etc 41
우리의숙제는 최석정의 9차직교라틴방진 과관련된주제의연구활동이왕성하게이루어져서국제학회에그결과를발표해야함. 현재전무함. 오히려대만 / 미국의학자들이관심을가지고최석정의 9차직교라틴방진에대한관심을논문으로발표한경우는있음 2014년세계수학자대회에서언급 (?) 그러나 ( 국외 ) 홍보절대부족 최석정과그의저서 구수략 에대한재평가가이루어져야함 공식적수학책 이아니다? 지수귀문도 를포함하여구수략정편에표시된수많은배열에대한심도있는연구가필요함 CS전공자들이석사논문주제로몇건사용함. 그러나, 국가적인차원에서대규모연구그룹을조성할필요있음. 42
Articles related with Choi Seok-Jeong ( 최석정관련자료모음 ) http://coding.yonsei.ac.kr/csj.htm Domestic ( 국내발표 ) 최석정, 구수략 ( 목판본 ), ~1715. < 연세대학교학술정보원국학자료실 ( 중앙도서관 5 층 ), 고서 ( 이춘호 ) 510.95 최석정구 -1 > 최석정, 구수략 조선시대산학총서, 정해남, 허민옮김, 교우사, 2006. 오윤용, 한상근, 최석정과그의마방진, 한국수학교육학회지시리즈 A < 수학교육 >, 1993 년 6 월호. 한상근, 우리나라수학이야기 : 조선시대최석정, 서울대학교수리과학부소식지, 2010 년 12 월. 한상근, " 최석정과그의구수략," 한국수학교육학회소식지, 1998 년 4 월호 강석기, 오일러앞지른최석정 - 직교라틴방진기록한최초의문헌구수략, 과학동아 2008 년 8 월호. 김성숙, 강미경, 최석정의직교라틴방진, 한국수학사학회지제 23 권제 3 호 (2010 년 8 월 ) 21 31. 송홍엽, Choi's orthogonal Latin Squares is at least 61 years earlier than Euler's, 서울대학교수리과학부 ε 강연, 2011 년 3 월, 서울대학교. 송홍엽, 최석정선생, 오일러를최소 61 년앞서직교라틴방진을만들다, 대한수학회소식지, 2013 년 9 월호. 김영욱, 최석정, 17 세기의영의정수학자, 대한수학회소식지 2013 년 9 월호. 송홍엽, " 오일러를앞선최석정의오일러방진," 정보와통신, 한국통신학회학회지, 2013 년 10 월호. 송홍엽, " 오일러를앞선최석정의오일러방진," 한국수학사학회가을학술발표회, 성균관대학교, 2013 년 11 월 23 일. International ( 해외발표 ) L. Euler, Recherches sur une nouvelle espece de quarres magiques (Investigations on a new type of magic squares), presented to the St. Petersburg Academy on March 8, 1776, and published in Verhandelingen uitgegeven door het zeeuwsch Genootschap der Wetenschappen te Vlissingen 9, Middelburg 1782, pp. 85-239. C. Colbourn and J. Dinitz (co-editors), Handbook of Combinatorial Designs, 1st edition, CRC Press, 1996, 2nd edition, Chapman & Hall/CRC, 2007. H.-Y. Song, Choi's orthogonal Latin Squares is at least 67 years earlier than Euler's, 2008 Global KMS International Conference, 2008. 10. JEJU ICC, KOREA. K.-W. Lih, A Remarkable Euler Square before Euler, Math. Mag. Vol. 83, No. 3, pp. 163-167, 2010. H.-Y. Song, "Euler Square in Korea before Euler," in preparation for Journal of Combinatorial Designs. 관련기타자료 E. T. Parker, "Orthogonal Latin Squares," Proceedings of National Academy of Sciences, 1959. J. Dénes and A. D. Keedwell, Latin squares and their applications, Academic Press, 1974. Hong-Yeop Song and Jeffrey H. Dinitz, Tuscan Squares, Part IV, Chapter 48 of The CRC Handbook of Combinatorial Designs, edited by C. J. Colbourn and J. H. Dinitz, CRC Press, pp. 480-484, 1996. 김동진, 오영환, 지수귀문도의특성및해를구하는알고리즘, 한국정보과학회봄학술발표회논문집, 1989. 전용훈, 수학사의미스터리마방진, 과학동아 1999 년 7 월호. 문병도, 지수귀문도해결의열쇠유전자알고리즘, 과학동아 2003 년 7 월호. 박경미, 수학콘서트, 동아시아, 2006 라틴방진응용자료 D.-S. Kim, H.-Y. Oh, and H.-Y. Song, Collision-free Interleaver composed of a Latin Square Matrix for Parallel-architecture Turbo Codes, IEEE Communications Letters, vol. 12, Issue 3, pp. 203-205, March 2008. K. Kim and V. K. Prasanna, Latin Squares for Parallel Array Access, IEEE Transactions and Parallel and Distributed Systems, vol. 4, Issue 4, pp. 361-370, April 1993. Hong-Yeop Song, "Total Number of Tuscan Squares of order n," The R. C. Bose Memorial Conference on Statistical Design and related Combinatorics, Colorado State University, in Fort Collins, Colorado, June 7-11, 1995. Robert Mandl, "ORTHOGONAL LATIN SQUARES: AN APPLICATION OF EXPERIIWEUT DESIGN TO COMPILER TESTING," Communications of the ACM, vol. 28, no. 10, Oct. 1985. 43