Abschätzung kgV

03.09.2009, 15:30

jester.

Abschätzung kgV

Hallo zusammen,

ich arbeite im Moment mit einem Kommilitonen an einem Vortrag zum AKS-Primzahltest, basierend auf dem Originalpaper von Agrawal, Kayal und Saxena. Dabei sind wir über das Lemma 3.1 gestolpert, das die Autoren als "simple fact" abtun. Allerdings tun wir uns mit dem Beweis jetzt doch etwas schwer.

Das Lemma (zu finden auf Seite 3) sagt aus: $\begin{eqnarray*} \operatorname{lcm}(m)\geq 2^{m},\quad m\geq 7 \end{eqnarray*}$ . Dabei steht $\begin{eqnarray*} \operatorname{lcm} \end{eqnarray*}$ für das kgV der ersten m natürlichen Zahlen.

Wir haben das kgV als Produkt aufgefasst: $\begin{eqnarray*} \operatorname{lcm}(m)=\prod_{\substack{p\in\mathbb{P} \\ p\leq m}}p^{c}=\prod_{p\in\mathbb{P}} p^{\lfloor \log_{p}(m)\rfloor} \end{eqnarray*}$ , wobei $\begin{eqnarray*} p^{c} \end{eqnarray*}$ für die vorkommenden Primzahlpotenzen steht und $\begin{eqnarray*} \mathbb{P} \end{eqnarray*}$ für die Menge aller Primzahlen.

Ein Versuch, das Lemma durch vollständige Induktion zu beweisen, ist fehlgeschlagen. Dann haben wir noch versucht, die Exponenten in dem o.g. Produkt zu betrachten, in der Form $\begin{eqnarray*} \sum_{\substack{p\in\mathbb{P}\\p\leq m}}\lfloor \log_{p}(m)\rfloor \end{eqnarray*}$ .

All diese Ausdrücke haben wir jedoch nicht entsprechend abschätzen können und daher sind wir nun auf der Suche nach einem Tipp, der uns auf den richtigen Weg bringt.

Das Paper, auf das die Autoren verweisen, habe ich im Internet nicht gefunden, so dass ich den dortigen Beweis auch nicht kenne.

03.09.2009, 15:52

Auf diesen Beitrag antworten »

Wenn du dich mit dem Thema befasst, wird dir auch die zweite Tschebyscheff-Funktion kein Fremdwort sein? Ich erwähne sie trotzdem, da sie einfach zu dieser Ungleichung dazugehört.

03.09.2009, 15:56

Duedi

Auf diesen Beitrag antworten »

Ist nur so ne Idee, aber angenommen, $\begin{eqnarray*} x_k := \operatorname{lcm}(k) \end{eqnarray*}$
Dann ist $\begin{eqnarray*} x_{k+1} \leq (k+1)\cdot x_k \end{eqnarray*}$ (wenn $\begin{eqnarray*} k+1 \end{eqnarray*}$ eine Primzahl ist, gilt das $\begin{eqnarray*} = \end{eqnarray*}$ , in manchen Fällen gilt aber auch $\begin{eqnarray*} x_{k+1}=x_k \end{eqnarray*}$ )
Die rekursive Form von $\begin{eqnarray*} 2^k \end{eqnarray*}$ sieht so aus: $\begin{eqnarray*} y_k := 2^k\ \Rightarrow y_{k+1}=2\cdot y_k \end{eqnarray*}$

Die Wachstumsgeschwindigkeit (ob man den Begriff der Ableitung bei solchen diskreten Werten benutzen darf, weiß ich nicht) ist also bei $\begin{eqnarray*} x_k \end{eqnarray*}$ größer als bei $\begin{eqnarray*} y_k \end{eqnarray*}$ (ab k=2). Jetzt musst du nur noch den Anfangswert $\begin{eqnarray*} k \geq 7 \end{eqnarray*}$ belegen.

EDIT: Ach Mist, es gilt ja $\begin{eqnarray*} x_{k+1} \leq (k+1)\cdot x_k \end{eqnarray*}$ (also kleiner gleich), das ist also nicht stichhaltig. Vielleicht hilft mein Ansatz ja doch irgendwie entfernt weiter. Ich bleib mal besser bei meinen Leisten Big Laugh

03.09.2009, 16:34

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von Arthur Dent
Wenn du dich mit dem Thema befasst, wird dir auch die zweite Tschebyscheff-Funktion kein Fremdwort sein? Ich erwähne sie trotzdem, da sie einfach zu dieser Ungleichung dazugehört.

Die Funktion haben wir gestern zufällig gefunden, nachdem wir auf das Lemma gestoßen sind. Soll heißen es sind quasi keine Kenntnisse über analytische Zahlentheorie oder solche Dinge vorhanden.

