四角のない単語

組合せ論 では、スクエアフリーワードとは、スクエアを含まないワード（記号の並び）のことです。スクエアとは、 XXという形式のワードで、Xは空ではありません。したがって、スクエアフリーワードは、パターン XX を避けるワードとしても定義できます。

バイナリアルファベット では、正方形のない単語は空の単語、および のみです。 ${\displaystyle \{0,1\}}$${\displaystyle \epsilon ,0,1,01,10,010}$${\displaystyle 101}$

三進法アルファベットには、無限の数の平方フリー単語が存在します。長さnの三進法平方フリー単語の数を数えることは可能です。 ${\displaystyle \{0,1,2\}}$${\displaystyle c(n)}$

この数は（ ）で制限されます。^[2]の上限は、フェケテの補題とオートマトンによる近似によって求めることができます。下限は、平方自由性を保存する置換を見つけることによって求めることができます。^[2]${\displaystyle c(n)=\Theta (\alpha ^{n})}$${\textstyle 1.3017597<\alpha <1.3017619}$${\displaystyle \alpha}$

3 文字のアルファベットには無限の数のスクエアフリー単語が存在するため、3 文字を超えるアルファベットにも無限の数のスクエアフリー単語が存在することになります。

次の表は、 kが4から15の範囲で、小数点以下7桁に丸めたk進数平方自由語の正確な成長率を示しています。 ^[2]

からAへの写像を考えます。ここでA はアルファベットであり、 2次元単語と呼ばれます。 をエントリとします。が存在する場合、単語はの線であり、 に対して となります。^[3]${\displaystyle {\textbf {w}}}$${\displaystyle \mathbb {N} ^{2}}$${\displaystyle {\textbf {w}}}$${\displaystyle w_{m,n}}$${\displaystyle {\textbf {w}}(m,n)}$${\displaystyle {\textbf {x}}}$${\displaystyle {\textbf {w}}}$${\displaystyle i_{1},i_{2},j_{1},j_{2}}$${\displaystyle {\text{gcd}}(j_{1},j_{2})=1}$${\displaystyle t\geq 0,x_{t}=w_{{i_{1}}+{j_{1}t},{i_{2}}+{j_{2}t}}}$

カルピ^[4]は、16文字のアルファベット上に2次元の単語が存在し、そのすべての行が正方形でないことを証明しています。コンピュータ検索では、 7文字のアルファベット上に2次元の単語が存在し、そのすべての行が正方形でないことは示されていません。 ${\displaystyle {\textbf {w}}}$${\displaystyle {\textbf {w}}}$${\displaystyle {\textbf {w}}}$${\displaystyle {\textbf {w}}}$

Shur ^[5]は、3文字以上の任意のアルファベットに対して長さnのスクエアフリーワードを生成できるR2F （random-t(w)o-free）と呼ばれるアルゴリズムを提案している。このアルゴリズムは、エントロピー圧縮の修正に基づいており、k文字のアルファベットから文字をランダムに選択して、 ⁠ ⁠ aryスクエアフリーワードを生成します。 ${\displaystyle (k+1)}$

アルゴリズムR2Fは、
    入力:アルファベットのサイズ、
           単語の長さ、出力:長さnの⁠ ⁠項平方フリー単語w です。${\displaystyle k\geq 2}$${\displaystyle n>1}$
    ${\displaystyle (k+1)}$

    ( は文字を含むアルファベットであることに注意してください。)${\textstyle \color {gray}\Sigma _{k+1}}$${\displaystyle \color {gray}\{1,...,k+1\}}$
    （単語 に対して、は の順列であり、a がbに先行する場合、${\displaystyle \color {gray}w\in \Sigma _{k}}$${\displaystyle \color {gray}\chi _{w}}$${\displaystyle \color {gray}\Sigma _{k}}$${\displaystyle \color {gray}\chi _{w}}$w内のa
     の右端の位置は、w内のbの右端の位置の右側にあります。
     たとえば、  には があります。${\displaystyle \color {gray}w=136263163\in \Sigma _{6}}$${\displaystyle \color {gray}\chi _{w}=361245}$
