パリティ問題
In number theory, a limitation of sieve theory

数論において、パリティ問題とは、多くの種類の素数計算問題において篩が良好な推定値を与えることを妨げる、篩理論における限界を指します。この問題は1949年にアトル・セルバーグによって特定され、命名されました。1996年頃から、ジョン・フリードランダーとヘンリク・イワニエツは、パリティ問題の障害を軽減するパリティに敏感な篩をいくつか開発しました

声明

テレンス・タオは、この問題について次のように「大まかに」述べました。[1]

パリティ問題。A が、すべての要素が奇数の素数の積（またはすべての要素が偶数の素数の積）である集合である場合、（追加の要素を加えない限り）ふるい理論はAの大きさの非自明な下限を与えることができない。また、いかなる上限も真実から2倍以上ずれる必要がある。

この問題は、ふるいが「素数を検出する」こと、言い換えれば、ある性質を持つ素数の個数に非自明な下限を与えることがなぜ難しいのかを説明できる可能性があるため、重要である。例えば、ある意味では、チェンの定理は双子素数予想の解に非常に近い。なぜなら、 p + 2 が素数か2つの素数の積（半素数）となるような素数pが無限に存在すると述べているからである。パリティ問題は、対象となるケースでは素因数が奇数（つまり1）であるため、ふるいを用いて2つのケースを分離することは不可能であることを示唆している。

例

この例はセルバーグによるもので、コジョカルとマーティによるヒント付きの練習問題として示されています。[2] ：133–134 

問題は、x ≤ でx 1/2以下の素因数を持たず、素因数が偶数個 (または奇数個) の数がいくつあるかを個別に推定することです。 Brun型またはSelberg型のふるいにおける重みの選択に関係なく、両方の問題に対して得られる上限は少なくとも (2 + o (1)) x / ln xになることが示されています。 しかし、実際には、因数が偶数個の集合は空なので、サイズは 0 になります。因数が奇数個の集合は、x 1/2と xの間にある素数だけなので、素数定理により、そのサイズは (1 + o (1)) x / ln xになります。 したがって、これらのふるい法では、最初の集合に対して有用な上限を与えることができず、2 番目の集合の上限を 2 倍過大評価してしまいます。

パリティ感受性ふるい

1996年頃から、ジョン・フリードレンダーとヘンリック・イワニエツは、パリティ問題を「打破」するための新しいふるい技術を開発しました。[3] [4] これらの新しい手法の成果の一つは、a 2 + b 4の形の素数が無限に存在することを述べたフリードレンダー・イワニエツの定理です

グリン・ハーマンはパリティ問題をふるいにおけるタイプI情報とタイプII情報の区別に関連付けています。 [5]

カラツバ現象

2007年、アナトリー・アレクセーヴィッチ・カラツバは、素因数の個数が与えられた等差数列の数の間に不均衡があることを発見しました。彼の論文[6] [7]は彼の死後に出版されました

を自然数（正の整数）の集合、すなわち数 とします。素数の集合、すなわち 、 、でそれぞれ異なる約数（つまりと）を2つだけ持つ整数 の集合は、 、と表されます。すべての自然数、、 は素数の積（必ずしも異なるとは限らない）として表すことができます。つまり であり、このような表現は因数の位数まで一意です。 N {\displaystyle \mathbb {N} } 1 , 2 , 3 , … {\displaystyle 1,2,3,\dots } n ∈ N {\displaystyle n\in \mathbb {N} } n > 1 {\displaystyle n>1} n {\displaystyle n} 1 {\displaystyle 1} P {\displaystyle \mathbb {P} } P = { 2 , 3 , 5 , 7 , 11 , … } ⊂ N {\displaystyle \mathbb {P} =\{2,3,5,7,11,\dots \}\subset \mathbb {N} } n ∈ N {\displaystyle n\in \mathbb {N} } n > 1 {\displaystyle n>1} n = p 1 p 2 … p k , {\displaystyle n=p_{1}p_{2}\dots p_{k},} p 1 ∈ P ,   p 2 ∈ P ,   … ,   p k ∈ P {\displaystyle p_{1}\in \mathbb {P} ,\ p_{2}\in \mathbb {P} ,\ \dots ,\ p_{k}\in \mathbb {P} }

標準表現において、偶数の素因数を持つ正の整数で構成される最初の集合と、奇数の素因数を持つ正の整数で構成される 2 つの集合を形成すると、2 つの集合はほぼ同じサイズになります。

