Lineare diophantische Gleichung

Neue Frage »

05.07.2007, 21:56	akechi90	Auf diesen Beitrag antworten »
Lineare diophantische Gleichung Ich stehe vor einer recht schwierigen Übungsaufgabe, in der ich Hilfe benötige: Seien $\begin{eqnarray} a_{1}, a_{2},... a_{n} \in \mathbb Z \end{eqnarray}$ , dann gibt es eine Konstante C(n) derart, dass jede lineare Gleichung der Form $\begin{eqnarray} (a_{1},a_{2},...,{a_n}) \begin{pmatrix} x_1 \\ x_2 \\ ... \\ x_n \end{pmatrix} = 0 \end{eqnarray}$ stets eine Lösung $\begin{eqnarray} x \in \mathbb Z^{n} \end{eqnarray}$ mit $\begin{eqnarray} x \neq 0 \end{eqnarray}$ besitzt, die die Relation $\begin{eqnarray} \mid x \mid \leq C(n)(max\{\mid a_1\mid , \mid a_2 \mid ,..., \mid a_n \mid \})^{\frac{1}{n-1}} \end{eqnarray}$ erfüllt. Mein bisheriger Fortschritt war, dass ich erkannt habe, dass es sich bei der Lösungsmenge um ein n-1-dimensionales Gitter im $\begin{eqnarray} \mathbb R^{n} \end{eqnarray}$ handelt. Das impliziert schon, dass die Lösung per Minkowski-Gitterpunktsatz zu führen ist (den kann ich in der Übungsaufgabe auch in einer stark abgeschwächten Form beweisen, die genügen würde). Nur gibt es ein Problem: Das Gitter liegt im n-Dimensionalen Raum und lässt sich somit nicht mit Minkowski analysieren. Ich benötige also eine Abbildung in den n-1-dimensionalen Raum, die die Metrik innerhalb der Gitterstruktur erhält (sprich - eine Drehung, die das Gitter in eine kanonische Einbettung des $\begin{eqnarray} \mathbb R^{n-1} \end{eqnarray}$ in den $\begin{eqnarray} \mathbb R^{n} \end{eqnarray}$ reindreht). Nur gibt es zwei Probleme - ich befürchte, dass eine ganzzahlig gewählte Gitterbasis keine vollständige Gitterbasis sein könnte, dass ich also zu große Werte für die Gitterdeterminante erhalte; ebenso finde ich keine Drehung, die mir das Gitter generell richtig "hindreht". Unser Dozent gab uns den Tipp, um die Aufgabe zu lösen, müsste man "etwas zählen". Soweit ich das richtig verstanden habe, müsste das der Ansatz mit der abgeschwächten Form von Minkowski sein. Hat hier jemand Erfahrungen mit dieser Aufgabe? Danke schon mal im Voraus. Carsten
05.07.2007, 22:15	AD	Auf diesen Beitrag antworten »
Da ist einiges sehr merkwürdig in deiner Problembeschreibung: 1.Du sprichst sicher nur über nichttriviale $\begin{eqnarray} x \end{eqnarray}$ , d.h., vom Nullvektor verschiedene. Ansonsten würde eben jener Nullvektor die Behauptung beweisen. 2.Wenn du schon beliebige ganze Zahlen $\begin{eqnarray} a_k \end{eqnarray}$ zulässt, dann kommt doch eher sowas wie $\begin{eqnarray} \max\{\|a_1\|, \ldots, \|a_n\|\} \end{eqnarray}$ in die Behauptung, oder? 3.Über welche Norm $\begin{eqnarray} \|x\| \end{eqnarray}$ sprichst du? Die euklidische?
05.07.2007, 22:18	akechi90	Auf diesen Beitrag antworten »
Exakt, es ist eine nicht-triviale Lösung des Problems gesucht. Die Betragszeichen habe ich schlicht vergessen. Die Norm ist die euklidische, ja. Aber ich habe schon festgestellt, dass sich das Problem auch mit der Maximumsnorm oder einer beliebigen p-Norm lösen lässt, da diese schließlich äquivalent sind. Allerdings scheint die euklidische besonders auf einen geometrischen Ansatz anzuspielen, der hier auch am ehesten zu greifen scheint. Dass das Problem einen geometrischen Lösungsansatz benötigt, scheint mir klar. Wie ich den Ansatz allerdings angreifbar mache, weiß ich eben noch nicht.
05.07.2007, 22:29	AD	Auf diesen Beitrag antworten »
Ich halte die Behauptung für falsch - Gegenbeispiel: Sei $\begin{eqnarray} m>1 \end{eqnarray}$ ganzzahlig, und wir betrachten: $\begin{eqnarray} a_1=m, \; a_2=m-1, \; a_3=a_4=\ldots=a_n=0 \end{eqnarray}$ Die "kleinste" nichttriviale Lösung ist $\begin{eqnarray} x_1=m-1,x_2=-m \end{eqnarray}$ , der Rest der $\begin{eqnarray} x_k \end{eqnarray}$ beliebig. Damit ist für alle nichtitrivialenLösungen $\begin{eqnarray} x \end{eqnarray}$ die Abschätzung $\begin{eqnarray} \|x\| \geq \sqrt{(m-1)^2+m^2} \geq m \end{eqnarray}$ , erfüllt. Andererseits ist aber $\begin{eqnarray} (\max\{\|a_1\|,\ldots,\|a_n\|\})^{\frac{1}{n-1}} = m^{\frac{1}{n-1}} \end{eqnarray}$ . Und nun lassen wir für festes $\begin{eqnarray} n \end{eqnarray}$ mal $\begin{eqnarray} m\to\infty \end{eqnarray}$ gehen und sehen, dass es kein solches $\begin{eqnarray} C(n) \end{eqnarray}$ mit $\begin{eqnarray} m \leq \|x\| \leq C(n) m^{\frac{1}{n-1}} \end{eqnarray}$ für $\begin{eqnarray} m\to\infty \end{eqnarray}$ gibt, zumindest nicht für $\begin{eqnarray} n>2 \end{eqnarray}$ .
05.07.2007, 22:32	akechi90	Auf diesen Beitrag antworten »
Dann setz mal deine Koeffizienten vor die Null, die Idee hatte ich auch schon Gib einfach bei einer Null als Lösung eine 1 vor dem Null-Koeffizienten an, das ist schon nicht-trivial. Trivial ist x = 0. EDIT: Nicht genau erklärt, was ich sagen wollte: Nicht-trivial ist in deinem Beispiel schon die Lösung mit $\begin{eqnarray} x_n = 1 \end{eqnarray}$ , wobei der Rest 0 ist.
05.07.2007, 22:35	AD	Auf diesen Beitrag antworten »
Ach Ok, hab ich übersehen. Na viel Spaß noch - wozu brauch man das Zeug eigentlich?
Anzeige