を一様にランダム 
    に
    選択し、その後に他のすべての文字を昇順で
    設定し、反復回数Nを0に設定します。${\displaystyle w[1]}$${\textstyle \Sigma _{k+1}}$ ${\displaystyle \chi_{w}}$  ${\displaystyle w[1]}$${\textstyle \Sigma _{k+1}}$

    一方、 jを一様にランダムに
        選択する${\displaystyle |w|<n}$ ${\textstyle \Sigma _{k}}$wの末尾に
        追加し、最初のj要素を右にシフトしてNを1ずつ
        増分して
        更新します。wがランクrの正方形で終わる場合は、wの
            最後のr文字を削除します。${\displaystyle a=\chi _{w}[j+1]}$${\displaystyle \chi_{w}}$${\displaystyle \chi _{w}[1]=a}$
          

    戻る ​

各反復でwの最後の文字を除く任意の文字を追加できるため、すべての (k+1) 元平方フリーワードはアルゴリズム R2F の出力になります。

長さnの⁠ ⁠${\displaystyle (k+1)}$進平方フリー単語を構築するためにアルゴリズム R2F で使用されるランダムな k 進文字の期待数は、長さnの単語の平方フリー性を時間内に検証できるアルゴリズムが存在することに注意してください。Apostolico と Preparata ^{[6] は、}サフィックスツリーを使用するアルゴリズムを示しています。Crochemore ^{[7] は、}アルゴリズムで分割を使用しています。Main と Lorentz ^{[8] は、}分割統治法に基づくアルゴリズムを提供しています。単純な実装では、長さnの単語の平方フリー性を検証するために時間が必要になる場合があります。 $${\displaystyle N=n\left(1+{\frac {2}{k^{2}}}+{\frac {1}{k^{3}}}+{\frac {4}{k^{4}}}+O\left({\frac {1}{k^{5}}}\right)\right)+O(1).}$$${\displaystyle O(n\log n)}$${\displaystyle O(n^{2})}$

アクセル・トゥーによって証明されたように、3文字以上のアルファベットには、無限に長い平方のない単語が存在する。^[9]

アルファベット3の無限平方自由単語の一例は、Thue-Morse列の最初の差分をとることによって得られるアルファベット上の単語である。^[9]つまり、Thue-Morse列から ${\displaystyle \{-1,0,+1\}}$

${\displaystyle 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0...}$

それぞれの項がThue-Morse数列の連続する2項の差である新しい数列を形成する。結果として得られる平方根のない単語は

${\displaystyle 1,0,-1,1,-1,0,1,0,-1,0,1,-1,1,0,-1,...}$（OEISの配列A029883）。

ジョン・リーチ^[10]が発見した別の例は、アルファベット 上で再帰的に定義されています。⁠ ⁠ を文字 で始まる任意の平方のない単語とします。${\displaystyle \{0,1,2\}}$${\displaystyle w_{1}}$0。単語を次のように再帰的に定義します。単語は、⁠ ⁠の各部分を置き換えることによって得られます。${\displaystyle \{w_{i}\mid i\in \mathbb {N} \}}$${\displaystyle w_{i+1}}$${\displaystyle w_{i}}$0で⁠ ⁠${\displaystyle w_{i}}$と0121021201210、各1と1202102012021、それぞれ2と2010210120102。このシーケンスが無限平方自由語に収束することを証明することは可能である。

0121021201210120210201202120102101201021202102012021...

無限の平方自由語は平方自由射によって生成できます。すべての平方自由語の像が平方自由である場合、射は平方自由と呼ばれます。長さ k のすべての平方自由語の像が平方自由である場合、射は k-平方自由と呼ばれます。

Crochemore ^[11]は、一様射hが平方自由であるための必要条件は3平方自由であることであることを証明している。言い換えれば、長さ3のすべての平方自由wに対してhが平方自由である場合に限り、hは平方自由である。総当たり探索によって平方自由射を見つけることは可能である。 ${\displaystyle h(w)}$

