투에-모스 수열

수학에서 투에-모스 수열(영어: Thue-Morse sequence), 또는 프로헷-투에-모스 수열(영어: Prouhet-Thue-Morse sequence)은 0에서 시작해서 앞의 수열의 불 보수를 덧붙여서 얻어지는 이진 수열 (0과 1의 무한수열)이다. 처음 몇 단계를 거치면 투에-모스 수열의 앞부분인 수열의 첫 단계는 0, 그 다음 단계는 01, 0110, 01101001, 0110100110010110,…을 얻을 수 있다. 전체 수열은 다음과 같이 시작한다.

이 그래픽은 투에 모스 수열의 반복적이고 상보적인 생성을 나타낸다.

01101001100101101001011001101001.... (OEIS의 수열 A010060)

정의

투에-모스 수열을 정의하는 여러 동등한 방법들이 있다.

직접 정의

n번째 원소 t_n을 계산하려면 n을 이진수로 써야 한다. 이 이진 표현에서 1의 개수가 홀수라면 t_n = 1이고, 짝수면 t_n = 0이다. 따라서 존 호턴 콘웨이 외는 t_n = 1을 만족하는 수 n을 불쾌한 수(영어: odious number, 홀수를 뜻하는 odd에서 나왔다)라고 부르고 t_n = 0일 때는 악한 수(영어: evil number, 짝수 even때문)라고 불렀다. 다시 말해, n이 악한 수일 때는 t_n = 0이고 n이 불쾌한 수일 경우에는 t_n = 1이다.

이 방법은 투에-모스 수열을 계산하는 빠른 방법이다. 먼저 t₀ = 0에서 시작하고, 각각의 n에 대해 n의 이진 표기에서 n − 1의 이진 표기와 다른 최상위 비트를 찾는다. (이 비트는 x를 n과 n − 1의 비트 단위 XOR이라 두고, x를 오른쪽으로 한 비트 옮기고 x와 옮긴 값의 비트 단위 XOR을 취함으로 남길 수 있다.) 이 비트가 짝수 인덱스에 있다면, t_n은 t_n − 1과 다르고, 아니면 t_n − 1과 같다. 따라서 이 알고리즘은 각 수열의 요소를 생성하는데 상수 시간이 걸리며 메모리의 로그 개수의 비트 (상수 개수의 단어)만을 사용한다.

점화식

투에-모스 수열은 모든 음이 아닌 정수 n에 대하여 다음 점화식을 만족시키는 수열 t_n이다.

t0	= 0,
t2n	= tn, 그리고
t2n+1	= 1 − tn.

L-시스템

투에-모스 수열은 morphic word이다. 즉, 투에-모스 수열은 다음의 린덴마이어 시스템의 출력이다:

변수	0, 1
상수	없음
시작	0
규칙	(0 → 01), (1 → 10)

비트 단위 NOT을 사용한 특성화

위에서 비트의 수열로 주어진 형태의 투에-모스 수열은 비트 단위 NOT을 사용하여 재귀적으로 정의할 수 있다. 첫 번째 원소는 0이다. 처음 2ⁿ개의 원소가 한번 결정되어 문자열 s를 형성하면, 다음 2ⁿ개의 원소는 s의 비트 단위 NOT으로 형성된다. 이제 처음 2ⁿ⁺¹개의 원소를 정의했으므로 재귀한다.

처음 몇 단계를 자세하게 설명하면,

• 0에서 시작한다.
• 0 의 비트 단위 NOT을 취한 것은 1이다.
• 연결시키면 처음 두 원소는 01이다.
• 01 의 비트 단위 NOT을 취한 것은 10이다.
• 연결시키면 처음 두 원소는 0110이다.
• 0110 의 비트 단위 NOT을 취한 것은 1001이다.
• 연결시키면 처음 두 원소는 01101001이다.
• 계속한다.

따라서

• T₀ = 0.
• T₁ = 01.
• T₂ = 0110.
• T₃ = 01101001.
• T₄ = 0110100110010110.
• T₅ = 01101001100101101001011001101001.
• T₆ = 0110100110010110100101100110100110010110011010010110100110010110.
• 등등.

무한 곱

수열은 다음과 같이도 정의할 수 있다.

$\prod _{i=0}^{\infty }(1-x^{2^{i}})=\sum _{j=0}^{\infty }(-1)^{t_{j}}x^{j}{\mbox{,}}\!$

이 때, t_j는 j = 0에서 시작했을 때 j번째 원소이다.

일부 특성