05.07.2007, 22:36	akechi90	Auf diesen Beitrag antworten »
An dem Gegenbeispiel ist nicht in Ordnung, dass ich den Begriff Nicht-Trivial nicht richtig geschildert habe. Das Gegenbeispiel besitzt die Lösung $\begin{eqnarray} x_1,x_2,...,x_{n-1} = 0; x_n =1 \end{eqnarray}$ , und die erfüllt die Bedingungen. Ich dachte auch zuerst, so ein Gegenbeispiel gefunden zu haben, habe aber erst dann die Forderung "nicht-trivial" verstanden.
05.07.2007, 22:39	akechi90	Auf diesen Beitrag antworten »
Das ist eine unserer Übungsaufgaben (bzw. die allerletze Übungsaufgabe) aus LinAlg I. Ich möchte diese Aufgabe lösen, ich brauche ja lediglich kleine Tipps. Was der Nutzen ist - keine Ahnung. Aber ich interessiere mich ja sehr für Zahlentheorie, und endlich mal eine höhere Zahlentheorie-Aufgabe zumindest in den Ansätzen zu lösen würde mich halt schon reizen.
03.08.2007, 01:21	akechi90	Auf diesen Beitrag antworten »
Habe inzwischen einen Beweis gefunden, Minkowski war doch ein allzu großes Geschütz. Man betrachtet einfach, wie groß das Bild eines diskreten Würfels im $\begin{eqnarray} \mathbb Z ^n \end{eqnarray}$ unter der gegebenen linearen Abbildung ist. Sobald sie nicht mehr injektiv ist, gibt es zwei Lösungen derselben inhomogenen Gleichung, und die Abschätzung kriegt man leicht mit dem Schubfachprinzip hin. Die Differenz der Lösungen ist eine Lösung der homogenen Gleichung, welche auch im diskreten Würfel liegen muss. Trotzdem danke für den Hilfeversuch

Neue Frage »

Antworten »

Lineare diophantische Gleichung

Verwandte Themen