Naar inhoud springen

Markovgetal

Uit Wikipedia, de vrije encyclopedie
De eerste niveaus van de markovgetallenboom

Een markovgetal is elk van de positieve gehele getallen en die deel uitmaken van een oplossing van de diofantische vergelijking:

Frobenius noemde deze getallen in 1913 de getallen van Markoff en de diofantische vergelijking de vergelijking van Markoff.[1] Ze zijn genoemd naar Andrej Markov. De vergelijking kwam voor in de theorie van binaire kwadratische vormen, die door Markov werd bestudeerd (Markov publiceerde in het Frans en gebruikte de Franse transcriptie van zijn naam, Markoff).[2][3] De getallen komen ook voor in de diofantische benadering van reële getallen door rationale getallen.

De oplossingen van de vergelijking zijn tripels . De variabelen en mogen gepermuteerd worden want de vergelijking is symmetrisch in en . Oplossingen worden bij conventie in de genormaliseerde vorm geschreven waarbij . De vergelijking heeft de triviale oplossingen (1,1,1) en (2,1,1); (1,2,1) en (1,1,2) beschouwt men als dezelfde oplossing. Andere oplossingen kunnen hieruit afgeleid worden. Als een oplossing is, dan is ook een oplossing; dit volgt uit het feit dat de vergelijking kwadratisch is in en . Uit (2,1,1) kan men zo afleiden dat (2,1,5) of (1,2,5) ook een oplossing is; uit (5,1,2) dat (5,1,13) of (1,5,13) een oplossing is, enzovoort.

Er zijn oneindig vele oplossingen, en oneindig vele markovgetallen. De eerste markovgetallen zijn:

1, 2, 5, 13, 29, 34, 89, 169, 194, 233, 433, 610, 985, 1325, ...[4]

De oplossingen van de vergelijking kan men in een binaire boom voorstellen. Elke oplossing is daarbij de "ouder" van twee verschillende oplossingen die volgens het hierboven beschreven mechanisme eruit zijn afgeleid (met of zonder permutatie).

De boom wordt soms in vereenvoudigde vorm weergegeven, met enkel de -waarden.

Vermoeden van Markov

[bewerken | brontekst bewerken]

In deze boom blijken sommige waarden van en meerdere malen voor te komen, maar de waarden van : 1, 2, 5, 13, 29, 34, 169, 194, 433, ... zijn kennelijk uniek. Het is een openstaand probleem of alle waarden van uniek zijn. Er zijn alvast geen tegenvoorbeelden van het vermoeden gevonden in de eerste 1046858 markovtripels.[4]

Het uniciteitsvermoeden of vermoeden van Markov, voor het eerst geformuleerd door Frobenius in 1913[1], zegt dat , als grootste lid van een markovtripel, op unieke wijze de twee andere leden bepaalt. Dit wil zeggen: kan niet het grootste getal zijn van twee verschillende tripels en , die allebei een oplossing zijn van de markov-vergelijking.

D. Rosen en G.S. Patterson vonden in 1970-71 dat het vermoeden klopt voor alle markovgetallen tot 30 cijfers lang (893 getallen in totaal).[5] Het vermoeden is bewezen voor bepaalde klassen van getallen,[6] bijvoorbeeld als een macht is van een priemgetal.[7] Een algemeen aanvaard, algemeen geldend bewijs is echter nog niet gevonden, maar Norbert Riedel voert in een artikel uit 2012 (later meermaals aangepast) wel een bewijs aan.[8] Een eerder voorgesteld bewijs van Riedel uit 2007 bleek niet helemaal correct.[9][10]

Men kan het vermoeden illustreren aan de hand van de vereenvoudigde markovboom met enkel -waarden. Voor een gegeven -waarde kan men de - en -waarden van het markovtripel vinden door te bedenken dat of gelijk is aan de -waarde van de "ouder" in de boom; en de ontbrekende waarde is dan de oplossing van een vierkantsvergelijking; bijvoorbeeld: voor is en is de oplossing van de vierkantsvergelijking , die kleiner is dan 169; dit is 2. Als het vermoeden onwaar zou zijn, betekent dit dat er een markovtripel bestaat dat langs meer dan een pad door de markovboom kan bereikt worden; de markovboom zou dan geen binaire boom blijken.

Andere eigenschappen

[bewerken | brontekst bewerken]
  • Afgezien van de singuliere oplossingen (1,1,1) en (1,1,2) bestaat elk markovtripel uit drie verschillende getallen, die twee aan twee onderling ondeelbaar zijn.
  • De pellgetallen met oneven index: 1, 5, 29, 169, 985,... zijn markovgetallen. Het zijn de -waarden van de tripels aan de linkerzijde van de boom (de onderzijde in de gekantelde figuur hiernaast). De verhouding van twee opeenvolgende getallen in deze rij convergeert naar
  • De fibonaccigetallen met oneven index: 1, 2, 5, 13, 34, 89, 233,... zijn markovgetallen. Het zijn de -waarden van de tripels aan de rechterkant van de boom (de bovenzijde in de figuur hiernaast). De verhouding van twee opeenvolgende getallen in deze rij convergeert naar
  • Elk oneven markovgetal is van de vorm , een viervoud plus 1.
  • Elk even markovgetal is van de vorm een achtvoud plus 2.