투에-모스 수열의 새로운 부분이 처음 부분에 비트 단위 NOT을 취함으로 만들어졌고, 이것이 다음 블럭의 처음에도 반복되기 때문에, 투에-모스 수열은 이중 반복(영어: square, 반복되는 연속적인 수열)으로 가득하다. 즉, XX의 예가 많이 있고, 이 때 X는 어떤 문자열을 의미한다. 당연히 $X$는 그런 문자열이다 if and only if $X=A,\,{\overline {A}},\,A{\overline {A}}A,$또는 ${\overline {A}}A{\overline {A}}$ 여기서 $A$는 어떤 $k\geq 0$에 대해 $A=T_{k}$이고 ${\overline {A}}$는 $A$의 비트 단위 NOT을 나타낸다 (0과 1을 맞바꾼다). 예를 들어 $k=0$일 때, $\ A=T_{0}=0$이고 이중 반복 $A{\overline {A}}AA{\overline {A}}A=010010$는 $T$에서 16번째 비트부터 나타난다. (따라서, $T$에 있는 이중 반복의 길이는 2의 거듭제곱이거나 2의 거듭제곱의 3배이다.) 하지만, 삼중 반복(영어: cubes, XXX의 예)은 없다. 또한 겹치는 이중 반복(영어: overlapping squares, 0X0X0이나 1X1X1의 예)도 없다. 임계 지수는 2이다.

모든 n > 1에 대해서 T_2n이 회문이라는 것을 주목하자. 더 나아가, q_n을 T_2n에서 연속적인 0사이의 1을 세서 얻어지는 단어라고 하자. 예를 들면, q₁ = 2이고 q₂ = 2102012 등등. 단어 T_n은 겹치는 반복을 포함하지 않아 결과적으로 단어 q_n은 회문 이중 반복 없는 단어이다.

투에-모스 열이 "이중 반복으로 가득하다"는 위의 문장은 더 정확하게 만들 수 있다: 이 수열은 고른 재귀 단어이고, 고른 재귀 단어는 어떤 유한한 문자열 X가 주어지면 결과적으로 길이가 n_X인 모든 블럭에 X가 나타나느 어떤 길이 n_X(종종 X의 길이보다 더 길다)가 있다는 것을 의미한다. 재귀 단어를 만드는 가장 간단한 방법은 완전히 주어진 수 m단계 다음에 완전히 반복되는 주기 수열을 만드는 것이다. 그러면 n_X는 X의 길이의 두 배 보다 긴 m의 배수로 둘 수 있다. 하지만 투에-모스 수열은 고른 재귀 수열이지만 주기수열이 아니고 심지어 부분적 주기 수열(일부 비주기 초기치 이후 주기적이 되는것을 의미한다)도 아니다.

투에-모스 사상(영어: Thue–Morse morphism)은 이진 수열의 집합에서 수열에 있는 모든 0을 01로, 1을 10으로 바꾸어서 자기 자신에게로 가는 함수 f로 정의한다. 그러면 T가 투에-모스 수열이라면 f(T)는 다시 T가 나온다. 즉, T는 f의 고정점이다. 함수 f는 자유 모노이드 {0,1}^∗과 T를 고정점으로 가지는 연장 가능 사상이다. 당연히 T는 본직적으로 f의 유일한 고정점이다. 유일한 다른 고정점은 T에 비트 단위 NOT을 취한 것으로 간단히 (0,1)에서 시작하는 것이 아닌 (1,0)에서 시작하는 투에-모스 수열이다. 이 특성은 오토마타 수열의 개념으로 일반화 할 수 있다.

이진 체에서 T의 생성 급수는 다음 형식적 멱급수이다

$t(Z)=\sum _{n=0}^{\infty }T(n)Z^{n}\ .$

이 멱급수는 다음의 등식을 만족하는 형식적 멱급수의 체에서 대수적이다

$Z+(1+Z)^{2}t+(1+Z)^{3}t^{2}=0$

조합론적 게임 이론에서

악한 숫자 ($t_{n}=0$인 수 $n$)의 집합은 님 덧셈(비트 단위 배타적 논리합) 아레의 음이 아닌 정수들의 부분집합을 형성한다. Kayles 게임에서, 악한 님 값은 게임에서 매우 적은(유한하게) 상태에서 나타나고 나머지는 모두 다 추악한 님 값을 가진다.

프로헷-테리-에스콧 문제

프로헷-테리-에스콧 문제(영어: Prouhet–Tarry–Escott problem)는 다음과 같이 정의할 수 있다. 양의 정수 N과 음이 아닌 정수 k가 주어졌을 때, 집합 S = { 0, 1, ..., N-1 }를 아래와 같이 k까지 거듭제곱의 합이 같은 두 서로소 부분집합 S₀와 S₁으로 분할하는 것이다. 이 때 i는 1에서 k까지의 모든 정수를 의미한다.

