Lambek–Mosers sats

Lambek -Mosers sats är en matematisk beskrivning av uppdelningar av de naturliga talen i två komplementära uppsättningar . Det gäller till exempel för uppdelningen av tal i jämna och udda , eller i primtal och icke-primtal (ett och de sammansatta talen ). Lambek-Mosers sats består av två delar. Den ena delen anger att två icke-minskande heltalsfunktioner som är inversa, i en viss mening, kan användas för att dela upp de naturliga talen i två komplementära delmängder, och den andra delen anger att varje komplementär partition kan konstrueras på detta sätt. När en formel är känd för det ${\displaystyle n}:$ e naturliga talet i en mängd, kan Lambek–Moser-satsen användas för att få en formel för det ${\displaystyle n}:$ e talet som inte ingår i mängden.

Lambek–Moser-satsen tillhör den kombinatoriska talteorin . Den är uppkallad efter Joachim Lambek och Leo Moser , som publicerade den 1954, och bör särskiljas från en icke-relaterad teorem av Lambek och Moser, senare förstärkt av Wild, om antalet primitiva Pythagoras trippel . Den utökar Rayleighs sats, som beskriver komplementära par av Beatty-sekvenser , sekvenserna av avrundade multiplar av irrationella tal.

Från funktioner till partitioner

De fyra funktionerna $f$ , $f^{*}$ , $F$ och $F^{*}$ , för de två Beatty-sekvenserna 1, 3 , 4, 6, ... och 2, 5, 7, 10, ... . Dessa sekvenser avrundar heltalsmultiplarna av $\varphi$ och $\varphi +1$ , där $\varphi$ är det gyllene snittet .

Låt $f$ vara vilken funktion som helst från positiva heltal till icke-negativa heltal som båda är icke-minskande (varje värde i sekvensen $f (1),f(2),f(3),\dots$ är minst lika stor som något tidigare värde) och obegränsat (det ökar så småningom förbi ett fast värde). Sekvensen av dess värden kan hoppa över vissa siffror, så den kanske inte har en invers funktion med samma egenskaper. Definiera istället en icke-minskande och obegränsad heltalsfunktion $f^{*}$ som är så nära inversen som möjligt i den meningen att för alla positiva heltal n { $displaystyle n}$ ,

$$f{\bigl (}f^{*}(n){\bigr )}<n\leq f{\bigl (}f^{*}(n)+1{\bigr )}.$$

På motsvarande sätt kan $f^{*}(n)$ definieras som antalet värden $x$ för vilka $f(x)<n$ . Det följer av någon av dessa definitioner att $f^{*}{}^{*}=f$ . Om de två funktionerna $f$ och $f^{*}$ plottas som histogram , bildar de spegelbilder av varandra över diagonallinjen $x=y$ .

Från dessa två funktioner $f$ och $f^{*}$ , definiera ytterligare två funktioner $F$ och $F^{*}$ , från positiva heltal till positiva heltal, av

$${\begin{aligned}F(n)&=f(n)+n\\F^{ *}(n)&=f^{*}(n)+n\\\end{aligned}}$$

Sedan säger den första delen av Lambek–Mosers sats att varje positivt heltal förekommer exakt en gång bland värdena för antingen $F$ eller $F^{*}$ . Det vill säga att värdena som erhålls från $F$ och värdena som erhålls från $F^{*}$ bildar två komplementära uppsättningar av positiva heltal. Mer kraftfullt, var och en av dessa två funktioner mappar dess argument $n$ till den ${\displaystyle n}:$ e medlemmen av dess uppsättning i partitionen.

Som ett exempel på konstruktionen av en partition från en funktion, låt $f(n)=n^{2}$ , funktionen som kvadrerar dess argument. Då är dess invers kvadratrotsfunktionen , vars närmaste heltalsapproximation (i den mening som används för Lambek–Mosers sats) är $f^{*}(n)=\ lfloor {\sqrt {n-1}}\rfloor$ . Dessa två funktioner ger $F(n)=n^{2}+n$ och $F^{*}(n)=\lfloor {\sqrt {n-1}}\rfloor +n.$ För $n=1,2,3, \dots$ värdena för $F$ är proniska tal