Eine grobe Idee, wohin das ganze gehen könnte, habe ich aber, wenn ich zwei Tatsachen aus dem Artikel ausnutze:

$\begin{eqnarray*} \operatorname{lcm}(n)=e^{\psi(n)}\sim e^{n} > 2^n \end{eqnarray*}$ - wobei $\begin{eqnarray*} \sim \end{eqnarray*}$ sich auf "Both functions are asymptotic to x, a statement equivalent to the prime number theorem." stützt.

Ist das, was ich geschrieben habe richtig und hilft uns das weiter, um das Lemma zu beweisen? Aus dem asymptotischen Verhalten kann ich ja noch nicht sicher schließen, dass $\begin{eqnarray*} \operatorname{lcm}(m)\geq 2^{m} \end{eqnarray*}$ , oder etwa doch?

03.09.2009, 17:28

Auf diesen Beitrag antworten »

Zitat:

Original von jester.
Aus dem asymptotischen Verhalten kann ich ja noch nicht sicher schließen, dass $\begin{eqnarray*} \operatorname{lcm}(m)\geq 2^{m} \end{eqnarray*}$ , oder etwa doch?

Du kannst daraus zumindest schließen, dass es ein $\begin{eqnarray*} m_0 \end{eqnarray*}$ gibt, so dass für alle $\begin{eqnarray*} m\geq m_0 \end{eqnarray*}$ die Ungleichung $\begin{eqnarray*} \operatorname{lcm}(m)\geq 2^{m} \end{eqnarray*}$ gilt.

03.09.2009, 17:53

Mystic

Auf diesen Beitrag antworten »

Zitat:

Original von jester.
Eine grobe Idee, wohin das ganze gehen könnte, habe ich aber, wenn ich zwei Tatsachen aus dem Artikel ausnutze:

$\begin{eqnarray*} \operatorname{lcm}(n)=e^{\psi(n)}\sim e^{n} > 2^n \end{eqnarray*}$ - wobei $\begin{eqnarray*} \sim \end{eqnarray*}$ sich auf "Both functions are asymptotic to x, a statement equivalent to the prime number theorem." stützt.

Ist das, was ich geschrieben habe richtig und hilft uns das weiter, um das Lemma zu beweisen? Aus dem asymptotischen Verhalten kann ich ja noch nicht sicher schließen, dass $\begin{eqnarray*} \operatorname{lcm}(m)\geq 2^{m} \end{eqnarray*}$ , oder etwa doch?

Hm, wäre wirklich

$\begin{eqnarray*} e^{\psi(x)}\sim e^x \end{eqnarray*}$

so könnte man durch Logarithmieren dann daraus schließen, dass sogar gilt

$\begin{eqnarray*} \psi(x) = x + o(1) \end{eqnarray*}$

was sicher nicht stimmt.

04.09.2009, 08:50

jester.

Auf diesen Beitrag antworten »

Zitat:

Original von Mystic
Hm, wäre wirklich

$\begin{eqnarray*} e^{\psi(x)}\sim e^x \end{eqnarray*}$

so könnte man durch Logarithmieren dann daraus schließen, dass sogar gilt

$\begin{eqnarray*} \psi(x) = x + o(1) \end{eqnarray*}$

was sicher nicht stimmt.

An welcher Stelle habe ich denn jetzt falsch gefolgert? Habe ich diese Aussage "Both functions are asymptotic to x, a statement equivalent to the prime number theorem." falsch interpretiert?

04.09.2009, 09:17

Auf diesen Beitrag antworten »

Wozu lange streiten, man braucht ja auch gar nicht $\begin{eqnarray*} \psi(x) = x + o(1) \end{eqnarray*}$ . Es genügt z.B. $\begin{eqnarray*} \psi(x) = x + o(x) \end{eqnarray*}$ , und das lässt sich aus (dem laut Wikipediabeitrag richtigen) $\begin{eqnarray*} \psi(x) = x + O\left( \frac{x}{\ln(x)} \right) \end{eqnarray*}$ schließen:

$\begin{eqnarray*} \psi(x) = x + o(x) \end{eqnarray*}$ bedeutet u.a., dass es für beliebige $\begin{eqnarray*} C<1 \end{eqnarray*}$ ein $\begin{eqnarray*} x_0 \end{eqnarray*}$ gibt, so dass $\begin{eqnarray*} \psi(x) \geq Cx \end{eqnarray*}$ für alle $\begin{eqnarray*} x\geq x_0 \end{eqnarray*}$ gilt. Also auch für $\begin{eqnarray*} C=\ln(2) \end{eqnarray*}$ .

