トゥー・モース数列

数学において、Thue–Morse列またはProuhet–Thue–Morse 列は、0 から始めて、それまでに得られた列のブール補数を連続して追加することによって得られるバイナリ列(0 と 1 の無限列) です。 ^[1]公平な分割やパリティ列への応用のため、公平なシェア列と呼ばれることもあります。この手順の最初の数ステップで、Thue–Morse 列のプレフィックスである文字列 0、01、0110、01101001、0110100110010110 などが生成されます。完全な列は次のように始まります。

01101001100101101001011001101001.... ^[1]

このシーケンスは、アクセル・トゥーとマーストン・モースにちなんで名付けられました。

Thue-Morse 列を定義する同等な方法がいくつかあります。

n番目の要素t _{n を}計算するには、数n を2 進数で表します。この 2 進数展開で1の数が奇数の場合はt _n  = 1 になり、偶数の場合はt _n  = 0 になります。^[2] つまり、t _{n は}nの偶数パリティ ビットです。John H. Conwayらは、 t _n = 1 を満たす数n を不吉な数 (奇数に似た数) と見なし、t _n = 0 を満たす数 n を邪悪 な数(偶数に似た数) と見なしました。

この方法は、Thue-Morseシーケンスを計算するための高速な方法につながります。まず、 t ₀  = 0から始めて、各nについて、 nのバイナリ表現で、n  −1の表現の同じビットと異なる最上位ビットを見つけます。このビットが偶数インデックスにある場合、 t _nはt _{n  −1}と異なり、そうでない場合はt _{n  −1}と同じになります。

Pythonの場合:

def  generate_sequence ( seq_length :  int ): 
"""Thue–Morse シーケンス。""" value = 1 for n in range ( seq_length ): # 注: (-1).bit_length() が 1 を返すと仮定しますx = ( n ^ ( n - 1 )) . bit_length () + 1 if x & 1 == 0 : # ビット インデックスは偶数なので、切り替え値value = 1 - value はvalue を返します    
      
       
        
                
             
            
                
         

結果として得られるアルゴリズムは、対数ビット数（一定数のワード数）のメモリのみを使用して、各シーケンス要素を生成するのに一定の時間がかかります。^[3]

トゥー・モース数列は、再帰関係を満たす数列t _{nである。}

${\displaystyle {\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&=1-t_{n},\end{aligned}}}$

すべての非負整数nに対して。^[2]

トゥー・モース列は形態語である。^{[4]これは次の}リンデンマイヤーシステムの出力である。

上記の形式の Thue-Morse シーケンスは、ビットのシーケンスとして、ビット否定演算を使用して再帰的に定義できます。したがって、最初の要素は 0 です。最初の 2 ⁿ個の要素が指定されて文字列sが形成されると、次の 2 ⁿ個の要素はsのビット否定を形成する必要があります。これで最初の 2 ^{n +1}個の要素が定義され、再帰的になります。

最初のいくつかのステップを詳しく説明します。

• 0から始まります。
• 0 のビット否定は 1 です。
• これらを組み合わせると、最初の 2 つの要素は 01 になります。
• 01 のビット否定は 10 です。
• これらを組み合わせると、最初の 4 つの要素は 0110 になります。
• 0110 のビット否定は 1001 です。
• これらを組み合わせると、最初の 8 つの要素は 01101001 になります。
• 等々。

それで

• T0 = 0_です。
• T1 = ₀₁。
• T2 = ₀₁₁₀。
• T3 = _01101001。
• T4 = _{0110100110010110}。
• T5 = 01101001100101101001011001101001 _。
• T6 = 0110100110010110100101100110100110010110011010010110100110010110100110010110 _。
• 等々。

Pythonの場合:

def  thue_morse_bits ( n ): 
"""Thue-Morse シーケンスの最初の 2**n ビットを含む int を返します。下位ビットが 1 番目です。""" bits = 0 for i in range ( n ): bits |= (( 1 << ( 1 << i )) - 1 - bits ) << ( 1 << i ) return bits	
	  
       
                      
     