2, 6, 12, 20, 30, 42, 56, 72, 90, 110, ...

medan värdena på $F^{*}$ är

1, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, ....

Dessa två sekvenser är komplementära: varje positivt heltal tillhör exakt en av dem. Lambek–Moser-satsen säger att detta fenomen inte är specifikt för proniska tal, utan snarare uppstår det för val av $f$ med lämpliga egenskaper.

Från partitioner till funktioner

De två funktionerna $f$ (blå pilar åt höger) och $f^{*}$ (röda pilar åt vänster) som härrör från uppdelningen av positiva heltal i primtal (2, 3, 5, 7, . ..) och icke-primtal (1, 4, 6, 8, ...). Visualisering baserad på en metod av Angel.

Den andra delen av Lambek–Mosers sats säger att denna konstruktion av partitioner från inversa funktioner är universell, i den meningen att den kan förklara vilken uppdelning av de positiva heltal som helst i två oändliga delar. Om $S=s_{1},s_{2},\dots$ och $S^{*}= s_{1}^{*},s_{2}^{*},\dots$ är två komplementära ökande sekvenser av heltal, man kan konstruera ett par funktioner $f$ och $f ^{*}$ från vilken denna partition kan härledas med Lambek–Mosers sats. För att göra det, definiera $f(n)=s_{n}-n$ och $f^{*}( n)=s_{n}^{*}-n$ .

Ett av de enklaste exemplen som detta skulle kunna tillämpas på är uppdelningen av positiva heltal i jämna och udda tal . Funktionerna $F(n)$ och $F^{*}(n)$ ska ge ${\displaystyle n}:$ e jämna respektive udda talet, så $F(n)=2n$ och $F^{*}(n)=2n-1$ . Från dessa härleds de två funktionerna $f(n)=F(n)-n=n$ och $f^{*}(n)=F^{*}(n)-n=n-1$ . De bildar ett inverst par, och partitionen som genereras via Lambek–Mosers sats från detta par är bara uppdelningen av de positiva heltalen i jämna och udda tal. En annan heltalspartition, i onda tal och odious tal (med pariteten för den binära representationen ) använder nästan samma funktioner, justerade av värdena för Thue–Morse-sekvensen .

Gränsformel