$\sum _{x\in S_{0}}x^{i}=\sum _{x\in S_{1}}x^{i}$

이 문제는 N이 2^k+1의 배수일 때 다음과 같은 솔루션을 가진다.

• S₀은 S에서 t_n = 0인 정수 n으로 이루어져 있다,
• S₁은 S에서 t_n = 1인 정수 n으로 이루어져 있다.

예를 들어, N = 8이고 k = 2일 때,

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,

0² + 3² + 5² + 6² = 1² + 2² + 4² + 7².

N이 2^k+1의 배수여야 한다는 조건은 반드시 필요한 것은 아니다. 솔루션이 있는 다른 경우가 일부 존재하지만, 이 조건은 더 강한 특성을 보장한다. 조건을 만족한다면, 등차 수열의 수 N개의 k제곱을 한 집합은 합이 같은 두 집합으로 분할 할 수 있다. 이것은 등차 수열의 n번째 원소를 나타내는 이항에 적용된 이항 정리에 의해 주어진 확장에서 직접적으로 따른다.

투에-모스 수열의 일반화와 두 부분 이상으로 분할하는 프로헷-테리-에스콧 문제에 대해서는 Bolker, Offner, Richman 그리고 Zara의 "The Prouhet –Tarry –Escott problem and generalized Thue –Morse sequences"을 보라.

프랙탈과 거북이 그래픽

거북이 그래픽을 사용할 때, 오토마톤이 수열로 프로그래밍 되어있다면 곡선이 만들어진다. 투에-모스 수열의 요소는 프로그램 상태를 만들기 위해 사용된다:

• t(n) = 0일 때, 한 단위 앞으로 이동한다,
• t(n) = 1일 때, 반시계 방향으로 π/3 만큼 회전한다,

나타나는 곡선은 유한한 면적을 가지면서 곡선의 길이가 무한한 프랙탈 곡선인 코흐 눈송이로 수렴한다. 이것은 투메-모스 수열의 프랙탈 성질을 나타낸다.

역사

투에-모스 수열은 정수론에 적용시킨 외젠 프로헷(Eugène Prouhet)이 1851년에 처음으로 연구를 시작하였다. 하지만, 프로헷은 이 수열을 명시적으로 언급하지 않았다. 이것은 1906년에 악셀 투에에게로 넘겨졌고, 투에는 이 수열으로 단어의 조합론 연구를 시작했다. 이 수열은 1921년 마스턴 모스의 연구에서 모스가 이 수열을 미분기하학에 적용시켰을 때 세상의 주목을 받게 되었다. 이 수열은 수차례 독자적으로 발견되었으며, 수학자들의 전문 연구에서만 발견된 것은 아니다. 예를 들면, 1935년에서 1937년까지 체스 세계 챔피언이였고 수학 교사였던 체스 그랜드마스터인 막스 오이베는 1929년에 체스에서의 적용을 발견하였다. 오이베는 무한히 연장되는 게임을 반복되는 이동에 의해서 무승부를 선언함으로 막는 규칙을 이 수열의 삼중 반복이 없는 특성(위의 문단 참고)을 사용해서 어떻게 회피할 후 있는지를 보였다.

같이 보기

• 데 장의 정리
• 파비우스 함수
• 프로헷-투에-모스 상수

참고 문헌