これを次のように (逆順に) 文字列に変換できます。

n  =  7
を印刷します( f " { thue_morse_bits ( n ) : 0 { 1 << n } b } " )

シーケンスは次のように定義することもできます。

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

ここで、t _{j は}、 j = 0 から開始する場合のj番目の要素です。

Thue–Morse 列には、多くの平方数 (文字列 のインスタンス) が含まれます。ここで、 は文字列 、、、またはを表します。ただし、いくつかの に対して、 はのビット否定です。^[5]たとえば、の場合、 となります。平方数は、16 番目のビットから始まって に現れます。 のすべての平方数は、これら 4 つの文字列のいずれかを繰り返すことで得られるため、それらの長さはすべてまたはです。いくつかの に対して、 となります。 には立方体( のインスタンス)は含まれません。重なり合う平方数(またはのインスタンス)もありません。^{[6] [7]}の臨界指数は 2 です。^[8]${\displaystyle XX}$${\displaystyle X}$${\displaystyle A}$${\displaystyle {\overline {A}}}$${\displaystyle A{\overline {A}}A}$${\displaystyle {\overline {A}}A{\overline {A}}}$${\displaystyle A=T_{k}}$${\displaystyle k\geq 0}$${\displaystyle {\overline {A}}}$${\displaystyle A}$${\displaystyle k=0}$${\displaystyle A=T_{0}=0}$${\displaystyle A{\overline {A}}AA{\overline {A}}A=010010}$${\displaystyle T}$${\displaystyle T}$${\displaystyle 2^{n}}$${\displaystyle 3\cdot 2^{n}}$${\displaystyle n\geq 0}$${\displaystyle T}$${\displaystyle XXX}$${\displaystyle 0X0X0}$${\displaystyle 1X1X1}$${\displaystyle T}$

Thue-Morse 列は一様回帰語である。列内の任意の有限文字列Xに対して、長さn _X （多くの場合Xの長さよりもはるかに長い）が存在し、X は長さn _Xのすべてのブロックに現れる。^{[9] [10]}注目すべきことに、Thue-Morse 列は一様回帰であるが、周期的でも最終的に周期的でもない（つまり、最初の非周期的なセグメントの後に周期的になる）ことである。^[11]

シーケンスT _{2 n は}任意のnに対して回文です。さらに、q _{n を}T _{2 n}内の連続するゼロ間の 1 を数えて得られる単語とします。たとえば、q ₁ = 2 およびq _{2 = 2102012 です。T n に}は重なり合う正方形が含まれていないため、単語q _nは回文のスクエアフリー単語です。

Thue –Morse射 μはアルファベット {0,1} 上で置換写像μ (0) = 01, μ (1) = 10 によって定義される。つまり、シーケンス内のすべての 0 は 01 に、すべての 1 は 10 に置き換えられる。^[12] T がThue–Morse シーケンスである場合、 μ ( T ) もTである。したがって、T はμの不動点である。射μは、 Tを不動点とする自由モノイド{0,1} ^∗上の延長可能な射である。つまり、 Tは本質的にμの唯一の不動点である。唯一の他の不動点はTのビット否定であり、これは単に (0,1) 上の Thue–Morse シーケンスではなく (1,0) 上の Thue–Morse シーケンスである。この特性は、自動シーケンスの概念に一般化できる。

二元体上のTの生成級数は形式的な冪級数である

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

この冪級数は有理関数体上の代数級数であり、次の式を満たす^[13]。

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

邪悪な数(の数)の集合は、非負整数のnim 加算(ビットごとの排他的論理和) による部分空間を形成します。Kayles のゲームでは、邪悪なnim 値はゲーム内の少数 (有限個) の位置に発生し、残りのすべての位置には不快な nim 値があります。 ${\displaystyle n}$${\displaystyle t_{n}=0}$

