Thue–Morse列

right|frame|Thue–Morse列を構築する過程 Thue–Morse列（トゥエモースれつ）もしくはProuhet–Thue–Morse列（プルエトゥエモースれつ）とは、0から始めて、これまでに得られた列のビット反転をつなげる操作を次々に行うことで得られる0と1からなる無限列のことである。この列は公平分割問題の解となることからfair share sequence（フェアシェアシーケンス）と呼ばれることもある。また、parity sequence（パリティシーケンス）と呼ばれることもある。最初の数ステップで得られる列は 0, 01, 0110, 01101001, 0110100110010110, ... のような列であり、これらはThue–Morse列の接頭辞でもある。この列の冒頭部分を示す。

01101001100101101001011001101001...（）

この数列は (Axel Thue)、 (Marston Morse)、 (Eugène Prouhet) にちなんで名づけられている。

定義 Thue–Morse列にはいくつかの等価な定義がある。

直接的な定義 thumb|2進法の各桁の総和を2で割った余りはThue–Morse列になる。 n 番目の要素 tn を計算するには、n を二進法で表したときの1の個数が奇数ならば tn = 1、偶数ならば tn = 0とする。つまり、tn は n の偶数パリティビットである。ジョン・ホートン・コンウェイらは tn = 1 を満たす n を odious numbers、tn = 0 となる数を evil numbersと呼んだ。これらはそれぞれodd、evenに似せた名称である。

高速な生成方法次の方法によりThue–Morse列を高速に計算できる。から始め、それぞれの n に対してと異なるビットのうち最上位のものを見つける。そのビットが偶数番目の位置なら tn はと異なり、そうでなければと同じである。

Pythonによる実装例:from typing import Iterator

def generate_sequence(seq_length: int) -> Iterator[int]: """Thue–Morse sequence.""" value: int = 1 for n in range(seq_length): # Note: assumes that (-1).bit_length() gives 1 x: int = (n ^ (n - 1)).bit_length() + 1 if x & 1 == 0: # Bit index is even, so toggle value value = 1 - value yield value このアルゴリズムは時間計算量は定数で、空間計算量は対数個のビット、つまり定数個のワードで実行できる。

漸化式 Thue–Morse列 tn は以下の漸化式を満たす。

ここで n は全ての非負整数である。

L-system thumb|L-Systemによって生成されるThue–Morse列 Thue–Morse列はmorphic wordである。次のようなL-systemの出力である。変数 0, 1 定数なし初期状態 0 置換規則 (0 → 01), (1 → 10)

ビット反転による定義この数列は以下のように定義することもできる。最初は0からはじめ、最初の個の要素が得られるごとに次の個の要素をそのビット反転で決める。これで個の要素が得られる。この過程を繰り返す。

最初の数ステップを示すと

まずは0から始める。 0のビット反転は1である。これを繋げる。最初の2つは01となる。 01のビット反転は10である。これを繋げる。最初の4つは0110となる。 0110のビット反転は1001である。これを繋げる。最初の8つは01101001となる。この手順を同様に繰り返す。

具体的には

T0 = 0. T1 = 01. T2 = 0110. T3 = 01101001. T4 = 0110100110010110. T5 = 01101001100101101001011001101001. T6 = 0110100110010110100101100110100110010110011010010110100110010110. 以下も同様である。

Pythonによる実装例を示す。def thue_morse_bits(n: int) -> int: """Return an int containing the first 2**n bits of the Thue–Morse sequence, low-order bit 1st.""" bits = 0 for i in range(n): bits |= ((1 << (1 << i)) - 1 - bits) << (1 << i) return bits以下のようにして文字列に変換できる。 n = 7 print(f"{thue_morse_bits(n):0{1<<n}b}")

母関数による定義この列は以下のように定義することもできる。

ここで tj はThue-Morse列の j 番目の要素である。ただし j = 0 から始めるものとする。

性質 Thue–Morse列には多くの「平方」、すなわちという形の文字列が含まれる。ここではとビット反転を用いて , , , もしくはと表される。例えばのときであり、平方はの16番目のビットから始まるパターンに現れる。に含まれる全ての「平方」がこれらの4パターンから生成されるため、整数を使って長さは全てかと表せる。一方で、は「立方」、すなわちのように同じ文字列を3回繰り返すパターンは含まない。また、「重なりを持つ平方」、すなわちやのようなパターンも含まれない。のcritical exponentは2である。

