Mersenne gissar

Inom matematiken handlar Mersenne -förmodningarna om karaktäriseringen av ett slags primtal som kallas Mersenneprimtal , vilket betyder primtal som är en potens av två minus ett.

Original Mersenne gissning

Originalet, kallat Mersennes gissning , var ett uttalande av Marin Mersenne i hans Cogitata Physico-Mathematica (1644; se t.ex. Dickson 1919) att talen $2^{n}-1$ var primtal för n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 och 257, och var sammansatta för alla andra positiva heltal n ≤ 257. På grund av storleken på dessa siffror gjorde och kunde inte Mersenne testa alla av dem, inte heller hans jämnåriga på 1600-talet. Det fastställdes så småningom, efter tre århundraden och tillgången på nya tekniker som Lucas–Lehmer-testet , att Mersennes gissning innehöll fem fel, nämligen två är sammansatta (de som motsvarar primtal n = 67, 257) och tre utelämnade primtal ( de som motsvarar primtal n = 61, 89, 107). Den korrekta listan är: n = 2, 3, 5, 7, 13, 17, 19, 31, 61, 89, 107 och 127.

Även om Mersennes ursprungliga gissning är falsk, kan den ha lett till den nya Mersenne-förmodan .

Ny Mersenne-gissning

New Mersenne-förmodan eller Bateman, Selfridge och Wagstaff-förmodan (Bateman et al. 1989) säger att för varje udda naturligt tal p , om något av två av följande villkor gäller, så gäller det tredje:

p = 2 ^k ± 1 eller p = 4 ^k ± 3 för något naturligt tal k . ( OEIS : A122834 )
2 ^p − 1 är primtal (en Mersenne primtal ). ( OEIS : A000043 )
(2 ^p + 1)/3 är primtal (en Wagstaff primtal ). ( OEIS : A000978 )

Om p är ett udda sammansatt tal, så är 2 ^p − 1 och (2 ^p + 1)/3 båda sammansatta. Därför är det bara nödvändigt att testa primtal för att verifiera sanningen i gissningarna.

För närvarande är de kända siffrorna för vilka alla tre villkoren gäller: 3, 5, 7, 13, 17, 19, 31, 61, 127 (sekvens A107360 i OEIS ) . Det är också en gissning att inget tal som är större än 127 uppfyller alla tre villkoren. Från och med februari 2020 är alla Mersenne-primtal upp till 2 ^43112609 − 1 kända, och för inget av dessa gäller det tredje villkoret förutom de som nyss nämnts.

Primer som uppfyller minst ett villkor är

2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 43, 61, 67, 79, 89, 101, 107, 127, 167, 191, 199, 257, 373, 3, 3, 5 607, 701, 1021, 1279, 1709, 2203, 2281, 2617, 3217, 3539, 4093, 4099, 4253, 4423 , 5807, 8191, ... IS )

Observera att de två primtal för vilka den ursprungliga Mersenne-förmodan är falsk (67 och 257) uppfyller det första villkoret för den nya gissningen (67 = 2 ⁶ + 3, 257 = 2 ⁸ + 1), men inte de andra två. 89 och 107, som missades av Mersenne, uppfyller det andra villkoret men inte de andra två. Mersenne kan ha trott att 2 ^p − 1 bara är primtal om p = 2 ^k ± 1 eller p = 4 ^k ± 3 för något naturligt tal k , men om han trodde att det var " om och bara om " skulle han ha inkluderat 61.

Status för nya Mersenne-gissningar för de första 100 primtal
2	3	5	7	11	13	17	19	23	29
31	37	41	43	47	53	59	61	67	71
73	79	83	89	97	101	103	107	109	113
127	131	137	139	149	151	157	163	167	173
179	181	191	193	197	199	211	223	227	229
233	239	241	251	257	263	269	271	277	281
283	293	307	311	313	317	331	337	347	349
353	359	367	373	379	383	389	397	401	409
419	421	431	433	439	443	449	457	461	463
467	479	487	491	499	503	509	521	523	541

Röd: p har formen 2 ⁿ ±1 eller 4 ⁿ ±3	Cyan bakgrund: 2 ^p −1 är primtal	Kursiv stil: (2 ^p +1)/3 är primtal	Fet: p uppfyller minst ett villkor

Den nya Mersenne gissningen kan ses som ett försök att rädda den månghundraåriga Mersennes gissning, som är falsk. Men enligt Robert D. Silverman , höll John Selfridge med om att New Mersenne-förmodan är "uppenbarligen sann" eftersom den valdes för att passa de kända data och motexempel utöver dessa fall är ytterst osannolikt. Det kan ses mer som en nyfiken observation än som en öppen fråga som behöver bevisas .

Renaud Lifchitz har visat att NMC är sant för alla heltal mindre än eller lika med 32582656 genom att systematiskt testa alla primtal som det redan är känt att ett av villkoren gäller. Hans webbplats dokumenterar verifieringen av resultat upp till detta antal. En annan för närvarande mer uppdaterad statussida på NMC är The New Mersenne Prime-förmodan.

Lenstra–Pomerance–Wagstaff gissningar

Lenstra , Pomerance och Wagstaff har gissat att det finns oändligt många Mersenne-primtal och, mer exakt, att antalet Mersenne-primtal mindre än x approximeras asymptotiskt av

e^{\gamma }\cdot \log _{2}\log _{2}(x),

där γ är Euler-Mascheroni-konstanten . Med andra ord är antalet Mersenne-primtal med exponent p mindre än y asymptotiskt

e^{\gamma }\cdot \log _{2}(y).

Det betyder att det i genomsnitt bör finnas ungefär $e^{\gamma }\cdot \log _{2}(10)$ ≈ 5,92 primtal p av ett givet antal decimalsiffror så att $M_{p}$ är primtal. Gissningen är ganska korrekt för de första 40 Mersenne-primtalen, men mellan 2 ^{20 000 000} och 2 ^{85 000 000} finns det minst 12, snarare än det förväntade antalet som är runt 3,7.

Mer generellt är antalet primtal p ≤ y så att ${\frac {a^{p}-b^{p}}{ab}}$ är primtal (där a , b är coprime heltal, a > 1, − a < b < a , a och b är inte båda perfekta r -te potenser för något naturligt tal r > 1, och −4 ab är inte en perfekt fjärde potens) är asymptotiskt

(e^{\gamma }+m\cdot \log _{e}(2))\cdot \log _{a}(y).

där m är det största icke-negativa heltal så att a och − b båda är perfekta 2 ^m -te potenser. Fallet för Mersenne-primtal är ett fall av ( a , b ) = (2, 1).

Se även

Gillies gissning om fördelningen av antalet primtalsfaktorer för Mersenne-tal
Lucas–Lehmer primalitetstest
Lucas primitetstest
Katalanska Mersenne gissningar
Mersennes lagar

Bateman, PT ; Selfridge, JL ; Wagstaff Jr., Samuel S. (1989). "Den nya Mersenne-förmodan". American Mathematical Monthly . Mathematical Association of America. 96 (2): 125–128. doi : 10.2307/2323195 . JSTOR 2323195 . MR 0992073 .
Dickson, LE (1919). Talteorin Historia . Carnegie Institute of Washington. sid. 31. OL 6616242M . Omtryckt av Chelsea Publishing, New York, 1971, ISBN 0-8284-0086-5 .

externa länkar

Prime-ordlistan. Ny Mersenne prime gissning.