Prouhet -Tarry-Escott問題は、次のように定義できます。正の整数Nと非負の整数kが与えられた場合、集合S = {0, 1, ..., N -1}を、kまでのべき乗の和が等しい 2つの互いに交わらない部分集合S ₀とS _1に分割します。つまり、

${\displaystyle \sum _{x\in S_{0}}x^{i}=\sum _{x\in S_{1}}x^{i}}$1 からkまでのすべての整数iについて。

N が2 ^{k +1}の倍数である場合、この解は次のように与えられます。

• S _{0 は、}S内の整数nのうちt _n = 0となるものから成り、
• S _{1 は}、S内の整数nのうちt _n = 1となるものから構成されます。

例えば、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乗の集合は、等しい和を持つ 2 つの集合に分割できます。これは、等差数列の n番目の要素を表す二項式に適用される二項定理によって与えられる展開から直接導かれます。

Thue-MorseシーケンスとProuhet-Tarry-Escott問題を2つ以上の部分に分割する一般化については、Bolker、Offner、Richman、Zaraの「The Prouhet-Tarry-Escott problem and generalized Thue-Morse columns」を参照してください。^[14]

タートルグラフィックスを使用すると、オートマトンがシーケンスでプログラムされている場合に曲線を生成できます。プログラム状態を選択するためにThue-Morseシーケンスメンバーを使用する場合:

• t ( n ) = 0の場合は1単位進む。
• t ( n ) = 1の場合、π/3ラジアン（60°）の角度で回転します。

結果として得られる曲線はコッホ曲線、つまり有限の面積を含む無限の長さのフラクタル曲線に収束します。これは、Thue-Morse数列のフラクタルな性質を示しています。^[15]

以下の手順で曲線を正確に描くことも可能です。^[16]

• t ( n ) = 0の場合は、πラジアン（180°）の角度で回転します。
• t ( n ) = 1の場合は、1 単位前進してから、π/3 ラジアンの角度で回転します。

公平な分割の問題に関する著書の中で、スティーブン・ブラムスとアラン・テイラーは、トゥー・モース順序に言及したが、それをそのように特定したわけではない。争われている品物の山を、品物の相対的な価値について合意している2者間で分配する場合、ブラムスとテイラーは、一方が他方より先に選択することで生じるえこひいきを回避する方法として、バランスのとれた交代、つまり交代で順番に選択するという手法を提案した。離婚する夫婦が共有品の分配で公平な決着をつける方法の例を示した。選択プロセスのさまざまな時点で、両当事者が交代で最初の選択者になる。アンが1つの品物を選び、次にベンが選び、次にベンが1つの品物を選び、次にアンが選ぶ。^[17]

ライオネル・レヴァインとキャサリン・E・スタンジは、エチオピア料理のディナーのような共有の食事を公平に分配する方法について議論する中で、先手を取ることの利点を減らす方法として、トゥー・モース順序を提案した。彼らは、「トゥー・モース順序が公平な結果を生み出す傾向があるという直感を定量化することは興味深いだろう」と示唆した。^[18]

ロバート・リッチマンはこの問題に取り組んだが、彼も出版時点ではトゥエ・モース列をそのようなものとして特定していなかった。^[19] 彼は列 Tn を区間 [0,1] 上のステップ関数として提示し、ウォルシュ関数およびラデマッハー関数との関係を説明した。彼はn次導関数がT _nで表現できること を示した。結果として、 T _nから生じるステップ関数は n − 1次多項式に直交する。この結果の帰結として、価値が単調減少連続関数 として表現されるリソースは、関数が平坦になるにつれてトゥエ・モースに収束する列を使用して最も公平に割り当てられる。例として、非線形濃度勾配を持つカラフェから同じ濃さのコーヒーをカップに注ぐ方法が示され、大衆紙に風変わりな記事が掲載された。^[20]

