メルセンヌ予想

ウィキペディア

メルセンヌ予想

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/11/02 15:48 UTC 版)

数学において、メルセンヌ予想（メルセンヌよそう、英: Mersenne conjectures）とは、2ⁿ − 1（n は自然数）で表されるような数であるメルセンヌ数のうち素数のもの（メルセンヌ素数）の特徴づけに関する予想である。

マラン・メルセンヌによる元々のメルセンヌ予想の内容

メルセンヌ予想はマラン・メルセンヌによって「Cogitata Physica-Mathematica」（1644年発表; 例えば Dickson 1919を参照）の中で次のような形で初めて言及された。すなわち、「n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の n に対して 2ⁿ − 1 は素数であり、これ以外のすべて正の整数に対しては n ≤ 257 の範囲で 2ⁿ − 1 は合成数である」というものであった。しかし、これらの n に対する 2ⁿ − 1 は、素数判定の計算をするにはあまりに巨大すぎて（例えば 2²⁵⁷ - 1 ）、メルセンヌはそれらの数字すべてが本当に素数であるか判定をしなかったし、できなかった。ただし、17世紀当時ではメルセンヌ以外の数学者も同様にこのような巨大な数の素数判定はできなかったであろう。3世紀後、リュカ–レーマー・テストのような新たな素数判定の技法の発見により、メルセンヌ予想は5つの間違いを含んでいることが明らかになった。まず、これらの n のうち、 n = 67, 257 の2つの場合において 2ⁿ − 1 は合成数であるし、n = 61, 89, 107 の3つの場合において 2ⁿ − 1 は素数となるがメルセンヌはこれを見落としていた。正しくは、 n ≤ 257 の範囲でメルセンヌ数が素数となるような n は次の通りである。 n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107, 127。メルセンヌの元々の予想は間違っていた一方で、 新メルセンヌ予想（New Mersenne conjecture）と Lenstra–Pomerance–Wagstaff 予想の研究へと繋がった。

新メルセンヌ予想

新メルセンヌ予想（New Mersenne conjecture）あるいは Bateman, Selfridge and Wagstaff conjecture (Bateman et al. 1989) とは、「任意の奇の自然数 p に対して、 もし次の条件のうち2つを満たしているならば、3つめの条件も同様に満たされるであろう」というものである。

1. ある自然数 k に対して、p = 2^k ± 1 あるいは p = 4^k ± 3 (オンライン整数列大辞典の数列 A122834)
2. 2^p − 1 が素数 （メルセンヌ素数） (A000043)
3. (2^p + 1) / 3 が素数 （ワグスタッフ素数） (A000978)

もし p が奇の合成数であるなら、2^p − 1 および (2^p + 1)/3 は両方とも合成数である。すなわち、この予想の真偽は素数判定のみで示すことができる。

現在、これら3つの条件をすべて満たす既知の数字は 3, 5, 7, 13, 17, 19, 31, 61, 127 である（A107360）。なお、この新メルセンヌ予想は「127よりも大きい数字はこれら3つのすべての条件を満たさないだろう」ということも含む。

3つの条件のうち、少なくとも1つを満たす素数は次の通り。
2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 67, 79, 89, 101, 107, 127, 167, 191, 199, 257, 313, 347, 521, 607, 701, 1021, 1279, 1709, 2203, 2281, 2617, 3217, 3539, 4093, 4099, 4253, 4423, 5807, 8191, 9689, 9941, ...（A120334による数列）

なお、67と257 (67=2⁶+3, 257=2⁸+1) は元々のメルセンヌ予想に含まれていたが、一方で89と107は元々のメルセンヌ予想に含まれていなかった。そのため、メルセンヌは「ある自然数 k に対して p = 2^k ± 1 もしくは p = 4^k ± 3 を必要十分条件として 2^p - 1 が素数である」というように考えていた可能性がある（A122834）。

新メルセンヌ予想は数世紀も前のメルセンヌ予想を甦らせようという試みにも受け取られるが、そのような認識は正しくない。しかし、Robert D. Silvermanによれば、en:John Selfridgeは「新メルセンヌ予想は既知のデータに合うように選ばれており、これらに対する反例は全くあり得そうにないため『明らかに真である』」と述べている。この問いかけは新メルセンヌ予想の証明の必要性に対する興味深い考察であると言える。

Renaud Lifchitzは3つの条件のうち1つを持つことが既に知られているすべての奇素数を検定することで新メルセンヌ予想が20,996,010以下のすべての整数に対して真であることを示した。Lifchitzのウェブサイトでは20,996,010までのすべての数字の検定についてドキュメント化している。さらに、新メルセンヌ素数に関する現在の最新のニュースに関してはThe New Mersenne Prime conjectureを参照。

Lenstra–Pomerance–Wagstaff 予想

Hendrik Lenstra, Carl Pomerance, Samuel S. Wagstaff Jr. はメルセンヌ素数が無限にあることを予想した。予想は正確には、x より小さいメルセンヌ素数の個数は漸近的に

$e^{\gamma }\cdot \log \log(x)/\log(2)$