Konjekti Sirakiz

Nan matematik, nou rele suit Sirakiz yon sekans nan antye natirèl yo ki defini nan fason sa a : nou kòmanse sòti nan yon nonm antye ki pi gran pase zewo; si li se yon nonm pè, nou divize li pa 2; si li enpè, nou miltipliye li pa 3 epi nou ajoute 1. Si nou repete operasyon an, nou jwenn yon sekans nan nonm antye pozitif yo, chak depann sèlman sou nonm ki vin anvan li.

Pa egzanp, si nou pran 14, nou ap bati sekans sa a : 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2 ... Se sa yo rele Suit Sirakiz nan chif 14.

Aprè nou fin jwenn chif 1, sekans valè yo (1,4,2,1,4,2 ...) repete endefiniman nan longè 3, se sa nou rele sik trivyal.

Si nou te kòmanse sòti nan yon lòt nonm antye, pandan nap aplike menm règ yo, nou ta jwenn yon sekans nonm diferan. A priori, li ta posib ke sekans Sirakiz la pa janm rive nan valè 1 si nou konsidere lòt valè inisyal, swa ke li mennen nan yon sik diferan de sik la trivyal, oswa ke li divèje vè lenfini. Men, yo pa janm jwenn egzanp yon sekans ki pa mennen nan 1, sètadi nan sik trivyal la.

Konjekti Sirakiz ki rele tou konjekti Collatz, konjekti Ulam , konjekti Tchèk oswa 3 x + 1 pwoblèm, se ipotèz matematik ki enonse ke sekans sa a ap rive nan 1 pou nenpòt ki antye positif.

Malgre senplisite li, li ap defye matematisyen yo depi plizyè ane. Paul Erdős te di sou konjekti Sirakiz la « syans matematik poko prè pou pwoblèm sa yo » .

Orijin

Depi 1928, Lothar Collatz te enterese ak iterasyon nonm antye yo, li te konn reprezante yo avèk graf ak ipègraf. Se nan kontèks sa a, li te envante pwoblèm nan 3x + 1 an, li te konn prezante li souvan nan seminè li yo. Nan lane 1952, pandan yon vizit nan vil Hambourg, Collatz eksplike Helmut Hasse pwoblèm nan. Helmut Hasse te difize li an Amerik nan Inivèsite Syracuse : suit Collatz la pran non "Suit Sirakiz". Pandan tan sa a, matematisyen polonè Stanislas Ulam gaye li nan laboratwa nasyonal Los Alamos la. Nan ane 1960 yo, pwoblèm nan te difize pa matematisyen Shizuo Kakutami nan inivèsite Yale ak Chikago.

Konjekti sa a mobilize anpil matematisyen pandan ane 1960 yo, pandan Gè Fwad la, te gen yon blag ki te fè konprann ke pwoblèm sa a te yon konplo Sovyetik yo te monte pou ralanti rechèch amerikèn.

Premye apwòch konjekti a

Suit Sirakiz la

Suit Sirakiz yon nonm antye N > 0 defini ak rekirans sa a :

$u_{0}=N$

epi pou tout antye natirèl n : $u_{n+1}={\begin{cases}{\dfrac {u_{n}}{2}}&{\mbox{si }}u_{n}{\mbox{ est pair,}}\\3u_{n}+1&{\mbox{si }}u_{n}{\mbox{ est impair.}}\end{cases}}$

Enonse konjekti a

Konjekti a endike ke pou tout N, gen yon endis n konsa Un = 1.

Suit Sirakiz pou N = 15

u 0	u 1	u 2	u 3	u 4	u 5	u 6	u 7	u 8	u 9	u 10	u 11	u 12	u 13	u 14	u 15	u 16	u 17	u 18	u 19	u 20
15	46	23	70	35	106	53	160	80	40	20	10	5	16	8	4	2	1	4	2	1	...

Reprezantasyon grafik sekans la pou N = 27.

Obsèvasyon grafik suit la pou N = 15 ak pou N = 27 montre ke suit la kapab pran gwo valè avanl li retounen nan ti valè yo. Grafik fè panse ak yon ti mòso grèl kap tonne san okenn direksyon detèmine oubyen trajektwa yon fèy kap tonbe, konsa nou vin ka pale Yo defini kondisyon sa yo :