ジョシュア・クーパーとアーロン・ダトルは、なぜトゥーエ・モース順序が離散的なイベントに対して公平な結果をもたらすのかを示した。^[21]彼らは、両射手の射撃技術が同等に低いガロア決闘 を繰り広げる最も公平な方法を考えた。クーパーとダトルは、各決闘者は、相手の勝利の事前確率が自分のそれを超えるとすぐに射撃の機会を要求すると仮定した。彼らは、決闘者の命中確率がゼロに近づくにつれて、射撃シーケンスがトゥーエ・モース順序に収束することを証明した。そうすることで、彼らは、トゥーエ・モース順序が長さ2 ⁿのシーケンス Tn だけでなく、任意の長さのシーケンスに対して公平な結果を生み出すことを実証した。

したがって、数学的には、公平さが目標であるが、その品質が連続的に変化するか離散的に変化するかにかかわらず、前のターンが後のターンと何らかの意味のある品質において単調に異なる場合、交互のターンの代わりにThue-Morseシーケンスを使用することが支持される。 [ ^{19 ]}

スポーツ競技は、公平な順序付け問題の重要なクラスを形成します。なぜなら、厳密に交代すると、一方のチームに不公平な利点が与えられることが多いためです。イグナシオ・パラシオス・ウエルタは、サッカーのPK戦のキック順序など、さまざまなトーナメント競技の事後的な公平性を改善するために、順序付けをThue-Morseに変更することを提案しました。^[22]彼はプロの選手を対象に一連のフィールド実験を行い、最初にキックするチームがABAB（またはT ₁）を使用した場合のゲームの60％、ABBA（またはT ₂）を使用した場合のゲームの54％、完全なThue-Morse（またはT _n）を使用した場合のゲームの51％で勝利することを発見しました。その結果、ABBAはFIFA（ヨーロッパ選手権と世界選手権）とイングランド連盟プロサッカー（EFLカップ）で広範囲にわたる試験が行われています。^{[23] ABBAのサーブパターンは}、テニスのタイブレークの公平性を改善することもわかっています。^[24]競技用ボートでは、T2_は4人乗りの舵手なしのレーシングボートで横方向の力（したがって横方向の揺れ）を排除する唯一の左舷と右舷の漕ぎ手配置であり、 T3は 8人乗りボートで揺れを回避する4つのリグのうちの₁つです。 ^[25]

公平性は選手ドラフトにおいて特に重要である。多くのプロスポーツリーグは、各ラウンドで弱いチームに早い段階で選択権を与えることで、競争力の均衡を達成しようとしている。対照的に、ファンタジーフットボールリーグには修正すべき既存の不均衡がないため、「スネーク」ドラフト（前方、後方など、またはT ₁）を使用することが多い。 ^[26]イアン・アランは、「第3ラウンドの逆転」（前方、後方、後方、前方など、またはT ₂）がさらに公平になると主張した。 ^{[27]リッチマンは、「キャプテンA」と「キャプテンB」が}バスケットボールのピックアップゲームでチームを選択する最も公平な方法はT _{3 を}反映していると示唆した 。キャプテンAは1、4、6、7番目の選択肢を持ち、キャプテンBは2、3、5、8番目の選択肢を持つ。^[19]

トゥー・モース系列の最初の2kビットは^、 2の累乗を法とする多項式ハッシュ関数の広いクラスによって0にマッピングされ、ハッシュ衝突を引き起こす可能性がある。^[28]

ディリクレ級数の特定の線形結合（係数がトゥエ・モース数列の項である）は、リーマンゼータ関数を含む恒等式を生じる（Tóth, 2022 ^[29]）。例えば：

${\displaystyle {\begin{aligned}\sum _{n\geq 1}{\frac {5t_{n-1}+3t_{n}}{n^{2}}}&=4\zeta (2)={\frac {2\pi ^{2}}{3}},\\\sum _{n\geq 1}{\frac {9t_{n-1}+7t_{n}}{n^{3}}}&=8\zeta (3),\end{aligned}}}$

