Landau-Symbol < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich beschäftige mich gerade mit Zahlentheorie und stolpere immer wieder über das Landau-Symbol O (großes O).
Aktuell hänge ich an dieser Stelle:
Sei [mm] \mu [/mm] die Möbius-Funktion
Ich betrachte nun für festes [mm] N\in\IN [/mm] :
[mm] \sum_{d\leq N}\mu(d) O(\frac{N}{d}) [/mm]
und ich möchte zeigen:
[mm] \sum_{d\leq N}\mu(d) O(\frac{N}{d}) [/mm] =O(N [mm] \log [/mm] N)
(ob bei dieser Umformung die Möbius-Funktion überhaupt eine Rolle spielt, kann ich nicht sagen)
Kann mir das jemand erklären?
Danke! 
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 01:52 Mo 21.11.2011 | | Autor: | felixf |
Moin!
> ich beschäftige mich gerade mit Zahlentheorie und stolpere
> immer wieder über das Landau-Symbol O (großes O).
>
> Aktuell hänge ich an dieser Stelle:
>
> Sei [mm]\mu[/mm] die Möbius-Funktion
>
> Ich betrachte nun für festes [mm]N\in\IN[/mm] :
>
> [mm]\sum_{d\leq N}\mu(d) O(\frac{N}{d})[/mm]
>
> und ich möchte zeigen:
>
> [mm]\sum_{d\leq N}\mu(d) O(\frac{N}{d})[/mm] =O(N [mm]\log[/mm] N)
>
> (ob bei dieser Umformung die Möbius-Funktion überhaupt
> eine Rolle spielt, kann ich nicht sagen)
In diesem Fall spielt die Moebiusfunktion keine Rolle, es reicht, dass [mm] $|\mu(d)| \le [/mm] C$ gilt fuer eine Konstante $C$ (die nicht von $d$ abhaengt).
Deswegen gilt [mm] $\sum_{d \le N} \mu(d) [/mm] O(N/d) = [mm] O(\sum_{d \le N} [/mm] N/d) = O(N [mm] \sum_{d \le N} [/mm] 1/d)$.
Nun ist [mm] $\sum_{d \le N} \frac{1}{d} \le [/mm] 1 + [mm] \int_1^N \frac{1}{t} \; [/mm] dt = 1 + [mm] [\log t]_1^N [/mm] = 1 + [mm] \log [/mm] N$. Damit gilt $O(N [mm] \sum_{d \le N} [/mm] 1/d) = O(N + N [mm] \log [/mm] N) = O(N [mm] \log [/mm] N)$.
LG Felix
|
|
|
| |
|
> Moin!
>
> > ich beschäftige mich gerade mit Zahlentheorie und stolpere
> > immer wieder über das Landau-Symbol O (großes O).
> >
> > Aktuell hänge ich an dieser Stelle:
> >
> > Sei [mm]\mu[/mm] die Möbius-Funktion
> >
> > Ich betrachte nun für festes [mm]N\in\IN[/mm] :
> >
> > [mm]\sum_{d\leq N}\mu(d) O(\frac{N}{d})[/mm]
> >
> > und ich möchte zeigen:
> >
> > [mm]\sum_{d\leq N}\mu(d) O(\frac{N}{d})[/mm] =O(N [mm]\log[/mm] N)
> >
> > (ob bei dieser Umformung die Möbius-Funktion überhaupt
> > eine Rolle spielt, kann ich nicht sagen)
>
> In diesem Fall spielt die Moebiusfunktion keine Rolle, es
> reicht, dass [mm]|\mu(d)| \le C[/mm] gilt fuer eine Konstante [mm]C[/mm] (die
> nicht von [mm]d[/mm] abhaengt).
>
> Deswegen gilt [mm]\sum_{d \le N} \mu(d) O(N/d) = O(\sum_{d \le N} N/d) = O(N \sum_{d \le N} 1/d)[/mm].
>
Danke für deine Antwort! Und eigentlich habe ich es jetzt auch verstanden. Bloß an dieser Stelle habe ich aber noch mal eine Frage:
> Nun ist [mm]\sum_{d \le N} \frac{1}{d} \le 1 + \int_1^N \frac{1}{t} \; dt = 1 + [\log t]_1^N = 1 + \log N[/mm].
> Damit gilt [mm]O(N \sum_{d \le N} 1/d) = O(N + N \log N) = O(N \log N)[/mm].
Beim ersten Schritt schätzt du die Reihe ja mithilfe von dem Integral ab. Was genau verwendest du denn da? Warum darfst du das in der Form machen? (gibt es da evtl. eine allgemeine Formel?)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:52 Mo 21.11.2011 | | Autor: | felixf |
Moin!
> Danke für deine Antwort! Und eigentlich habe ich es jetzt
> auch verstanden. Bloß an dieser Stelle habe ich aber noch
> mal eine Frage:
>
> > Nun ist [mm]\sum_{d \le N} \frac{1}{d} \le 1 + \int_1^N \frac{1}{t} \; dt = 1 + [\log t]_1^N = 1 + \log N[/mm].
> > Damit gilt [mm]O(N \sum_{d \le N} 1/d) = O(N + N \log N) = O(N \log N)[/mm].
>
> Beim ersten Schritt schätzt du die Reihe ja mithilfe von
> dem Integral ab. Was genau verwendest du denn da?
Dieselbe Technik, die auch beim ![[]](/images/popup.gif) Integralkriterium verwendet wird. Es gilt [mm] $\int_1^N \frac{1}{t} \; [/mm] dt [mm] \le \sum_{d=1}^N \frac{1}{d} \le [/mm] 1 + [mm] \int_1^N \frac{1}{t} \; [/mm] dt$.
> Warum
> darfst du das in der Form machen? (gibt es da evtl. eine
> allgemeine Formel?)
Warum nicht? Ich muss irgendwie [mm] $\sum_{d=1}^N \frac{1}{d}$ [/mm] nach oben Abschaetzen. Ich kann natuerlich auch [mm] $\sum_{d=1}^N \frac{1}{d} \le \sum_{d=1}^N [/mm] 1 = N$ machen, aber dann bekomm ich nicht $O(N [mm] \log [/mm] N)$ heraus, sondern [mm] $O(N^2)$.
[/mm]
Die obige Abschaetzung [mm] $\log [/mm] N [mm] \le \sum_{d=1}^N \frac{1}{d} \le [/mm] 1 + [mm] \log [/mm] N$ zeigt uebrigens, dass $O(N [mm] \log [/mm] N)$ optimal ist, solange du [mm] $\mu(d)$ [/mm] einfach durch eine Konstante beschraenkst.
(Ich vermute stark, dass es trotzdem optimal ist, aber das ist dann wohl etwas aufwaendiger zu zeigen...)
LG Felix
|
|
|
|