• tan vòl la : li se pi piti endis n kote Un = 1. Valè li se 17 pou suit Sirakiz 15 epi 46 pou suit Sirakiz 127 ;
• tan vòl altitid : li se endis n ki pi piti n kote U n +1 < u 0 . Valè li se 10 pou suit Sirakiz 15 epi 23 pou suit Sirakiz 127.
• 1 suit Sirakiz cuse 15 et de 23 pour la suite de Syracuse 127 ;
• altitid maksimòm lan : sa a se valè maksimòm nan suit
• Valè li de 6suit Sirakiz racupie et de 4 7suit Sirakiz racuse 127.

Lòt fòmilasyon konjekti a

Nou ka bay anpil fòmil ekivalan pwoblèm Sirakiz la. Konjekti Sirakiz ekivalan ak pwopozisyon sa yo :

1. dire tout vòl limite;
2. dire nenpòt vòl limite nan altitid;
3. chak vòl gen yon kantite etap ki ka pran valè pè limite ;
4. chak vòl gen yon kantite etap enpè limite;
5. chak vòl gen yon kantite fini nan etap altitid ki pran valè enpè ;
6. chak vòl gen yon kantite limite nan etap enpè nan altitid.

Apwòch konjekti a ak rezilta yo

Suit konprese

Suit Sirakiz konprime, pou N = 15.

Suit Sirakiz konprime, pou N = 127.

Nou remake ke si Un enpè nan fòmil anlè a Un+1 se nesesèman yon nonm pè kidonk, valè kap vin aprè a ap yon divizyon pa de ; nous kapab defini yon lòt suit konprese si nou konbine de pati sa yo konsa :

$v_{n+1}={\begin{cases}{\frac {v_{n}}{2}}&{\mbox{si }}v_{n}{\mbox{ est pair}}\\{\frac {3v_{n}\,+\,1}{2}}&{\mbox{si }}v_{n}{\mbox{ est impair.}}\end{cases}}$

Nouvo suit sa se yon kontinyasyon nan vèsyon bazik la, epi konjekti a di ke rezilta sa a toujou fini ak seri siklik sa a : 1,2,1 ...

Suit Sirakiz konprese pou N = 15

v 0	v 1	v 2	v 3	v 4	v 5	v 6	v 7	v 8	v 9	v 10	v 11	v 12	v 13	v 14
15	23	35	53	80	40	20	10	5	8	4	2	1	2	1	...

Pye bwa sa a lye nimewo ki genyen vòl dire mwens pase 20 (klike sou elaji).

Nou ka kòmanse toi ak yon algoritm envès [réf.  nesesè] :

$R(n)={\begin{cases}\{2n\}&{\mbox{si }}n\equiv 0,1,2,3{\mbox{ ou }}5\\\{2n,(n-1)/3\}&{\mbox{si }}n\equiv 4\end{cases}}{\pmod {6}}.$

Olye pou nou pwouve ke sekans la dirèk, si nou kòmanse ak nenpòt nonm antye natirèl yo, nap toujou rive nan 1, nou eseye montre ke algoritm envès la, ki kòmanse nan 1, kapab nan jenere tout antye natirèl ki pa zewo.

Genyen [réf. nesesè] tou yon vèsyon konprese nan algoritm envès la :

$R(n)={\begin{cases}\{2n\}&{\text{si }}n\equiv 0{\mbox{ ou }}1\\\{2n,(2n-1)/3\}&{\text{si }}n\equiv 2\end{cases}}{\pmod {3}}.$

Algoritm envès sa yo ka reprezante ak pye bwa, ki gen rasin 1. Si konjekti a se verite, pyebwa sa yo kouvri tout antye natirèl ki pa zewo.

Apwòch binè

Si nou repete aplikasyon sa yo fonksyon Sirakiz la

a ka reprezante tankou yon machin abskap trete yon pwosesis binè . Machin lan pswivl fè twa etap sa yo sou nenpòt ki nimewo enpè jiskaske gen yon "1" ki rete:

1. Ajoute yon "1" nan fen (dwat) nan nimewo a nan binè (bay 2 n + 1);
2. Adisyone nonm orijinal la n (kap bay 2 n + 1 + n = 3 n + 1);
3. Retire tout "0" ki sou bò dwat la (ki se, divize pa de jiskaske rezilta a vin enpè).