• Abrahams, Marc (2010년 7월 12일). “How to pour the perfect cup of coffee”. 《The Guardian》. 
• Arndt, Jörg (2011). 〈1.16.4 The Thue–Morse sequence〉. 《Matters Computational: Ideas, Algorithms, Source Code》 (PDF). Springer. 44쪽. 
• Allouche, Jean-Paul; Shallit, Jeffrey (2003). 《Automatic Sequences: Theory, Applications, Generalizations》. Cambridge University Press. ISBN 978-0-521-82332-6. Zbl 1086.11015. 
• Berstel, Jean; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009). 《Combinatorics on words. Christoffel words and repetitions in words》. CRM Monograph Series 27. Providence, RI: American Mathematical Society. ISBN 978-0-8218-4480-9. Zbl 1161.68043. 
• Berthé, Valérie; Rigo, Michel, 편집. (2010). 《Combinatorics, automata, and number theory》. Encyclopedia of Mathematics and its Applications 135. Cambridge: Cambridge University Press. 7쪽. ISBN 978-0-521-51597-9. Zbl 1197.68006. 
• Brams, Steven J.; Taylor, Alan D. (1999). 《The Win-Win Solution: Guaranteeing Fair Shares to Everybody》. W. W. Norton & Co., Inc. 36–44쪽. ISBN 0-393-04729-6. 
• Brlek, Srećko (1989). “Enumeration of Factors in the Thue-Morse Word”. 《Discrete Applied Mathematics》 24: 83–96. doi:10.1016/0166-218x(92)90274-e. 
• Bugeaud, Yann (2012). 《Distribution modulo one and Diophantine approximation》. Cambridge Tracts in Mathematics 193. Cambridge: Cambridge University Press. ISBN 978-0-521-11169-0. Zbl 1260.11001. 
• Cooper, Joshua; Dutle, Aaron (2013). “Greedy Galois Games” (PDF). 《American Mathematical Monthly》 120 (5): 441–451. doi:10.4169/amer.math.monthly.120.05.441. 
• Krieger, Dalia (2006). 〈On critical exponents in fixed points of non-erasing morphisms〉. Ibarra, Oscar H.; Dang, Zhe. 《Developments in Language Theory: Proceedings 10th International Conference, DLT 2006, Santa Barbara, CA, USA, June 26-29, 2006》. Lecture Notes in Computer Science 4036. Springer-Verlag. 280–291쪽. ISBN 3-540-35428-X. Zbl 1227.68074. 
• Levine, Lionel; Stange, Katherine E. (2012). “How to Make the Most of a Shared Meal: Plan the Last Bite First” (PDF). 《American Mathematical Monthly》 119 (7): 550–565. doi:10.4169/amer.math.monthly.119.07.550. 2014년 5월 3일에 원본 문서 (PDF)에서 보존된 문서. 2018년 1월 9일에 확인함. 
• Lothaire, M. (2011). 《Algebraic combinatorics on words》. Encyclopedia of Mathematics and Its Applications 90. With preface by Jean Berstel and Dominique Perrin Reprint ofe 2002 haback판. Cambridge University Press. ISBN 978-0-521-18071-9. Zbl 1221.68183. 
• Lothaire, M. (2005). 《Applied combinatorics on words》. Encyclopedia of Mathematics and Its Applications 105. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. Cambridge: Cambridge University Press. ISBN 0-521-84802-4. Zbl 1133.68067. 
• Ma, Jun; Holdener, Judy (2005). “When Thue-Morse meets Koch” (PDF). 《Fractals》 13 (3): 191–206. doi:10.1142/S0218348X05002908. MR 2166279. 
• Palacios-Huerta, Ignacio (2012). “Tournaments, fairness and the Prouhet–Thue–Morse sequence” (PDF). 《Economic inquiry》 50 (3): 848–849. doi:10.1111/j.1465-7295.2011.00435.x. 
• Pytheas Fogg, N. (2002). 《Substitutions in dynamics, arithmetics and combinatorics》. Lecture Notes in Mathematics 1794. Editors Berthé, Valérie; Ferenczi, Sébastien; Mauduit, Christian; Siegel, A. Berlin: Springer-Verlag. ISBN 3-540-44141-7. Zbl 1014.11015. 
• Richman, Robert (2001). “Recursive Binary Sequences of Differences” (PDF). 《Complex Systems》 13 (4): 381–392. 
• Barrow, John D. (2010). “Rowing and the Same-Sum Problem Have Their Moments” (PDF). 《American Journal of Physics》 78 (7): 728–732. doi:10.1119/1.3318808. 

외부 링크

• “Thue-Morse sequence”. 《Encyclopedia of Mathematics》 (영어). Springer-Verlag. 2001. ISBN 978-1-55608-010-4. 
• Weisstein, Eric Wolfgang. “Thue-Morse Sequence”. 《Wolfram MathWorld》 (영어). Wolfram Research. 
• Allouche, J.-P.; Shallit, J. O. The Ubiquitous Prouhet-Thue-Morse Sequence. (contains many applications and some history)
• Thue–Morse Sequence over (1,2) (OEIS의 수열 A001285)
• Odious numbers (OEIS의 수열 A000069)
• Evil numbers (OEIS의 수열 A001969)
• Reducing the influence of DC offset drift in analog IPs using the Thue-Morse Sequence. A technical application of the Thue–Morse Sequence
• MusiNum - The Music in the Numbers. Freeware to generate self-similar music based on the Thue–Morse Sequence and related number sequences.
• Parker, Matt. “The Fairest Sharing Sequence Ever” (video). standupmaths. 2016년 1월 20일에 확인함.