Skolem–Mahler–Lech-satsen

I additiv och algebraisk talteori säger Skolem –Mahler–Lech-satsen att om en talföljd uppfyller en linjär differensekvation, bildar med finitely många undantag positionerna där sekvensen är noll ett regelbundet upprepande mönster. Detta resultat är uppkallat efter Thoralf Skolem (som bevisade satsen för sekvenser av rationella tal ), Kurt Mahler (som bevisade det för sekvenser av algebraiska tal ), och Christer Lech (som bevisade det för sekvenser vars element tillhör något fält av karakteristiska 0 ). Dess kända bevis använder p-adisk analys och är icke-konstruktiva .

Satspåstående

Låt $s(n)_{n\geq 0}$ vara en sekvens av komplexa tal som uppfyller $s(n)=c_{1}s(n-1)+c_{2}s(n-2)+\cdots +c_{d}s (nd)$ för alla $n\geq d$ , där $c_{i}$ är komplexa talkonstanter (dvs en konstant-rekursiv sekvens av ordningen $d$ ) . Då är mängden nollor $\{n\;\mid \;s(n)=0\}$ lika med unionen av en finit mängd och ändligt många aritmetiska progressioner .

Om vi ​​har $c_{d}\neq 0$ (exklusive sekvenser som 1, 0, 0, 0, ...), så är mängden nollor i själva verket lika med unionen av en finit mängd och ändligt många fullständiga aritmetiska progressioner, där en oändlig aritmetisk progression är full om det finns heltal a och b så att progressionen består av alla positiva heltal lika med b modulo a .

Exempel

Tänk på sekvensen

0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ...

som växlar mellan nollor och Fibonacci-talen . Denna sekvens kan genereras av den linjära upprepningsrelationen

$F(i)=F(i-2)+F(i-4)$

(en modifierad form av Fibonacci-recidiv), utgående från basfallen F (1) = F (2) = F (4) = 0 och F (3) = 1. För denna sekvens är F ( i ) = 0 om och bara om jag är antingen en eller jämn. Således kan positionerna där sekvensen är noll delas upp i en finit uppsättning (singletonmängden {1} ) och en fullständig aritmetisk progression (de positiva jämna talen ).

I det här exemplet behövdes endast en aritmetisk progression, men andra återkommande sekvenser kan ha nollor vid positioner som bildar flera aritmetiska progressioner.

Relaterade resultat

Skolem -problemet är problemet med att avgöra om en given återkommande sekvens har en nolla. Det finns en algoritm för att testa om det finns oändligt många nollor, och om så är fallet för att hitta sönderdelningen av dessa nollor till periodiska mängder som garanteras existerar av Skolem–Mahler–Lech-satsen. Det är dock okänt om det finns en algoritm för att avgöra om en återkommande sekvens har några icke-periodiska nollor ( Ouaknine & Worrell 2012) .

• Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akad. Skrifter , I (6) , citerad i Lech 1953.
• Mahler, K. (1935), "Eine arithmetische Eigenschaft der Taylor-Koeffizienten rationaler Funktionen", Akad. Wetensch. Amsterdam, Proc. , 38 : 50–60 , citerad i Lech 1953.
• Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik , 2 (5): 417–421, Bibcode : 1953ArM.....2..417L , doi : 10.1007/bf02590997 .
•   Mahler, K. (1956), "Om Taylor-koefficienterna för rationella funktioner", Proc. Cambridge Philos. Soc. , 52 (1): 39–48, Bibcode : 1956PCPS...52...39M , doi : 10.1017/s0305004100030966 , S2CID 124295518 .
•   Mahler, K. (1957), "Tillägg till artikeln "Om Taylor-koefficienterna för rationella funktioner", Proc . Cambridge Philos. Soc. , 53 (2): 544, Bibcode : 1957PCPS...53..544M , doi : 10.1017/s0305004100032552 , S2CID 251098312 .
•   Ouaknine, Joël; Worrell, James (2012), "Decision problems for linear recurrence sequences", Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, Frankrike, 17-19 september 2012, Proceedings , Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, s. 21–28, doi : 10.1007/978-3-642-33512-9_3 , MR 3040104 .

externa länkar

• Weisstein, Eric W. "Skolem-Mahler-Lech-satsen" . MathWorld .