スタンレーシーケンス

数学において、スタンレー数列は、等差数列 を回避するように数列の要素を選択する貪欲アルゴリズムによって生成される整数数列です。 が、どの 3 つの要素も等差数列を形成しない非負の整数の有限集合 (つまり、セーラム・スペンサー集合) である場合、 から生成されるスタンレー数列は、の要素からソートされた順序で開始し、数列の各連続する要素が、既に選択された数よりも大きく、かつ、それらの数と 3 項等差数列を形成しない数となるように繰り返し選択します。これらの数列は、リチャード・P・スタンレーにちなんで名付けられました。 ${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$

空集合から始まるスタンレー数列は、3進数表現で0と1の数字のみを持つ数から構成される。^[1]つまり、3進数で書くと2進数のように見える。これらの数は

0、1、3、4、9、10、12、13、27、28、30、31、36、37、39、40、...（OEISのシーケンスA005836）

スタンレー数列として構築することにより、この数列は辞書式に最初の等差数列フリー数列となる。その要素は、 3の異なる累乗の和、番目の中心二項係数が3を法として1となる数、およびバランスのとれた3進数表現がその3進数表現と同じになる数である。^[2]${\displaystyle n}$${\displaystyle n}$

この数列を3進数から構築することは、4進数表現が数字0と1のみを持つ数列であるモーザー・ド・ブリュイン数列の構築や、3進数表現が数字0と2のみを使用する区間内の実数の部分集合であるカントール集合の構築に類似している。より一般的には、これらは2正則数列であり、乗数2の線形再帰関係によって定義される整数列のクラスの1つである。 ^[3]${\displaystyle [0,1]}$

この数列には2の累乗が3つ含まれている: 1、4、256 = 3 ⁵ + 3 ² + 3 + 1。ポール・エルデシュは、これらがこの数列に含まれる2の累乗のみであると推測した。^[4]

アンドリュー・オドリツコとリチャード・P・スタンレーは、 2進-3進数列、およびまたはから始まる他のスタンレー数列において、ある閾値までの要素の数はに比例して増加することを観察した。他の開始集合では、彼らが検討したスタンレー数列はより不規則に、しかしよりまばらに増加するように見えた。^[1]たとえば、最初の不規則なケースは であり、これは数列を生成する。 ${\displaystyle n}$${\displaystyle \{0,3^{k}\}}$${\displaystyle \{0,2\cdot 3^{k}\}}$${\displaystyle n^{\log _{2}3}\approx n^{0.631}}$${\displaystyle \{0,s\}}$${\displaystyle s=4}$

0、4、5、7、11、12、16、23、26、31、33、37、38、44、49、56、73、78、80、85、95、99、...（OEISのシーケンスA005487）

オドリツコとスタンレーは、そのような場合には任意の閾値までの要素の数は であると推測した。つまり、スタンレー数列の成長率には、2元-3元数列と同様の成長率を持つものと、はるかに小さい成長率を持つものとの二分法がある。この推測によれば、中間の成長率を持つスタンレー数列は存在しないはずである。^{[1] [5]}${\displaystyle n}$${\displaystyle O{\bigl (}{\sqrt {n\log n}}{\bigr )}}$

モイは、スタンレー数列が、緩慢な増加の数列について推測された境界よりも大幅に遅く増加することはあり得ないことを証明した。すべてのスタンレー数列には、 までの要素が含まれる。より正確には、モイは、すべてのそのような数列、すべての、および十分に大きいすべての について、要素の数は少なくとも であることを示した。^[6] その後の著者らはこの境界の定数因子を改良し、^[7] として増加するスタンレー数列については、その増加率の定数因子は、分母が 3 の累乗である任意の有理数になり得ることを証明した。^[8]${\displaystyle \Omega {\bigl (}{\sqrt {n}}{\bigr )}}$${\displaystyle n}$${\displaystyle \epsilon >0}$${\displaystyle n}$${\displaystyle ({\sqrt {2}}-\varepsilon ){\sqrt {n}}}$${\displaystyle n^{\log _{2}3}}$

2元-3元数列のバリエーション（各要素に1が加算される）は、1936年にポール・エルデシュとパル・トゥランによって検討され、3項の等差数列が存在しないことに気づき、等差数列のない最も密な数列であると（誤って）推測しました。^[9]

1978年にアンドリュー・オドリツコと共同で行った未発表の研究で、リチャード・P・スタンレーは貪欲アルゴリズムを使って漸進的シーケンスを生成する実験を行った。彼らが研究したシーケンスは、初期セットのスタンレーシーケンスとまったく同じであった。^[1]${\displaystyle \{0,s\}}$

スタンレー数列は、エルデシュ（死後）と他の4人の著者によって1999年に発表された論文で命名され、以外の開始集合に一般化された。 ^[5]${\displaystyle \{0,s\}}$

• モイ、リチャード A. (2017)、奇数文字を含むスタンレー配列、arXiv : 1707.02037
• モイ、リチャード A.; ロルニック、デビッド (2016)、「スタンレーシーケンスの新しい構造」、離散数学、339 (2): 689–698、arXiv : 1502.06013、doi :10.1016/j.disc.2015.10.017、MR  3431382、S2CID  6660477
•  ロルニック、デイビッド (2017)、「スタンレーシーケンスの分類について」、ヨーロッパ組合せ論ジャーナル、59 :51–70、arXiv : 1408.1940、doi : 10.1016/j.ejc.2016.06.004、MR3546902
• Sawhney, Mehtaab (2017)、「スタンレーシーケンスの特性値」、arXiv : 1706.05444