Nimewo nou te kòmanse a se 7. Ekriti binè li se 111 (paske 7 = 2 ² + 2 ¹ + 2 ⁰ ) Sekans ki sòti a se sekans sa a:

 111
     1111
     1011 0
    10111
    10001 0
   100011
   1101 00
   11011
  101000
  1011
 1 0000
 11
1 00 

Apwòch pwobabilis

Gen diskisyon eristik ak estatistik pou motive konjekti a. Si nou konsidere, yon iterasyon sekans Sirakiz ki konprese a pou yon nonm v ke nou pran san okenn règ nan yon entèval ki ase gran, nap wè ke si v se yon nonm pè, li miltipliye pa (1/2), tandike yon nonm enpè ap miltipliye pa (3/2) apeprè. Nan de ka yo, nou verifye ke si rezilta a pè, sa endepandan de chwa v nou te fè a. Genyen yon rezonman eristik ki sipoze ke rezonman pwobabalis la valab pou nenpòt ki valè suit konprese a. Menm si rezonman sa manke egzaktitid (valè suit la ap pran yo pa aleyatwa), kèk obsèvasyon eksperimantal vle konfimel. Konsa, modèl nou jwenn lè nou aplike ipotèz sila a pèmèt nou konnen avèk presizyon dire vòl an altitid suit la. Avèk rezonman eristik sa a nou kapab di ke statistikman, efè ki soti nan de operasyon ki fèt youn dèyè lòt nan suit la se yon miltiplikasyon pa 3/4 oswa nou kapab di ke operasyon Sirakiz la kontrakte nonm nou te pati avèl la nan yon rapò ki vo apeprè rasin kare (3/4) = 0.866...

Rapò sa a ki pi piti lontan pase 1 sijere ke eleman siksesif yon sekans nan suit Sirakiz lapa ka grandi endefiniman. Pa gen okenn prèv solid pou deklarasyon sa a (e menm si yo ta fè agiman pwobabilis sa a vin rijid, li pa tap posib pou nou konkli). Epitou, agiman sila pa montre ke sekans trivyal yo pa egziste.

Konsènan distribisyon nonm ki verifye ipotèz Syracuse la, pa metòd pwogramasyon lineyè yo reyisi montre ke, pou yo x ase gran, kantite nonm antye ki pi ba pase x epi ki verifye ipotèz la se pou pi piti x ekspozan a, pou ton konstant a <1. An 2002, I. Krasikov ak J. Lagarias te jwenn a = 0.84.

Apwòch enfòmatik

Yon wout enteresan pou eksplorasyon suit la se etidye li sistematikman nan konpòtman li avèk òdinatè, pou nonm ki gwo anpil. Yo verifye konjekti a pou tout nonm ki pi piti pase N = 1,25×2⁶² . Gwosè nonm sa ki evalye a sis milya milya, ranfòse kwayans nan konjekti Sirakiz la. Poutan, nou dwe konprann ke menm si nou ta pouswiv kalkil sa yo, sa pap bay okenn demonstrasyon konjekti a; men li ka pèmèt nou jwenn yon kont-egzanp ki tap kapab demontre ke konjekti Sirakiz la genyen manti ladan li. Epitou apwòch sa kapab bay anpil rezilta nimerik ke teyorisyen ap kapab itilize pou reyalize demonstrasyon yo. Pa egzanp, si nou itilize nonm N ki mansyone anwo a avèk yon teyorèm [6] sou longè sik yo, nou kapab konkli ke pa ka genyen lòt sik ki pa sik trivyal la (1,4,2,1,...) ki genyen yon longè ki pi piti pase 17 milya[7].

Rezilta nimerik yo fè li posib pou chache korelasyon ant nonm N ak dire vòl la, oswa rekò altitid la. Li te obsève ke si rekò altitid la ta ka trè wo, dire a nan vòl la te an konparezon pi modès.

Yon obsèvasyon sou nonm ke yo deja etidye samble endike ke altitid maksimòman se majore pa φ(N)×N2, kote φ(N) ta ka swa yon konstant, oswa yon fonksyon lantman kwasant. Tan vòl a se pi iregilye men samble majore pa yon miltip logaritm N. Eksperyans nimerik sijere nouvo konjekti vo ke teyoris yo en ka atake.