ここで はThue-Morse数列の項である。実際、より大きい実部を持つすべての に対して、 ${\displaystyle (t_{n})_{n\geq 0}}$${\displaystyle n^{\rm {th}}}$${\displaystyle s}$${\displaystyle 1}$

${\displaystyle (2^{s}+1)\sum _{n\geq 1}{\frac {t_{n-1}}{n^{s}}}+(2^{s}-1)\sum _{n\geq 1}{\frac {t_{n}}{n^{s}}}=2^{s}\zeta (s).}$

トゥー・モース数列は、1851年にウジェーヌ・プルーエ [fr]によって初めて研究され、^{[30]彼はそれを}数論に応用した。しかし、プルーエはこの数列について明示的には言及しなかった。これは1906年にアクセル・トゥーに委ねられ、彼はそれを用いて語の組合せ論の研究を始めた。この数列が世界的な注目を集めたのは、1921年にマーストン・モースがそれを微分幾何学に応用した時であった。この数列はこれまで何度も独立に発見されており、必ずしも専門の研究数学者によるものではない。例えば、チェスのグランドマスターで数学教師のマックス・ユーは、1929年にチェスへの応用でこれを発見した。彼は、キューブフリー特性（上記参照）を利用して、動きの繰り返しを引き分けと宣言することで、ゲームが無限に長引くのを防ぐことを目的とした3回繰り返しルールを回避する方法を示した。当時、このルールを発動するには、連続した同一の盤面の状態が必要であった。このルールは後に、同じ盤面の位置がどの時点でも 3 回繰り返されるように修正されました。これは、シーケンスから連続基準を永久に回避できることが示されるためです。

• デジャンの定理
• ファビウス関数
• トゥー・モース数列の第一階差
• グレイコード^{[31] [32]}
• コモルニク・ロレティ定数
• プルーエ・テュー・モース定数

• Bugeaud, Yann (2012)。分布法 1 とディオファントス近似。ケンブリッジ数学論文集。第 193 巻。ケンブリッジ:ケンブリッジ大学出版局。ISBN 978-0-521-11169-0.ZBL1260.11001  。​
• ロテール、M. (2005)。単語に組み合わせ論を応用。数学とその応用の百科事典。 Vol. 105. ジャン・ベルステル、ドミニク・ペラン、マキシム・クロシュモア、エリック・ラポルト、メリヤル・モーリ、ナディア・ピサンティ、マリー＝フランス・サゴ、ジェシーヌ・ライナート、ソフィー・シュバス、マイケル・ウォーターマン、フィリップ・ジャケ、ヴォイチェフ・シュパンコウスキー、ドミニク・ポラロン、ジル・シェーファーによる共同作品。ロマン・コルパコフグレゴリー・クチェロフ、ジャン＝ポール・アルーシュ、ヴァレリー・ベルテ。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-84802-2.ZBL1133.68067  。​

ウィキメディア・コモンズには、 Thue-Morse 列に関連するメディアがあります。

• 「Thue-Morse 数列」、数学百科事典、EMS Press、2001 [1994]
• ワイスタイン、エリック・W.「トゥー・モールス系列」。マスワールド。
• Allouche, J.-P.; Shallit, JO ユビキタス Prouhet-Thue-Morse シーケンス。(多くのアプリケーションといくつかの歴史が含まれています)
• (1,2) 上の Thue–Morse 列 ( OEISの列A001285 )
• OEISシーケンス A000069 (不快な数: 2 進展開で 1 が奇数個ある数)
• OEISシーケンス A001969 (邪悪な数字: 2 進展開で 1 が偶数個ある数字)
• Thue-Morseシーケンスを使用してアナログIPのDCオフセットドリフトの影響を軽減します。Thue-Morseシーケンスの技術的応用
• MusiNum - 数字の中の音楽。Thue-Morse シーケンスと関連する数列に基づいて自己相似音楽を生成するフリーウェア。
• パーカー、マット。「史上最も公平な共有シーケンス」（ビデオ）。standupmaths 。 2016年1月20日閲覧。