I samma arbete som de bevisade Lambek–Mosers sats, gav Lambek och Moser en metod för att gå direkt från ${\displaystyle F} ,$ funktionen som ger ${\displaystyle n}:$ e medlemmen av en uppsättning positiva heltal, till $F^{*}$ , funktionen som ger den ${\displaystyle n}:$ e icke-medlemmen, utan att gå igenom $f$ och $f^{*}$ . Låt $F^{\#}(n)$ beteckna antalet värden av $x$ för vilka $F(x)\leq n$ ; detta är en approximation av den inversa funktionen av $F$ , men (eftersom den använder $\leq$ istället för < $\displaystyle <}$ ) förskjuten med en från den typ av invers som används för att definiera $f^{*}$ från $f$ . Sedan, för alla $n$ , är $F^{*}(n)$ gränsen för sekvensen

$$n,n+F^{\#}(n),n+F^{\# }{\bigl (}n+F^{\#}(n){\bigr )},\dots ,$$

vilket betyder att denna sekvens så småningom blir konstant och värdet den tar när den gör det är $F^{*}(n)$ .

Lambek och Moser använde primtalen som exempel, efter tidigare arbeten av Viggo Brun och DH Lehmer . Om $\pi (n)$ är primtalsräknefunktionen (antalet primtal mindre än eller lika med $n$ ), då $n$ :te icke-primtal (1 eller ett sammansatt nummer ) ges av sekvensens gräns

$$n,n+\pi (n),n+\pi {\bigl (}n+\pi (n){\ större )},\dots$$

För vissa andra sekvenser av heltal konvergerar motsvarande gräns i ett fast antal steg, och en direkt formel för den komplementära sekvensen är möjlig. I synnerhet kan det ${\displaystyle n}:$ e positiva heltal som inte är en ${\displaystyle k}:$ te potens erhållas från den begränsande formeln som

$$n+\left\lfloor {\sqrt[{k}]{n+\lfloor {\sqrt[{k}]{n}}\rfloor }}\right\rfloor .$$

Historia och bevis

Satsen upptäcktes av Leo Moser och Joachim Lambek , som publicerade den 1954. Moser och Lambek citerar Samuel Beattys tidigare arbete om Beatty-sekvenser som inspiration, och citerar också Viggo Bruns och DH Lehmers arbete från tidigt 1930-tal metoder relaterade till deras begränsande formel för $F^{*}$ . Edsger W. Dijkstra har tillhandahållit ett visuellt bevis på resultatet, och senare ytterligare ett bevis baserat på algoritmiska resonemang. Yuval Ginosar har tillhandahållit ett intuitivt bevis baserat på en analogi av två idrottare som springer i motsatta riktningar runt en cirkulär racerbana.

Relaterade resultat

För icke-negativa heltal

En variant av satsen gäller för partitioner av de icke-negativa heltalen, snarare än för partitioner av de positiva heltalen. För denna variation motsvarar varje partition en Galois-koppling av de ordnade icke-negativa heltalen till sig själva. Detta är ett par icke-minskande funktioner $(f,f^{*})$ med egenskapen att för alla $x$ och $y$ , $f(x)\leq y$ om och endast om $x\leq f(y)$ . Motsvarande funktioner $F$ och $F^{*}$ definieras något mindre symmetriskt av $F(n)=f(n) +n$ och $F^{*}(n)=f^{*}(n)+n+1$ . För funktioner definierade på detta sätt bildar värdena för $F$ och $F^{*}$ (för icke-negativa argument, snarare än positiva argument) en partition av de icke-negativa heltalen, och varje partition kan konstrueras på detta sätt.

Rayleighs teorem

Huvudartikel: Beatty-sekvens

Rayleighs teorem säger att för två positiva irrationella tal $r$ och ${\displaystyle s} ,$ båda större än ett, med ${\tfrac {1}{r}}+ {\tfrac {1}{s}}=1$ , de två sekvenserna $\lfloor i\cdot r\rfloor$ och $\lfloor i\cdot s\ rfloor$ för ${\displaystyle i=1,2,3,\dots } ,$ erhållet genom att avrunda nedåt till ett heltal multiplerna av $r$ och $s$ , är komplementära. Det kan ses som en instans av Lambek–Mosers sats med $f(n)=\lfloor rn\rfloor -n$ och $f^{\ast }(n)=\lgolv sn\rgolv -n$ . Villkoret att $r$ och $s$ är större än ett innebär att dessa två funktioner är icke-minskande; de härledda funktionerna är $F(n)=\lfloor rn\rfloor$ och $F^{*}(n)=\lfloor sn\rfloor .$ Sekvenserna av värden för $F$ och $F^{*}$ som bildar den härledda partitionen är kända som Beatty sekvenser , efter Samuel Beattys återupptäckt 1926 av Rayleighs teorem.

Se även

• Hofstadter Figur-Figur-sekvenser , ett annat par av komplementära sekvenser som Lambek-Mosers sats kan tillämpas på

Anteckningar

•    Allouche, Jean-Paul; Dekking, F. Michel (2019), "Generaliserade Beatty-sekvenser och komplementära trippel", Moscow Journal of Combinatorics and Number Theory , 8 ( 4): 325–341, arXiv : 1809.03424 , doi : 10.2140/moscow.3259 .2059 . 4026541 , S2CID 119176190
•    Angel, Myer (1964), "De naturliga talens partitioner", Canadian Mathematical Bulletin , 7 (2): 219–236, doi : 10.4153/CMB-1964-020-1 , MR 0161826 , S2CID 129372999
•    Beatty, Samuel (1926), "Problem 3173", The American Mathematical Monthly , 33 (3): 159, doi : 10.2307/2300153 , JSTOR 2300153 ; Solutions av Beatty, A. Ostrowski, J. Hyslop och AC Aitken, vol. 34 (1927), s. 159–160, JSTOR 2298716
•   Brun, Viggo (1931), "Rechenregel zur Bildung der $n$ -ten Primzahl" [Beräkningsregler för att bygga ${\displaystyle n}:$ e primtal], Norsk Matematisk Tidsskrift (på norska), 13 : 73– 79, Zbl 0003.14902 , citerad av Lambek & Moser 1954
•   Chamberland, Marc (2017), "Beatty sequences" , Single Digits: In Praise of Small Numbers , Princeton University Press, s. 32–33, ISBN 978-0-691-17569-0
• Dijkstra, Edsger W. (1980), On a theorem by Lambek and Moser (PDF) , Rapport EWD753, University of Texas
•   Dijkstra, Edsger W. (1982), "Lambek and Moser revisited" , i Broy, Manfred; Schmidt, Gunther (red.), Theoretical Foundations of Programming Methodology: Lecture Notes of an International Summer School, regisserad av FL Bauer, EW Dijkstra och CAR Hoare, NATO Advanced Study Institutes Series, Series C – Mathematical and Physical Sciences, vol. 91, D. Reidel Publishing Co., s. 19–23, doi : 10.1007/978-94-009-7893-5_2 , Zbl 0533.40001
•    Dos Reis, AJ; Silberger, DM (1990), "Generating nonpowers by formula" , Mathematics Magazine , 63 (1): 53–55, doi : 10.1080/0025570X.1990.11977485 , JSTOR 26915103 , 429 388
•    Fraenkel, Aviezri S. (1977), "Complementary systems of integers", The American Mathematical Monthly , 84 (2): 114–115, doi : 10.2307/2319931 , JSTOR 2319931 , MR 0429815
• Garry, YKK (1997), "Omvända sekvenser och komplementära sekvenser" (PDF) , Mathematical Excalibur , 3 (4): 2
• Ginosar, Yuval (2014), "Om Lambek–Mosers teorem" , Heltal , 14 : A09:1–A09:4, arXiv : 1207.5633
•    Honsberger, Ross (1970), "Essay 12: Complementary sequences", Ingenuity in Mathematics , New Mathematical Library, vol. 23, New York: Random House, Inc., s. 93–110, ISBN 0-394-70923-3 , MR 3155264
•   Lambek, Joachim (1994), "Some Galois connections in elementary number theory", Journal of Number Theory , 47 (3): 371–377, doi : 10.1006/jnth.1994.1043 , MR 1278405
•   Lambek, Joachim ; Moser, Leo (augusti–september 1954), "Inversa och komplementära sekvenser av naturliga tal", The American Mathematical Monthly , 61 (7): 454–458, doi : 10.1080/00029890.1954.11988496 , JSTOR7 0807
•   Lehmer, DH (1932), "An inversive algorithm", Bulletin of the American Mathematical Society , 38 (10): 693–694, doi : 10.1090/S0002-9904-1932-05496-9 , MR 1562488
• John William Strutt, Baron Rayleigh (1894), The Theory of Sound , vol. 1 (andra upplagan), Macmillan, sid. 123
•     Roberts, Joe (1992), Lure of the Integers , MAA Spectrum, Washington, DC: Mathematical Association of America, sid. 11, doi : 10.2307/40148160 , ISBN 0-88385-502-X , JSTOR 40148160 , MR 1189138
•   Wild, Roy E. (1955), "Om antalet primitiva pytagoreiska trianglar med area mindre än n " , Pacific Journal of Mathematics , 5 : 85–91, doi : 10.2140/pjm.1955.5.85 , MR 0067912