シドン配列

数論において、シドン列は、すべてのペアごとの和( について)が異なる自然数の列です。シドン列はシドン集合とも呼ばれ、フーリエ級数の研究でこの概念を導入したハンガリーの数学者シモン・シドンにちなんで名付けられました。 ${\displaystyle A=\{a_{0},a_{1},a_{2},\dots \}}$${\displaystyle a_{i}+a_{j}}$ ${\displaystyle i\leq j}$

^シドン[1]によって提起されたシドン列の研究における主な問題は、ある限界までシドン列が含むことができる要素の最大数を見つけることである。膨大な研究にもかかわらず^[2] 、この問題は未解決のままである。^[3]${\displaystyle x}$

ポール・エルデシュとパル・トゥランは、任意の に対して、シドン数列においてより小さい要素の数は最大 であることを証明しました。数年前、ジェームズ・シンガーはx未満の項を持つシドン数列を構築しました。上限は 1969 年に に、2023 年に に改善されまし^た。[ 5 ^]${\displaystyle x>0}$${\displaystyle x}$${\displaystyle {\sqrt {x}}+O({\sqrt[{4}]{x}})}$${\displaystyle {\sqrt {x}}(1-o(1))}$${\displaystyle {\sqrt {x}}+{\sqrt[{4}]{x}}+1}$${\displaystyle {\sqrt {x}}+0.998{\sqrt[{4}]{x}}}$

1994年にエルデシュは、この境界の証明または反証に対して500ドルの賞金を出しました。^[6]${\displaystyle {\sqrt {x}}+o(x^{\varepsilon })}$

シドン部分集合は、の全てのシドン部分集合について最大値が取られるとき、稠密であると呼ばれる。稠密シドン集合の構造については豊富な文献があり^{[7] [8]}、エルデシュ・トゥラン、 [ ^9]シンガー、^[10]ボーズ、^[11]スペンス、^{[12] [13]}ヒューズ^[14]およびシレルエロ^[15]による古典的な構成は、稠密シドン集合がを満たすことを確立している。ルザが指摘したように、「どういうわけか、稠密シドン集合の既知の構成はすべて素数を含む」^{[16] 。}${\displaystyle A\subset [n]:=\{1,2,\dots ,n\}}$${\displaystyle \left|A\right|=\max \left|S\right|}$${\displaystyle [n]}$ ${\displaystyle A}$${\displaystyle \left|A\right|\geq \left(1-o(1)\right){\sqrt {n}}}$

バラスブラマニアンとダッタ^[17]の最近の結果によれば、稠密なシドン集合が濃度を持つ場合、 ${\displaystyle A=\{a_{1},\dots ,a_{\left|A\right|}\}\subset [n]}$${\displaystyle |A|=n^{1/2}-L^{\prime }}$

${\displaystyle a_{m}=m\cdot n^{1/2}+{\mathcal {O}}\left(n^{7/8}\right)+{\mathcal {O}}\left(L^{1/2}\cdot n^{3/4}\right)}$

ここで、これは次のようないくつかの有用な漸近結果を直接的に与えます。 ${\displaystyle L=\max\{0,L^{\prime }\}}$

${\displaystyle \sum _{a\in A}a^{\ell }={\frac {1}{\ell +1}}\cdot n^{\frac {2\ell +1}{2}}+{\mathcal {O}}\left(n^{\frac {8\ell +3}{8}}\right)+{\mathcal {O}}\left(L^{1/2}\cdot n^{\frac {4\ell +1}{4}}\right)}$

任意の正の整数に対して。 ${\displaystyle \ell }$

エルデシュはまた、 がその要素の数を まで表す任意の特定の無限シドン列に対して、 であることも示しました。つまり、無限シドン列は最も密な有限シドン列よりも薄いということです。 ${\displaystyle A}$${\displaystyle A(x)}$${\displaystyle x}$$${\displaystyle \liminf _{x\to \infty }{\frac {A(x){\sqrt {\log x}}}{\sqrt {x}}}\leq 1.}$$

反対方向では、ChowlaとMianは貪欲アルゴリズムが任意のに対してとなる無限シドン列を与えることを観察した。^[18] Ajtai、Komlós、Szemerédiはこれを改良し、となるシドン列を 構築した^[19]。${\displaystyle A(x)>c{\sqrt[{3}]{x}}}$${\displaystyle x}$ $${\displaystyle A(x)>{\sqrt[{3}]{x\log x}}.}$$

これまでのところ、最も良い下限値はImre Z. Ruzsaによって与えられ、となるシドン列が存在することを 証明しました^[20] 。Erdős は となる 無限シドン集合が存在すると予想しました。彼とRényi は、予想密度 となるが、任意の自然数に対して方程式 の解が最大で存在するような定数が存在するという弱い性質のみを満たす列の存在を示しました^[21]。(シドン列であるためには である必要があります。) $${\displaystyle A(x)>x^{{\sqrt {2}}-1-o(1)}}$$${\displaystyle A}$${\displaystyle A(x)>x^{1/2-o(1)}}$${\displaystyle \{a_{0},a_{1},\dots \}}$${\displaystyle k}$${\displaystyle n}$${\displaystyle k}$${\displaystyle a_{i}+a_{j}=n}$${\displaystyle k=1}$

エルデシュはさらに、自然数における値がシドン列を形成するような非定数の整数係数 多項式が存在すると予想した。具体的には、5 乗の集合がシドン集合であるかどうかを問うた。ルザは、関数の値域がシドン列となるような を持つ実数が存在することを示してこれに近づいた。ここで、 は整数部を表す。 は無理数であるため、この関数は多項式ではない。5 乗の集合がシドン集合であるという主張は、ランダー、パーキン、セルフリッジによる後の予想の特殊なケースである。 ${\displaystyle c}$${\displaystyle 0<c<1}$${\displaystyle f(x)=x^{5}+\lfloor cx^{4}\rfloor }$${\displaystyle \lfloor \ \rfloor }$${\displaystyle c}$${\displaystyle f(x)}$

漸近基底を形成するシドン列の存在（十分に大きい自然数はすべて、その列の数の和として表すことができることを意味する）は、2010 年にに対して証明され、 ^[22] 2014 年に に対して証明され、^[23]（ より小さい項が 1 つある 4 つの項の和、任意に小さい正の に対して）は 2015 年に^[24]、2023 年にはプレプリントとして^{[25]証明された。 [26]}この後者の問題は、1994 年にエルデシュ、サルコジ、ソスの論文で問題として提起された。^[27]${\displaystyle m}$${\displaystyle n}$${\displaystyle m}$${\displaystyle m=5}$ ${\displaystyle m=4}$ ${\displaystyle m=3+\varepsilon }$${\displaystyle n^{\varepsilon }}$${\displaystyle \varepsilon }$${\displaystyle m=3}$

すべての有限シドン集合はゴロム定規であり、逆もまた同様です。

これを確認するには、がシドン集合でありゴロム定規ではないという矛盾を仮定します。これはゴロム定規ではないので、 となる要素が 4 つ存在する必要があります。したがって、 となり、これはシドン集合であるという命題と矛盾します。したがって、すべてのシドン集合はゴロム定規でなければなりません。同様の議論により、すべてのゴロム定規はシドン集合でなければなりません。 ${\displaystyle S}$${\displaystyle a_{i}-a_{j}=a_{k}-a_{l}}$${\displaystyle a_{i}+a_{l}=a_{k}+a_{j}}$${\displaystyle S}$

• モーザー・デ・ブリュイン数列
• サムセット