투에-모스 수열

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색
이 그래픽은 투에 모스 수열의 반복적이고 상보적인 생성을 나타낸다.

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

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

정의[편집]

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

직접 정의[편집]

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

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

점화식[편집]

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

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

L-시스템[편집]

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

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

비트 단위 NOT을 사용한 특성화[편집]

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

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

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

따라서

  • T0 = 0.
  • T1 = 01.
  • T2 = 0110.
  • T3 = 01101001.
  • T4 = 0110100110010110.
  • T5 = 01101001100101101001011001101001.
  • T6 = 0110100110010110100101100110100110010110011010010110100110010110.
  • 등등.

무한 곱[편집]

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

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

일부 특성[편집]

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

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

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

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

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

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

조합론적 게임 이론에서[편집]

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

프로헷-테리-에스콧 문제[편집]

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

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

  • S0S에서 tn = 0인 정수 n으로 이루어져 있다,
  • S1S에서 tn = 1인 정수 n으로 이루어져 있다.

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

0 + 3 + 5 + 6 = 1 + 2 + 4 + 7,
02 + 32 + 52 + 62 = 12 + 22 + 42 + 72.

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

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

프랙탈과 거북이 그래픽[편집]

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

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

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


역사[편집]

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

같이 보기[편집]

각주[편집]

  1. Allouche & Shallit (2003, 15쪽)
  2. Arndt (2011).
  3. Lothaire (2011, 11쪽)
  4. Brlek (1989).
  5. Lothaire (2011, 113쪽)
  6. Pytheas Fogg (2002, 103쪽)
  7. Krieger (2006).
  8. Lothaire (2011, 30쪽)
  9. Berthé & Rigo (2010).
  10. Lothaire (2011, 31쪽)
  11. Berstel 외. (2009, 70쪽)
  12. Berstel 외. (2009, 80쪽)
  13. Bolker, Ethan; Offner, Carl; Richman, Robert; Zara, Catalin (2016). “The Prouhet –Tarry –Escott problem and generalized Thue –Morse sequences”. 《Journal of Combinatorics》 7 (1): 117–133. 
  14. Ma & Holdener (2005).

참고 문헌[편집]

외부 링크[편집]