しかし、もし二つの集合を、等差数列、 、、といった、標準表現に素数が含まれない正の整数に限定すると、これらの正の整数のうち、素因数が偶数個のものは、素因数が奇数個のものよりも少なくなる傾向があります。カラツバはこの性質を発見しました。彼はまた、この現象の公式も発見しました。それは、素因数が一定の制約に従う場合の、奇数個と偶数個の素因数を持つ自然数集合の基数の差を表す公式です。いずれの場合も、関係する集合は無限であるため、「大きい」と「小さい」とは、素数の上限が無限大になる集合の比の極限を意味します。等差数列を含む素数の場合、カラツバはこの極限が無限であることを証明しました。 6 m + 1 {\displaystyle 6m+1} m = 1 , 2 , … {\displaystyle m=1,2,\dots } k m + l {\displaystyle km+l} 1 ≤ l < k {\displaystyle 1\leq l<k} ( l , k ) = 1 {\displaystyle (l,k)=1} m = 0 , 1 , 2 , … {\displaystyle m=0,1,2,\dots }

数学用語を使用して、カラツバ現象を言い換えます。

とをの部分集合とし、 が偶数個の素因数を含む場合 が成り立ち、 が奇数個の素因数を含む場合 が成り立つものとする。直感的に、2つの集合との大きさはほぼ同じである。より正確には、すべての に対して、と を定義する。ここではとなるようなからのすべての数の集合の濃度であり、は となるようなからのすべての数の集合の濃度である。との漸近的挙動はE. Landauによって導かれた：[8] N 0 {\displaystyle \mathbb {N} _{0}} N 1 {\displaystyle \mathbb {N} _{1}} N {\displaystyle \mathbb {N} } n ∈ N 0 {\displaystyle n\in \mathbb {N} _{0}} n {\displaystyle n} n ∈ N 1 {\displaystyle n\in \mathbb {N} _{1}} n {\displaystyle n} N 0 {\displaystyle \mathbb {N} _{0}} N 1 {\displaystyle \mathbb {N} _{1}} x ≥ 1 {\displaystyle x\geq 1} n 0 ( x ) {\displaystyle n_{0}(x)} n 1 ( x ) {\displaystyle n_{1}(x)} n 0 ( x ) {\displaystyle n_{0}(x)} n {\displaystyle n} N 0 {\displaystyle \mathbb {N} _{0}} n ≤ x {\displaystyle n\leq x} n 1 ( x ) {\displaystyle n_{1}(x)} n {\displaystyle n} N 1 {\displaystyle \mathbb {N} _{1}} n ≤ x {\displaystyle n\leq x} n 0 ( x ) {\displaystyle n_{0}(x)} n 1 ( x ) {\displaystyle n_{1}(x)}

n 0 ( x ) = 1 2 x + O ( x e − c ln ⁡ x ) , n 1 ( x ) = 1 2 x + O ( x e − c ln ⁡ x ) ; c > 0. {\displaystyle n_{0}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right),n_{1}(x)={\frac {1}{2}}x+O\left(xe^{-c{\sqrt {\ln x}}}\right);c>0.}

これは

n 0 ( x ) ∼ n 1 ( x ) ∼ 1 2 x , {\displaystyle n_{0}(x)\sim n_{1}(x)\sim {\frac {1}{2}}x,}

とが漸近的に等しい ことを示しています n 0 ( x ) {\displaystyle n_{0}(x)} n 1 ( x ) {\displaystyle n_{1}(x)}

さらに、

n 1 ( x ) − n 0 ( x ) = O ( x e − c ln ⁡ x ) , {\displaystyle n_{1}(x)-n_{0}(x)=O\left(xe^{-c{\sqrt {\ln x}}}\right),}

2つの集合の濃度の差が小さくなるように

一方、を自然数、 を自然数列 とすると、; ; それぞれは を法として異なる。 を数列 に属する素数の集合とします 。（ はを割り切れないすべての素数の集合です ）。 k ≥ 2 {\displaystyle k\geq 2} l 1 , l 2 , … l r {\displaystyle l_{1},l_{2},\dots l_{r}} 1 ≤ r < φ ( k ) {\displaystyle 1\leq r<\varphi (k)} 1 ≤ l j < k {\displaystyle 1\leq l_{j}<k} ( l j , k ) = 1 {\displaystyle (l_{j},k)=1} l j {\displaystyle l_{j}} k {\displaystyle k} j = 1 , 2 , … r . {\displaystyle j=1,2,\dots r.} A {\displaystyle \mathbb {A} } k n + l j {\displaystyle kn+l_{j}} j ≤ r {\displaystyle j\leq r} A {\displaystyle \mathbb {A} } k {\displaystyle k}