Men rechèch teyorik la rete sèl chimen ki kapab pèmèt nou pòte presizyon sou egzistans yon seri trajektwa ki ta enfini : yo montre deja ke nonm ki tap nan trajektwa sa yo tap genyen yon dansite asenptotik ki vo zewo; pou rete nan lojik vòl la nou kapab di ke pou ti mòso lagrèl la pa tonbe atè li dwe genyen yon vitès ki gwo anpil. Si konjekti a se verite, yon vòl konsa pa ta dwe egziste.

Yon deklarasyon endesidab ?

Piske rezilta yo fèb anpil malgre anpil matematisyen briyan [Kiyès?] ki eseye travay sou konjekti sa epitou aplikasyon metòd matematik ki pisan kèk chèchè ap mande tèt yo kounya si konjekti Sirakiz la pa endesidab. Nan lane 1972, John Conway te tabli karaktè endesidab fas ak algoritm yo pou yon fanmi pwoblèm ki jeneralize pwoblèm nan (gade atik ki sou langaj pwogramasyon ekzotik Fractran). Rezilta sa a vle di ke genyen kèk pwoblèm nan fanmi niu konsidere a ki endesidab (an reyalite li ta menm posib, nan teyori sinon nan pratik, pou yo ta rive jwenn youn), men se pa rezoud anyen sou kesyon desidabilite nan pwoblèm Sirakiz la an pati.

Ekstansyon nan nonm reyèl ak nonm konplèks

10bit 10-5-8-4-2-1-2-1-2-1-... nan ekstansyon pou nonm reyèl konjekti Syracuse la (ladanl yo ranplase "3 n   +   1 "pa" (3 n   +   1) / 2 ")

Nou kapab wè pwoblèm Sirakiz la tankou restriksyon suit $z_{n+1}=f(z_{n})$ asou antye natirèl yo kote $f(z)$ se yon fonksyon reyèl oswa konplèks sila :

$f(z)={\frac {1}{2}}z\cos ^{2}\left({\frac {\pi }{2}}z\right)+(3z+1)\sin ^{2}\left({\frac {\pi }{2}}z\right).$

Oswa, nan vèsyon konprese a kote $3n+1$ an ranplase pa ${\frac {(3z+1)}{2}}$ :

$f(z)={\frac {1}{2}}z\cos ^{2}\left({\frac {\pi }{2}}z\right)+{\frac {(3z+1)}{2}}\sin ^{2}\left({\frac {\pi }{2}}z\right).$

fraktal nan vwazinaj liy reyèl la.

Nan seri chif reyèl yo, Marc Chamberland te etidye fonksyon an kote li montre konjekti a pa kenbe ak fonksyon sa a pou chif reyèl paske li genyen yon enfinite pwen fiks. Li te montre tou ke gen omwen yon lòt sik : 1,1925 - 2,1386 epitou ke genyen suit enfini ki divèje pou valè reyèl yo.

Nan plan konplèks la, se Letherman, Schleicher ak Wood ki te etidye fonksyon an Anpil pwen divèje nan infini, nan ilistrasyon anwo a yo reprezante an jòn oswa an ble. Fwontyè ant rejyon ki divèjesa yo ak sa ki pa divèjeyo, genyen koulè nwa, epi yo fòme yon koub fraktal. Ladan li nou jwenn eleman karakteristik nan ansanm Mandelbrot la.

Bibliyografi

• (angle) en Jeffrey Lagarias, The 3x +1 Problem: An Annotated Bibliography, II (2000-)
• Yon paj nan FAQ nan fr.sci.maths
• Jean-Paul Delahaye, "konjekti Sirakiz la", Pou Syans, n , me 1998 [PDF]
• (angle) en Sinyor, J., "T'he 3x+1 Problem asSting Rewriting System," International journal of Mathematics and Mathematical Sciences, Volim 2010 (2010), ID Atik 458563, 6 paj.
• Suit Sirakiz la yon mond ki chaje ak konjekti pa Luc-Olivier Pochon, Alain Favre, 2017 [PDF]

Gade tou

• Mwatye gwoup 3x + 1

Lyen deyò

• Pwoblèm lan nan twa pati sou sit Imaj nan matematik  : (I) elemantè men redoutab, (II) sik nan longè 5 ak (III) èske gen sik ki pa trivial?
• Kalkile suit Sirakiz sou calculis.net
• Fonksyon Sirakiz nan langaj LOGO
• BOINC Pwojè : Konjekti Collatz la