Über den Zusammenhang $\begin{eqnarray*} \operatorname{lcm}(m) = e^{\psi(m)} \end{eqnarray*}$ folgt dann das gesuchte $\begin{eqnarray*} \operatorname{lcm}(m) \geq 2^m \end{eqnarray*}$ für hinreichend große $\begin{eqnarray*} m \end{eqnarray*}$ .

04.09.2009, 09:22

kiste

Auf diesen Beitrag antworten »

Hallo,

es gilt $\begin{eqnarray*} m{n \choose m} \mid \mathrm{lcm}(n) \end{eqnarray*}$ für alle $\begin{eqnarray*} 1 \leq m \leq n \end{eqnarray*}$ .
Damit gilt $\begin{eqnarray*} (2n+1){2n \choose n} = (n+1){2n+1 \choose n+1} \mid \mathrm{lcm}(2n+1) \end{eqnarray*}$ und $\begin{eqnarray*} n{2n\choose n} \mid \mathrm{lcm}(2n) \mid \mathrm{lcm}(2n+1) \end{eqnarray*}$ .

Insgesamt $\begin{eqnarray*} n(2n+1){2n \choose n} \mid \mathrm{lcm}(2n+1) \leq \mathrm{lcm}(2n+2) \end{eqnarray*}$ . Der Rest ist eine Abschätzung des Binomialkoeffizienten.

04.09.2009, 09:28

Auf diesen Beitrag antworten »

Zitat:

Original von kiste
es gilt $\begin{eqnarray*} m{n \choose m} \mid \mathrm{lcm}(n) \end{eqnarray*}$ für alle $\begin{eqnarray*} 1 \leq m \leq n \end{eqnarray*}$ .

Vielleicht habe ich eine Denkblockade, aber so unmittelbar einleuchtend ist mir diese Eigenschaft nicht. Kannst du mir mal auf die Sprünge helfen?

04.09.2009, 09:40

kiste

Auf diesen Beitrag antworten »

Nein das ist auch nicht einleuchtend Augenzwinkern

Dazu untersucht man das Integral $\begin{eqnarray*} I = \int_{0}^1 x^{m-1}(1-x)^{n-m} = \int_0^1 \sum_k (-1)^k {n-m\choose k}x^{m-1+k} = \sum_k (-1)^k {n-m\choose k} \frac{1}{m+k} \end{eqnarray*}$ .
Also $\begin{eqnarray*} I\mathrm{lcm}(n) \in \mathbb N \end{eqnarray*}$ da $\begin{eqnarray*} k \leq n-m \end{eqnarray*}$ also $\begin{eqnarray*} \frac{\mathrm{lcm}(n)}{m+k} \in \mathbb N \end{eqnarray*}$ .

Per Induktion(mit Hilfe von part. Integration) nach $\begin{eqnarray*} n-m \end{eqnarray*}$ zeigt man nun $\begin{eqnarray*} I = \frac{1}{m{n \choose m}} \end{eqnarray*}$

04.09.2009, 09:46

Auf diesen Beitrag antworten »

Nett.

Danke für den Beweis, da müsste man schon einen exzellenten Blick haben, um da selber drauf zu kommen. Freude

Wenn ich das richtig sehe, dann ist $\begin{eqnarray*} I \end{eqnarray*}$ ein spezieller Betafunktionswert.

04.09.2009, 16:24

jester.

Auf diesen Beitrag antworten »

Da unsere Vorkenntnisse sich auf Lineare Algebra I beschränken, befürchte ich, dass das alles ein bisschen zu hoch für uns ist. Ich hatte auf etwas elementareres gehofft. Big Laugh

Aber danke an alle beteiligten. Freude

04.09.2009, 17:16

Auf diesen Beitrag antworten »

Ich würde an deiner Stelle nicht so rasch verzweifeln. kiste hat eine hervorragend nachvollziehbare Beweisvariante vorgelegt - man kann das ganze im wesentlichen auf zwei Induktionsbeweise aufbauen:

(1) wie oben erwähnt: $\begin{eqnarray*} \int\limits_0^1 ~ x^{m-1}(1-x)^{n-m} ~ \dd x = \frac{1}{m\cdot \binom{n}{m}} \end{eqnarray*}$

und

(2) $\begin{eqnarray*} n(2n+1)\binom{2n}{n} \geq 2^{2n+2} \end{eqnarray*}$ für alle $\begin{eqnarray*} n\geq 3 \end{eqnarray*}$

Beide sind gut machbar: Beim ersten kistes Tipp mit der partiellen Integration befolgen, beim zweiten kommt man sofort klar, wenn man alles im Induktionsschritt mal aufschreibt. Wink

04.09.2009, 17:26

jester.

Auf diesen Beitrag antworten »

Ok, dann werde ich mich morgen vormittag damit befassen und mich noch mal melden.

Neue Frage »

Antworten »

Abschätzung kgV

Verwandte Themen