を の素因数を含まない自然数の集合とし、を の素因数が偶数である数の部分集合とし、を の素因数が奇数である数の部分集合とする。関数を定義する。 N ∗ {\displaystyle \mathbb {N} ^{*}} A {\displaystyle \mathbb {A} } N 0 ∗ {\displaystyle \mathbb {N} _{0}^{*}} N ∗ {\displaystyle \mathbb {N} ^{*}} N 1 ∗ {\displaystyle \mathbb {N} _{1}^{*}} N ∗ {\displaystyle \mathbb {N} ^{*}}

n ∗ ( x ) = ∑ n ≤ x n ∈ N ∗ 1 ; n 0 ∗ ( x ) = ∑ n ≤ x n ∈ N 0 ∗ 1 ; n 1 ∗ ( x ) = ∑ n ≤ x n ∈ N 1 ∗ 1. {\displaystyle n^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} ^{*}\end{array}}1;n_{0}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{0}^{*}\end{array}}1;n_{1}^{*}(x)=\displaystyle \sum _{\begin{array}{c}n\leq x\\n\in \mathbb {N} _{1}^{*}\end{array}}1.}

カラツバは、 に対して漸近式 x → + ∞ {\displaystyle x\to +\infty }

n 1 ∗ ( x ) − n 0 ∗ ( x ) ∼ C n ∗ ( x ) ( ln ⁡ x ) 2 ( r φ ( k ) − 1 ) , {\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim Cn^{*}(x)(\ln x)^{2\left({\frac {r}{\varphi (k)}}-1\right)},}

は有効です。ここで、は正の定数です。 C {\displaystyle C}

彼はまた、他の自然数集合、例えば 2 つの平方数の和の形で表現可能な数に対しても類似の定理を証明することが可能であること、またすべての因数が に属する自然数集合が類似の漸近挙動を示すことも示した。 A {\displaystyle \mathbb {A} }

カラツバ定理は、 が特定の無限の素数集合である 場合に一般化されました。 A {\displaystyle \mathbf {A} }

カラツバ現象は次の例で説明される。正規表現に数列,に属する素数を含まない自然数を考える。この現象は次の式で表される。 6 m + 1 {\displaystyle 6m+1} m = 1 , 2 , … {\displaystyle m=1,2,\dots }

n 1 ∗ ( x ) − n 0 ∗ ( x ) ∼ π 8 3 n ∗ ( x ) ln ⁡ x , x → + ∞ . {\displaystyle n_{1}^{*}(x)-n_{0}^{*}(x)\sim {\frac {\pi }{8{\sqrt {3}}}}{\frac {n^{*}(x)}{\ln x}},\qquad x\to +\infty .}

注釈

  1. ^ タオ、テレンス(2007年6月5日). 「未解決問題：ふるい理論におけるパリティ問題」 . 2008年8月11日閲覧
  2. ^ Cojocaru, Alina Carmen ; M. Ram Murty (2005).ふるい法とその応用入門. ロンドン数学会学生テキスト. 第66巻. ケンブリッジ大学出版局. ISBN  0-521-61275-6。
  3. ^ フリードランダー、ジョン、ヘンリク・イワニエツ(1997-02-18). 「パリティに敏感なふるいを用いた多項式の素数のカウント」米国科学アカデミー紀要. 94 (4): 1054–1058 .書誌コード:1997PNAS...94.1054F. doi : 10.1073/pnas.94.4.1054 . PMC 19742. PMID 11038598.  1054–1058 
  4. ^ Friedlander, John ; Henryk Iwaniec (1998). 「素数のための漸近ふるい」Annals of Mathematics . 148 (3): 1041– 1065. arXiv : math/9811186 . Bibcode :1998math.....11186F. doi :10.2307/121035. JSTOR  121035. S2CID  11574656.
  5. ^ ハーマン、グリン(2007).素数検出ふるい. ロンドン数学会モノグラフ. 第33巻. プリンストン大学出版局. pp. 45, 335. ISBN 978-0-691-12437-7. Zbl  1220.11118.
  6. ^ Karatsuba, AA (2011). 「素数集合の性質」.ロシア数学概論. 66 (2): 209– 220.書誌コード:2011RuMaS..66..209K. doi :10.1070/RM2011v066n02ABEH004739
  7. ^ Karatsuba, AA (2011). 「素数集合の自然数の乗法基底としての性質」『ドクラディ数学』（84:1）：1-4 .
  8. ^ E. ランダウ (1912)。 「Uber die Anzahl der Gitter punkte in gewissen Bereichen」。ゴット。ナクリヒト。 : 687 – 771。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Parity_problem&oldid=1317481477"