Thue–Morse列はuniformly recurrent wordである。列に現れる文字列 X それぞれについてある nX (しばしば X の長さよりはるかに大きい) が存在し、長さ nX 以上の連続列全てに X が現れる。Thue–Morse列は（初期部分を除いたとしても）周期的でないにもかかわらずこのような性質を持つ。

T2n は任意の n について回文数である。さらに、T2n に現れる連続する0の間にある1の個数を数えて得られる語を qn とすると、q1 = 2 や q2 = 2102012 のようになる。Tn は「重なりを持つ平方」を含まないため、 qn は回文的なsquarefree wordsである。

Thue–Morse 射 μ は記号を {0,1} としたとき μ(0) = 01, μ(1) = 10 となる射として定義される。つまり、列に含まれる 0 は 01 に、1 は 10 に置き換えられる。T がThue–Morse列ならば μ(T) もまた T である。したがって T は μ の不動点である。射 μ は自由モノイド {0,1}∗ 上のprolongable morphismであり、T を不動点に持つ。T は本質的に唯一の μ の不動点である。他の不動点は T のビット反転しかなく、これは(0,1)の代わりに(1,0)を使ったThue–Morse列である。この性質はautomatic sequenceの概念として一般化できる。

二進体上の T の母関数は以下の形式的冪級数である。

これは以下の等式を満たす。

Thue-Morse列の 0 と 1 をとに置き換えると一般化Thue-Morse列が得られる。とが異なる正の整数ならば、生成される列を単純連分数の項として用いることができる。その結果得られる Thue-Morse continued fraction,

は超越数である。

組合せゲーム理論 evil numbers ( を満たす ) はビットごとの排他的論理和のもとで非負整数の部分空間をなす。Kaylesというゲームではevilなnim-valuesは有限個の局面にしか現れず、残りの局面はodiousなnim-valuesを持つ。

The Prouhet–Tarry–Escott problem Prouhet–Tarry–Escott problemは次のような問題である。正の整数 N と非負整数 k が与えられたとき、集合 S = { 0, 1, ..., N-1 } を2つの素集合 S0 と S1 に分割し、1以上k以下の全てのiについて以下の関係を満たすようにする。

N が 2k+1 の倍数のとき、以下の解をもつ。

S0 は S のうち tn = 0 を満たす整数 n からなる S1 は S のうち tn = 1 を満たす整数 n からなる

例えばならば

N が 2k+1 の倍数であるという条件は厳密には必要ではなく、他にも解が存在する場合がある。しかし、この条件はより強い性質を保証する。この条件が満たされるとき等差数列中の任意の N 個の数について、その k 乗の集合を和が等しい二つの集合へ分割できる。これは、等差数列の第 n 項を表す二項式に二項定理を適用して展開することから直接従う。

Thue–Morse列とProuhet–Tarry–Escott problemを3つ以上の部分への分割へ一般化したものについては、Bolker, Offner, Richman and Zara による "The Prouhet–Tarry–Escott problem and generalized Thue–Morse sequences" を参照されたい。

フラクタルとタートル turtle graphicsを用いてある列によってプログラムされたオートマトンから曲線を生成できる。Thue–Morse列を使って以下のルールを考える。

t(n) = 0 ならば一歩進む t(n) = 1 ならば π/3 ラジアン (60°) 回転する

このルールはコッホ曲線に収束する。これはThue-Morse列のフラクタル的性質を示している。

次のルールによって精密に描くこともできる。

t(n) = 0 ならば π ラジアン (180°) 回転する t(n) = 1 ならば一歩進んでから π/3 ラジアン回転する

公平分割問題 Steven BramsとAlan Taylorは公平分割問題に関する著書で、名前は挙げなかったもののThue–Morse列を用いた。二者が、相対的な価値について合意している品物の山を分けるとき、BramsとTaylorは balanced alternation または taking turns taking turns taking turns . . . と呼ぶ方法を提案した。これは、片方が先に選ぶことによって生じる有利さを回避するための方法である。たとえば離婚する夫婦が共同所有物を公平に分配する場合、ある時点ごとに先に選ぶ側を交代する。Ann が一つ選び、次に Ben が選び、次に Ben が一つ選び、次に Ann が選ぶ、というように進める。

Lionel LevineとKatherine E. Stangeはエチオピア料理のような共有の食事を公平に分ける方法を論じる中で、先手の有利さを減らす方法としてThue–Morse列を提案した。彼らは「Thue–Morse列による順序が公平な結果をもたらす傾向があるという直観を定量化するのは興味深いだろう」と述べた。

