Möbius-funktion

I matematik , den Möbius funktionen generelt en særlig multiplikativ funktion , defineret på strengt positive heltal og med værdier i mængden {-1, 0, 1}. Det er involveret i Möbius-inversionsformlen .

Det bruges i forskellige grene af matematik. Set fra en elementær vinkel tillader Möbius-funktionen visse tælleberegninger , især til undersøgelse af p- grupper eller i grafteori . I aritmetik defineres det undertiden som det inverse af den konstante multiplikationsfunktion 1 til Dirichlet-konvolutionsoperationen . Det findes også til undersøgelse af cyklotomiske polynomer over området for rationelle tal . Dens rolle er analog for begrænsede felter, og derfor griber Möbius-funktionen ind i teorien om korrigerende koder . I analytisk talteori introduceres Möbius-funktionen oftere ved hjælp af Dirichlet-serien . Det griber ind i visse beviser knyttet til studiet af Riemann-hypotesen om primtal .

Brugen af denne funktion er gammel: vi finder den i Euler i 1748 eller endda i Gauss i hans Disquisitiones arithmeticae i 1801. Det var ikke desto mindre Möbius, der først studerede den systematisk i 1832.

Definition og egenskaber

Definition

I resten af artiklen betegner N sæt af naturlige tal og N * for strengt positive heltal. Den mest almindelige definition er:

Definition af Möbius-funktionen - Möbius- funktionen $μ$ er defineret fra N * i {–1, 0, 1}. Billedet μ ( n ) af et heltal n > 0 er lig med:

0 hvis n er delelig med en anden perfekt firkant end 1;
1 hvis n er produktet af et lige antal forskellige primtal;
–1 hvis n er produktet af et ulige antal forskellige primtal.

Tabellen over de første tyve værdier er derfor:

ikke	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20
μ ( n )	1	–1	–1	0	–1	1	–1	0	0	1	–1	0	–1	1	1	0	–1	0	–1	0

og grafen over de første halvtreds værdier er:

Ækvivalent definition

Karakterisering af Möbius-funktionen - Möbius- funktionen er den omvendte af den konstante funktion $1$ for Dirichlet-konvolution , det vil sige den unikke aritmetiske funktion $μ$ således, at for ethvert heltal $n > 0$ , sumværdierne af $μ$ på alle positive divisorer af $n$ er:

\ sum _ {{d | n}} \ mu (d) = \ left \ {{\ begin {matrix} 1 & {\ mbox {si}} n = 1 \\ 0 & {\ mbox {si}} n > 1. \ slut {matrix}} til højre.

Med denne anden definition er $μ$ automatisk , ligesom $1$ , multiplikativ , det vil sige at:

${\ displaystyle \ mu (1) = 1}$ og alle relativt prime , . ${\ displaystyle m, n \ in \ mathbb {N} ^ {*}}$ ${\ displaystyle \ mu (nm) = \ mu (n) \ mu (m)}$

Bevis for ækvivalensen af de to definitioner

Lad os vise, at funktionen $μ$ i den første definition opfylder godt

{\ displaystyle \ sum _ {d \ mid n} \ mu (d) = \ left \ {{\ begin {matrix} 1 & {\ mbox {si}} n = 1 \\ 0 & {\ mbox {si} } n> 1. \ slut {matrix}} til højre.}

Hvis n = 1, er resultatet indlysende. Hvis n > 1, skal P være sættet med primfaktorer for n og s = kort ( P ) (≥ 1). De eneste delere af n, hvis billede med μ ikke er nul, er dem uden en kvadratfaktor, dvs. produkterne fra forskellige elementer i P , idet antallet af P- dele med kardinal t er lig med binomialkoefficienten, så ved at anvende binomial formel :

{s \ vælg t}

{\ begin {align} \ sum _ {{d \ mid n}} \ mu (d) & = \ sum _ {{D \ subset P}} \ mu \ left (\ prod _ {{p \ in D} } p \ right) = \ sum _ {{D \ subset P}} (- 1) ^ {{{{\ rm {card}}} (D)}} \\ & = \ sum _ {{t = 0 }} ^ {s} (- 1) ^ {t} {{\ rm {card}}} (\ {D \ subset P \ mid {{\ rm {card}}} (D) = t \}) \ \ & = \ Sum _ {{t = 0}} ^ {s} {s \ vælg t} (- 1) ^ {t} = (- 1 + 1) ^ {s} = 0, \ slut { justeret}}

som afslutter demonstrationen.
I stedet for at anvende den binomiale formel, kunne vi desuden direkte bevise det i dette særlige tilfælde, det vil sige vise, at der i P er lige så mange dele af en jævn kardinal som en ulige kardinal. Til det er det tilstrækkeligt at rette et element p af P og gruppere delene af P to efter to efter par af formen ( S , S ∪ { p } ), hvor S er en del af P, der ikke indeholder p . Hver del af P vises i et par og kun en, og hvert par har en del af lige kardinal og en af ulige kardinal, hvilket tydeligt viser, at P har lige mange lige og ulige dele.

Möbius inversionsformel

Den anden definition giver os mulighed for hurtigt at demonstrere det for enhver aritmetisk funktion f :

Den aritmetiske funktion g defineret af

\ forall n \ i \ mathbb {N} ^ {*} \ quad g (n) = \ sum _ {{d \ mid n}} f (d)

afkrydset

{\ displaystyle \ forall n \ in \ mathbb {N} ^ {*} \ quad f (n) = \ sum _ {d \ mid n} \ mu \ left ({\ tfrac {n} {d}} \ right ) g (d)}

Kombinatorisk

Grundlæggende definitioner og egenskaber

En kombinatorisk tilgang gør det muligt at generalisere ovenstående undersøgelse. Teknikken består i at studere et endeligt og delvist ordnet sæt A, hvis rækkefølge er noteret ≤. Vi bruger følgende definition:

Definition af en kæde - Lad $a$ og $b være$ to elementer i $A$ således at $a \leq b$ . For ethvert naturligt tal p kalder vi en kæde med længden p, der forbinder $a$ til $b$ , enhver endelig sekvens $( x 0 , x 1 , ..., x p )$ sådan at:

{\ displaystyle a = x_ {0} <x_ {1} <\ cdots x_ {p-1} <x_ {p} = b}

I resten af afsnittet betegner vi med c p ( a , b ) antallet af kæder med længden p, der forbinder a til b . Vi har straks et par egenskaber. For eksempel, hvis a er et element i A , er c p ( a , a ) 1 for p = 0 og 0 for p > 0, og hvis b er et element af A, der er strengt større end a, så er c 0 ( a , b ) = 0 og c 1 ( a , b ) = 1. Mere generelt etablerer vi følgende lemma:

Lemma - Hvis $a$ og $b$ er to elementer i $A$ således at $a < b$ , for hvert naturlige tal $p$ ,

{\ displaystyle c_ {p + 1} (a, b) = \ sum _ {a \ leq c <b} c_ {p} (a, c) = \ sum _ {a <c \ leq b} c_ {p } (c, b)}

Faktisk er enhver kæde med længde p + 1, der forbinder $a$ til $b$ , sammensat af en kæde med længde p, der forbinder $a$ til $c$ og en kæde med længde 1, der forbinder $c$ til $b$ , hvilket viser den første lighed. Det andet vises på samme måde.

Gian-Carlo Rota definerer en ny Möbius-funktion , som han betegner μ A , og som vi vil se generaliserer μ :

Definition af G.-C. Rota for Möbius-funktionen μ A - Möbius-funktionen μ A med heltal er defineret på A × A ved:

{\ displaystyle \ forall a, b \ i A \ quad a \ leq b \ Rightarrow \ mu _ {A} (a, b) = \ sum _ {p \ in \ mathbb {N}} (- 1) ^ { p} c_ {p} (a, b) \ quad {\ text {and}} \ quad a \ not \ leq b \ Rightarrow \ mu _ {A} (a, b) = 0}

Med andre ord tæller vi positivt alle kæder med lige længder, der forbinder a til b og negativt med ulige længder. Vi bemærker endvidere, at disse definitioner forbliver gyldige, hvis A er uendelig, forudsat at der kun findes et begrænset antal elementer placeret mellem a og b (vi siger derefter, at rækkefølgen er lokalt endelig (in) ). Lemmaet gør det muligt at bevise følgende analog af karakteriseringen af μ:

Karakterisering af μ A - Lad $a$ og $b være$ to elementer i $A$ således at $a < b$ :

{\ displaystyle \ mu _ {A} (a, a) = 1 \ quad {\ text {and}} \ quad \ sum _ {a \ leq c \ leq b} \ mu _ {A} (a, c) = \ sum _ {a \ leq c \ leq b} \ mu _ {A} (c, b) = 0}

. Demonstration

Den første lighed kommer fra det faktum, at den unikke kæde, der forbinder $a$ til $a,$ er af længde 0. Den anden er en direkte konsekvens af det foregående forslag:

{\ displaystyle \ sum _ {a \ leq c \ leq b} \ mu _ {A} (a, c) = \ sum _ {a \ leq c \ leq b} \ sum _ {p \ in \ mathbb {N }} (- 1) ^ {p} c_ {p} (a, c) = \ sum _ {p \ in \ mathbb {N}} (- 1) ^ {p} \ sum _ {a \ leq c \ leq b} c_ {p} (a, c)}

Det foregående forslag viser, at:

{\ displaystyle \ sum _ {a \ leq c \ leq b} \ mu _ {A} (a, c) = \ sum _ {p \ in \ mathbb {N}} (- 1) ^ {p} {\ stor (} c_ {p + 1} (a, b) + c_ {p} (a, b) {\ big)} = c_ {0} (a, b) = 0}

Det sidste uafgjort vises på samme måde.

Dirichlet-konvolutionsproduktet generaliserer, hvilket gør det muligt at associeres med enhver lokalt endelig rækkefølge A, dets forekomst algebra (in) , og ovenstående resultat omformuleres derefter ved fortolkningen af μ A som en invers i denne ringenhed .

Dette resultat også at vise en inversion formel for μ A .

Forholdet mellem definitionen af Möbius og Rota

Her angiver sæt A det strengt positive heltal udstyret med rækkefølge: a ≤ b når a er en skillevægge af b .

Denne rækkefølge er lokalt endelig, og når vi anvender karakteriseringen af μ A på den med 1 som den første variabel, finder vi karakteriseringen μ.

Vi bemærker også, at hvis a deler b , tilknytter kortet, som til en streng ( x 1 , x 1 , ..., x p ) strengen (1, x 2 / x 1 , ..., x p / x 1 ) udgør en sammenhæng mellem sættet af kæder med længden p, der forbinder a til b, og dem, der forbinder 1 til b / a .

Vi udleder derfor:

Forholdet mellem definitionerne af Möbius-funktionerne - I to strengt positive heltal $a$ og $b$ således, at $a$ deler $b$ , er funktionen μ af Möbius, og at μ A af Rota er forbundet med:

{\ displaystyle \ mu _ {A} (a, b) = \ mu _ {A} \ left (1, {\ frac {b} {a}} \ right) = \ mu \ left ({\ frac {b } {a}} \ højre)}

Via dette link, kan den konventionelle inversion formlen for μ ses som et specielt tilfælde af, at der for μ A .

Dirichlet-serien

For alle komplekse tal s af reelle del strengt større end 1,

{\ displaystyle \ sum _ {n = 1} ^ {\ infty} {\ frac {\ mu (n)} {n ^ {s}}} = {\ frac {1} {\ zeta (s)}} \ quad {\ text {et}} \ quad \ sum _ {n = 1} ^ {\ infty} {\ frac {| \ mu (n) |} {n ^ {s}}} = \ sum _ {n = 1} ^ {\ infty} {\ frac {(\ mu (n)) ^ {2}} {n ^ {s}}} = {\ frac {\ zeta (s)} {\ zeta (2s)}} }

hvor er Riemann zeta-funktionen . $\ zeta$

Den Mertens funktionen er defineret ved . $M$ ${\ displaystyle M (n) = \ sum _ {k = 1} ^ {n} \ mu (k)}$

Den Primtalssætningen svarer til og til . En mere sofistikeret version af det Primtalssætningen (med en eksplicit vurdering af udtrykket rester) blev anvendt i 1899 af Edmund Landau demonstrere: . ${\ displaystyle \ sum _ {n = 1} ^ {\ infty} {\ frac {\ mu (n)} {n}} = 0}$ ${\ displaystyle \ lim _ {n \ to \ infty} {\ frac {M (n)} {n}} = 0}$ ${\ displaystyle \ sum _ {n = 1} ^ {\ infty} {\ frac {\ mu (n) \ ln n} {n}} = - 1}$

Noter og referencer

G. Villemin, ” Möbius-funktionen ” , på Numbers: kuriositeter - teori - anvendelse .
Françoise Badiou, “ Möbius inversion formula ”, Delange-Pisot-Poitou Seminar Theory of numbers , vol. 2, eksp. 1,1960, s. 2-3 ( læs online [PDF] ).
For endnu et bevis, se Badiou 1960 , s. 2-3 eller "Aritmetiske funktioner" i lektionen "Introduktion til talteori" på Wikiversity .
(en) G.-C. Rota, " På grundlaget for kombinatorisk teori, I: Teori om Möbius-funktioner ", Z. Wahrscheinlechlichkeitstheorie u. verw. Gebiete , vol. 2, 1963, s. 340-368.
IREM i Marseille , Kurser og aktiviteter i aritmetik til de afsluttende klasser ( læs online ) , s. 75.
IREM-Marseille , s. 76.
IREM-Marseille , s. 80.
Se f.eks. G. Tenenbaum , Introduktion til analytisk og probabilistisk talteori , [ detalje af udgaver ] , SMF , koll. “Specialiserede kurser”, Paris, 1995, I.3.6, eller (en) Tom M. Apostol , Introduktion til analytisk talteori , Springer ,1976, 340 s. ( ISBN 978-0-387-90163-3 , læs online ), th. 4.15 og 4.16.
(fra) E. Landau, Handbuch der Lehre von der Verteiligung der Primzahlen ,1909( læs online ) , s. 569.

Eksternt link

(da) Eric W. Weisstein , “ Möbius-funktion ” , på MathWorld