アルゴリズムsquare-free_morphismの出力は、可能な限り最低のランクkを持つ square-free 射です
    。

     trueの場合、k_sf_words を、3 進アルファベット
        の長さkのすべてのスクエアフリー ワードのリストに設定します。k_sf_wordsの各に対して、 k_sf_wordsの各に対して、k_sf_wordsの各に対して、ifの場合、現在のループを終了します(次へ進む)
                     。ifの場合、長さwのすべてのスクエアフリーに対して、がスクエアフリーの場合、${\displaystyle k=3}$
    
           ${\displaystyle h(0)}$   
             ${\displaystyle h(1)}$   
                 ${\displaystyle h(2)}$   
                     ${\displaystyle h(1)=h(2)}$ 
                        ${\displaystyle h(1)}$ ${\displaystyle h(0)\neq h(1)}$  ${\displaystyle h(2)\neq h(0)}$ 
                         ${\displaystyle h(w)}$ 3 次に
                            kを
        増分して返す ${\displaystyle h(0),h(1),h(2)}$1

3 進アルファベットでは、ランク 11 の一様自由平方射が正確に 144 個存在し、ランクが 11 より低い一様自由平方射は存在しません。

無限の平方自由語を得るには、次のような平方自由語から始める。0、それに平方自由射h を連続的に適用します。結果として得られるワードは平方自由性の特性を保持します。たとえば、h を平方自由射とすると、は無限平方自由ワードになります。 ${\displaystyle w\to \infty }$${\displaystyle h^{w}(0)}$

注意すべきは、3進アルファベット上の射が一様でない場合、この射が5平方自由である場合に限り、この射は平方自由である。^[11]

三進法のアルファベットでは、長さが13を超える平方のない単語には、平方のない2文字の組み合わせがすべて含まれます。^[12]

これは、2 文字の組み合わせab を除いたスクエアフリー単語を作成することで証明できます。結果として、bcba cbca cbaca は、組み合わせab を除いた最長のスクエアフリー単語となり、その長さは 13 になります。

3 文字以上のアルファベットでは、任意の 2 文字の組み合わせのない、任意の長さの正方形のない単語が存在することに注意してください。

三進法のアルファベットでは、長さが36を超える平方のない単語には、平方のない3文字の組み合わせがすべて含まれます。^[12]

ただし、 abaという 3 文字の組み合わせを含まない、任意の長さのスクエアフリー単語が存在します。

3 文字以上のアルファベットでは、任意の 3 文字の組み合わせのない、任意の長さの正方形のない単語が存在することに注意してください。

有限単語wにおける文字aの密度は次のように定義されます。ここで、は単語における文字aの出現回数、は単語の長さです。無限単語における文字aの密度は次のように定義されます。ここで、は長さlの単語wの接頭辞です。^[13]${\displaystyle {\frac {|w|_{a}}{|w|}}}$${\displaystyle |w|_{a}}$${\displaystyle w}$${\displaystyle |w|}$${\displaystyle \liminf _{l\to \infty }{\frac {|w_{l}|_{a}}{|w_{l}|}}}$${\displaystyle w_{l}}$

無限三元平方自由単語における文字aの最小密度は に等しい。^[13]${\displaystyle {\frac {883}{3215}}\approx 0.2747}$

無限三元平方自由単語における文字aの最大密度はに等しい。^[14]${\displaystyle {\frac {255}{653}}\approx 0.3905}$

• Berstel, Jean ; Lauve, Aaron; Reutenauer, Christophe; Saliola, Franco V. (2009)。単語の組合せ論。クリストッフェル語と単語の繰り返し。CRM モノグラフ シリーズ。第 27 巻。プロビデンス、ロードアイランド州:アメリカ数学協会。ISBN 978-0-8218-4480-9.ZBL1161.68043  。​
• ロテール、M. (1997)。単語の組合せ論。ケンブリッジ：ケンブリッジ大学出版局。ISBN 978-0-521-59924-5。。
• ロテール、M. (2011)。単語の代数的組合せ論。数学とその応用百科事典。第90巻。ジャン・ベルステルとドミニク・ペランによる序文付き（2002年ハードカバー版の再版）。ケンブリッジ大学出版局。ISBN 978-0-521-18071-9.ZBL1221.68183  。​
• ピテアス・フォッグ、N. (2002)。Berthé, ヴァレリー;フェレンチ、セバスチャン。モーデュイ、クリスチャン。シーゲル、アン (編)。力学、算術、組み合わせ論における置換。数学の講義ノート。 Vol. 1794年。ベルリン：シュプリンガー・フェルラーク。ISBN 978-3-540-44141-0.ZBL1014.11015  .​