Robert Richmanも同様の問題を扱ったが、発表時にはThue–Morse列とは同定していなかった。彼は Tn を区間[0,1]上の階段関数として表し、それらとWalsh 関数やRademacher関数との関係を記述した。また、第 n 導関数を Tn によって表せることを示した。この帰結として、Tn は次数 n − 1 の多項式と直交する。この結果の帰結として、価値が単調減少する連続関数で表される資源は、その関数がより平坦になるにつれてThue–Morse列に近づく順序で分配するのが最も公平になる。例として、非線形な濃度勾配をもつコーヒーサーバーから同じ濃さのコーヒーを注ぎ分ける問題が挙げられる。

Joshua CooperとAaron Dutleは離散的な事象に対してThue–Morse列による順序が公平な結果をもたらす理由を示した。彼らは、双方の射撃技術が同程度に低い決闘 (Galois duel) において最も公平な射撃順序を考察した。CooperとDutleは、両者が決闘開始前の事前確率で相手の勝率が自分の勝率を上回った時点で直ちに射撃する機会を要求すると仮定した。彼らはこの条件のもとで、命中率が0に近づくにつれて順序がThue–Morse列に収束することを示した。これにより、長さ 2n の列 Tn に限らず、任意の長さの列に対してもThue–Morse順序が公平な結果をもたらすことが示された。

したがって、目標が公平性であり、かつ早い手番と遅い手番が何らかの意味のある性質について単調に異なる場合、単純な交代ではなくThue–Morse列を用いることを数学は支持している。その性質は連続的に変化する場合でも、離散的に変化する場合でもよい。

スポーツ競技は、公平な順序づけ問題の重要な例である。完全な交代ではしばしば不公平が生じるからである。Ignacio Palacios-HuertaはサッカーのPK戦などさまざまな競技の公平性を改善するために順序をThue–Morse列に変更することを提案した。プロ選手を対象としたフィールド実験では、ABAB (T1) 型では60%だった先手勝率がABBA (T2) 型では54%になり、さらに完全なThue–Morse列 (Tn) では51%になることが判明した。この結果を受けて、FIFAの欧州選手権・世界選手権やイングランドのEFLカップではABBA型が試験導入された。ABBA型はテニスのタイブレークのサーブ順にも用いられている。ローイング競技では、T2 は4人乗り舵手なし競漕艇において横向きの力、したがって横揺れをなくす唯一の漕手配置であり、T3 は8人乗り艇で横揺れを避ける四つの配置の一つである。

公平性は選手のドラフトでも特に重要である。多くのプロスポーツリーグではチーム戦力の均衡のため、各ラウンドで弱いチームに優先的に指名権を与える。これに対し、fantasy football leaguesでは既存の不均衡がないため交互に指名する (T1) のが一般的である。Ian Allanは “third-round reversal” (T2) がより公平だと論じた。Richmanはストリートボールにおいて最も公平に選手を選ぶ方法は T3 に対応すると提案した。つまり、キャプテンAは第1,4,6,7指名を行い、キャプテンBは第2,3,5,8指名を行う。

ハッシュ衝突 Thue–Morse列の最初のビットは2の冪を法とする幅広いクラスの多項式ハッシュ関数によって 0 に写される。これはハッシュ衝突を引き起こしうる。

リーマンゼータ関数係数がThue–Morse列の項であるディリクレ級数の特定の線形結合から、リーマンゼータ関数を含む恒等式が得られる (Tóth, 2022 )。例えば、

ここではThue–Morse列の第項である。実際、実部が1より大きい全てのについて

歴史 Thue–Morse列は1851年にによって初めて研究され、数論に応用された。しかし、プルエはこの数列を明示的には述べなかった。これを行ったのは1906年のアクセル・トゥエであり、この数列を使ってを基礎付けた。この数列が世界的に注目されるようになったのは1921年にマーストン・モースが微分幾何学に応用したときである。この数列は何度も独立に発見されており、発見者は必ずしも専門の研究数学者ではなかった。例えばチェスのグランドマスターであり数学教師でもあったマックス・エーワが1929年に、この数列を用いて当時のスリーフォールド・レピティション（チェスの千日手）を回避できることを示した。この数列には「立方」が含まれないため、当時の「同一手順3回の繰り返し」のルールではスリーフォールド・レピティションを無限に回避し続けることができる。このルールはのちに「同一局面3回の繰り返し」に改められた。

関連項目 Dejean's theorem Fabius function First difference of the Thue–Morse sequence グレイコード Komornik–Loreti constant Prouhet–Thue–Morse constant

脚注

参考文献

Thue–Morse列

Źródło i licencja