Mathematik
Refine
Year of publication
Document Type
- Article (112)
- Doctoral Thesis (76)
- Preprint (48)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (377)
Is part of the Bibliography
- no (377)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
Institute
- Mathematik (377)
- Informatik (56)
- Präsidium (22)
- Physik (6)
- Psychologie (6)
- Geschichtswissenschaften (5)
- Sportwissenschaften (5)
- Biochemie und Chemie (3)
- Biowissenschaften (3)
- Geographie (3)
Kieferorthopäden beschreiben die Anordnung der Zähne und die Stellung der Kiefer üblicherweise mittels Winkel und Strecken in der sagittalen Gesichtsebene. Im vorliegenden Fall werden fünf Winkel betrachtet und jedes Individuum lässt sich als Punkt in einem 5-dimensionalen Raum darstellen. Individuen, die laut Experten ein gut funktionierendes Gebiss und ein harmonisches Äußeres besitzen, formen eine Punktwolke, die im Folgenden als die Norm Population bezeichnet wird. Individuen fern von der Wolke benötigen kieferorthopädische Behandlung. Welche Form sollte dieser Eingriff annehmen? Durch Hilfsmittel der modernen Kieferorthopädie lassen sich die beschriebenen Winkel nahezu nach Belieben ändern. Dies ist natürlich verbunden mit einer unterschiedlichen Menge an Problemen, Arbeitsaufwand und Unannehmlichkeiten, abhängig vom individuellen Patienten. Diese Arbeit präsentiert eine Methode, die auf jedem Computer leicht implementierbar und auf k Variablen verallgemeinerbar ist. Sie ermöglicht Kieferorthopäden eine Visualisierung, wie verschiedene denkbare Anpassungen der Winkel eines Patienten dessen relative Position zur Norm Population verändern. Damit unterstützt sie Kieferorthopäden bei der Entscheidung für einen Behandlungsplan, der die besten Ergebnisse verspricht.
Ein universeller zentraler Grenzwertsatz für den Abstand zweier Kugeln in zufälligen Splitbäumen
(2008)
In der vorliegenden Arbeit wird ein Modell des zufälligen Splitbaumes untersucht. Dies ist ein verallgemeinertes Modell, das bei passender Wahl der zugehörigenParameter viele konkrete Suchbäume umfasst. Das Modell ist in der Arbeit von L. Devroye beschrieben: Nach einem zufallsbasierten Algorithmus werden den Knoten des Baumes Daten in Form von Kugeln hinzugefügt. Tiefe und Höhe sind dabei grundlegende Größen, die die Komplexität von Suchoperationen beschreiben, wenn das Suchbaummodell als Datenstruktur verwendet wird. Das Augenmerk der Arbeit richtet sich auf eine weitere entscheidende Größe: Den Abstand zweier rein zufällig gewählter Kugeln im Baum. Aufbauend auf Devroyes Erkenntnissen zum asymptotischen Verhalten der Tiefe der zuletzt eingefügten Kugel im Splitbaum, wird ein neues Resultat erzielt: Ein universeller Zentraler Grenzwertsatz für den Abstand der Kugeln. Als Anwendungsbeispiel werden zwei vom allgemeinen Modell abgedeckte Suchbäume betrachtet und der jeweilige Grenzwertsatz für die Abstände aus dem universellen Satz abgeleitet.
Das Assignment Problem ist ein bekanntes kombinatorisches Optimierungsproblem, bei dem es darum geht, in einem gewichteten bipartiten Graphen ein Matching mit minimalem Gewicht zu finden. In dieser Arbeit sind die Kantengewichte exponentialverteilt zu speziell gewählten Raten. Damit sind Erwartungswert und Varianz des minimalen Gewichts von besonderem Interesse. Zunächst wird ein Beweis der Parisi Formel und der Coppersmith-Sorkin Formel erläutert. Die Formeln beschreiben den Erwartungswert des minimalen Gewichts im Fall, dass die Raten alle dem Wert 1 entsprechen. Im zweiten Teil wird die Herleitung einer expliziten Formel zur Berechnung der Varianz des zufälligen minimalen Gewichts erklärt, wobei die Raten immer noch mit 1 übereinstimmen. Gleichzeitig wird eine Formel für die höheren Momente geliefert, aus der die Parisi Formel und Coppersmith-Sorkin Formel aus dem ersten Teil folgen und die sogar das bisherige Modell bezüglich der Parameter erweitert. Schließlich kann man das Ergebnis des zweiten Teils zur Beschreibung des asymptotischen Verhaltens der Varianz benutzen.
Die vorliegende Arbeit beschäftigt sich mit Gruppen von quasi-Automorphismen von Graphen, genauer gesagt, von gefärbten Graphen. Ein gefärbter Graph ist ein Graph, dessen Kantenmenge in eine disjunkte Vereinigung von Mengen von Kanten einer bestimmten Farbe zerlegt ist. Ein Automorphismus eines solchen Graphen muss insbesondere die Farben der Kanten respektieren. Ein quasi-Automorphismus eines solchen Graphen ist eine Bijektion der Eckenmenge auf sich selbst, die nur endlich oft die Autmomorphismeneigenschaft verletzt, d.h. nur endlich viele Kanten nicht respektiert und nur endlich viele Kanten neu entstehen läßt. Die Menge der quasi-Automorphismen eines Graphen bildet eine Untergruppe in der Gruppe der Permutationen der Eckenmenge. Eine Auswahl interessanter Beispiele solcher Gruppen und manche ihrer Eigenschaften sind neben einigen grundsätzlichen Überlegungen Thema dieser Arbeit. Die erste Klasse von Graphen, die wir untersuchen, sind Cayley-Graphen (endlich erzeugter) Gruppen. Dabei werden wir zeigen, dass die quasi-Automorphismengruppe eines Cayley-Graphen nicht von dem (endlichen) Erzeugendensystem abhängt. Wir werden zeigen, dass für eine einendige Gruppe $G$ die quasi-Automorphismengruppe des Cayley-Graphen stets als semidirektes Produkt der finitären Permutationen von $G$ und der Gruppe $G$ selbst zerfällt. In der Klasse der mehrendigen Gruppen gibt es genau $2$ Gruppen für die das ebenfalls gilt, nämlich die Gruppe der ganzen Zahlen ...Z und die unendliche Diedergruppe $D_infty$. In allen anderen Gruppen ist das oben erwähnte semidirekte Produkt stets eine echte Untergruppe. Trotzdem werden wir im Ausblick eine Konstruktion angeben, die für eine gegebene Gruppe $G$ einen Graphen $Gamma$ liefert, dessen quasi-Automorphismengruppe als semidirektes Produkt von $S_Gamma$ -- so bezeichnen wir die Gruppe der finitären Permutationen der Ecken von $Gamma$ -- und $G$ zerfällt. Des Weiteren werden wir die quasi-Automorphismengruppe des ebenen binären Wurzelbaumes betrachten. Wir werden zeigen, dass diese eine Erweiterung von (Richard) Thompsons Gruppe VV durch die Gruppe der finitären Permutationen ist, eine Präsentierung entwickeln und die Endlichkeitseigenschaften dieser Gruppe und einiger Untergruppen beleuchten. Insbesondere werden wir einen Zellkomplex konstruieren, auf dem die Gruppe der quasi-ordnungserhaltenden quasi-Automorphismen, welche das Urbild der Untergruppe FF von VV unter der kanonischen Projektion ist, mit endlichen Stabilisatoren operiert. Diese Operation erfüllt dabei die Bedingungen, die nötig sind, um mit Hilfe von Browns Kriterium nachzuweisen, dass die Gruppe vom Typ FPunendlich ist. Das co-Wort-Problem einer Gruppe $G$ bezüglich eines unter Inversion abgeschlossenen Erzeugendensystems $X$ ist die Sprache aller Worte aus dem freien Monoid $X^*$, die unter der kanonischen Projektion auf ein Element ungleich der Identität in $G$ abgebildet werden. Wir werden zeigen, dass das co-Wort-Problem der quasi-Automorphismengruppe des ebenen binären Wurzelbaumes eine kontext-freie Sprache bildet. Sei $mathop{coCF}$ die Klasse der Gruppen mit kontextfreiem co-Wort-Problem. Diese Klasse ist abgeschlossen bezüglich Untergruppenbildung und alle Gruppen, deren Zugehörigkeit zu $mathop{coCF}$ bisher nachgewiesen wurde, sind Unterguppen der quasi-Automorphismengruppe des ebenen binären Wurzelbaumes. Die $n$-strahligen Houghton-Gruppen erweisen sich als quasi-Automorphismengruppen von Sterngraphen, d.h. von Graphen, die disjunkte Vereinigungen von $n$ Strahlen verschiedener Farben sind. Wir werden uns mit geometrischen Phänomenen der Cayley-Graphen dieser Gruppen beschäftigen. Insbesondere werden wir nachweisen, dass die $2$-strahlige Houghton-Gruppe Houn[2] beliebig tiefe Sackgassen besitzt. Eine Sackgasse der Tiefe $k$ in einem Cayley-Graphen ist ein Element, dessen Abstand zur Identität mindestens so groß ist, wie der Abstand zur Identität aller Elemente im $k$-Ball um das Element. Sogar in einem stärkeren Sinne, der in dieser Arbeit definiert wird, ist die Tiefe der Sackgassen unbeschränkt. Um dies und verwandte Fragen besser behandlen zu können, entwickeln wir Modelle, die eine Beschreibung der Cayley-Graphen von Houn[n] ermöglichen. Im abschließenden Ausblick thematisieren wir einige Ansätze, in denen wir interessante Anwendungen von quasi-Automorphismengruppen sehen.
Im Zentrum dieser Arbeit steht die Operation der Gruppe Gamma:=SL_n(Z[1/m]) auf dem symmetrischen Raum M:=SL_n(R)/SO(n). Allgemeiner betrachten wir die Operation rho:Gamma->Isom(M) einer S-arithmetischen algebraischen Gruppe durch Isometrien auf dem zugehörigen symmetrischen Raum M. Die symmetrischen Räume sind Riemannsche Mannigfaltigkeiten mit nichtpositiver Krümmung und daher insbesondere CAT(0)-Räume. R. Bieri und R. Geoghegan haben für die Operation rho:G->Isom(M) einer abstrakten Gruppe G auf einem CAT(0)-Raum M die geometrischen Invarianten Sigma^k(rho) als Teilmenge des Randes von M eingeführt (vgl. [Robert Bieri and Ross Geoghegan, Connectivity properties of group actions on non-positively curved spaces, vol. 161, Memoirs of the AMS, no. 765, American Mathematical Society, 2003]). Die Fokusierung, die durch die geometrischen Invarianten erreicht wird, hat sich in vielen Fällen bewährt, in denen eine Operation durch Translationen auf dem euklidischen Raum zur Verfügung steht. Über die Invarianten von anderen CAT(0)-Operationen ist noch wenig bekannt. In der vorliegenden Arbeit berechnen wir nun die geometrischen Invarianten Sigma^k(rho) für die oben erwähnte Operation rho der S-arithmetischen Gruppe Gamma auf dem zugehörigen symmetrischen Raum M. Wir erhalten für die Gruppe SL_n(Z[1/m]) die folgende Invariante: Sigma^k(rho) ist der ganze Rand von M, falls k kleiner als s(n-1) ist; Sigma^k(rho) ist die Menge aller Randpunkte e von M, die nicht im Rand eines rational definierten flachen Unterraum von M liegen, falls k größer oder gleich s(n-1) ist. Hierbei ist s die Anzahl der verschiedenen Primteiler von m. Die obigen Resultate sind eine Verallgemeinerung derer in [Robert Bieri and Ross Geoghegan, Controlled Connectivity of SL_2(Z[1/m]), Geometriae Dedicata 99 (2003), 137--166]. Der Beweis, den wir geben, besteht aus einer Vereinfachung des Beweises von Bieri und Geoghegan, die dann auf die allgemeinere Situation angepasst werden konnte. Ein interessanter Aspekt ergibt sich, wenn wir für eine Operation rho auf M die Zahlen k betrachten, für die gilt: (*) Sigma^k(rho) ist der ganze Rand von M. Operiert die Gruppe Gamma mit diskreten Bahnen, dann ist (*) äquivalent zur Eigenschaft, daß die Punktstabilisatoren Gamma_a, für a aus M, vom Typ F_k sind. Die Eigenschaft (*) ist auch von Interesse für S-arithmetische Untergruppen einer linearen algebraischen Gruppe über einem Funktionenkörper. Wir zeigen, daß es hier eine naheliegende Operation rho' auf einem Bruhat-Tits Gebäude M' gibt, so daß Gamma' ein Punktstabilisator und damit die Eigenschaft (*) mit der Eigenschaft "Gamma' ist vom Typ F_k" zusammenfällt. Im Zahlkörperfall sind die Verhältnisse ganz anders. Unsere S-arithmetischen Gruppen operieren auf dem symmetrischen Raum M nicht mit diskreten Bahnen und sind durchwegs vom Typ F_k für alle k. Dagegen erlaubt unser Hauptresultat die Bestimmung der Zahlen k mit der Eigenschaft (*) und zeigt eine interessante Abhängigkeit von s=|S| und dem Rang r der algebraischen Gruppen (rho erfüllt (*) <=> k<rs). Das Hauptresultat wird außerdem nicht nur für SL_n(Q), sondern allgemeiner für Chevalley-Guppen über Q oder Q(i) gezeigt, so daß wir damit für eine Reihe von klassischen CAT(0)-Operationen die Invarianten Sigma^k(rho) bestimmt haben.
Die Hilbertsche Grundlegung der Geometrie darf für alle analogen Untersuchungen als vorbildlich gelten. Zwei ihrer Eigenschaften sind es, auf die es hier ankommt. Erstens wird von allen sprachlichen Definitionen der Objekte, mit denen sie operiert, wie Punkt, Gerade, zwischen usw. abgesehen; nur ihre gegenseitigen Beziehungen und deren Grundgesetze werden axiomatisch an die Spitze gestellt. Zweitens werden die Axiome in verschiedene Gruppen gewisser Eigenart und Tragweite gespalten (die des Schneidens und Verbindens, die Axiome der Ordnung, der Kongruenz usw.), und es ist eine wesentliche Aufgabe des axiomatischen Aufbaues, zu prüfen, bis zu welchen Resultaten eine einzelne oder mehrere dieser Gruppen für sich führen. Die gleiche Behandlung eignet sich für die Mengenlehre. Von sprachlicher Einführung der Begriffe Menge, Bereich usw. ist daher ebenso abzusehen , wie von der des Punktes oder Raumes. Ebenso kann man hier gewiisse Axiomgruppen unterscheiden, die Axiome der Aquivalenz, die Axiome der Ordnung usw., und kann die gleichen Fragen stellen, wie im Gebiet der Geometrie. Dies soll im folgenden geschehen und zwar für denjenigen Teii, der nur mit dar Äquivalenz der Mengen, der Mengenteilung und Mengenverbindung, sowie der Mengenvergleichung operiert.....
In dem Artikel ,,Zur Axiomatik der Mengenlehre" habe ich die Axiome, die sich mit den Gebieten der Äquivalenz, der Mengenteilung und Mengenuergleichung beschäftigen, einer Erörterung unterzogen. An zwei Resultate dieses Artikels knüpfe ich hier an. Erstens einmal, da die in ihm durchgeführten Untersuchungen auf die Elemente der Mengen gar nicht eingehen, so stellen sie, allgemein gesprochen, axiomatische Betrachtungen über Größen und Größenbeziehungen dar, an denen die Mengen ja Teil haben; und zweitens hatte eine der dort analysierten Beziehungen den Gedanken nahegelegt, auch Größen entgegengesetzter Art (resp. Mengen von zweierlei Art von Elementen) in Betracht zu ziehen, und auf sie die oben genannten Operationen auszudehnen. Hier nun gebe ich im folgenden einige Ergänzungen. Bereits a. a. O.war bemerkt worden, daß es naturgemäß der Untersuchung bedarf, ob für die so charakterisierten Mengen die weiteren allgemeinen Sätze der Cantorschen Theorie in Kraft bleiben. Inzwischen hat mir Herr A. Fränkel mitgetelt, daß für das von mir konstruierte Beispiel schon ein Teil der in meinem Artikel zugrunde gelegten Axiome versagt; und zwar ein Teil der Axiome über Teilmengen. Über Teilmengen habe ich zwei Axiome an die Spitze gestellt. ......
This thesis exhibits skeins based on the Homfly polynomial and their relations to Schur functions. The closures of skein-theoretic idempotents of the Hecke algebra are shown to be specializations of Schur functions. This result is applied to the calculation of the Homfly polynomial of the decorated Hopf link. A closed formula for these Homfly polynomials is given. Furthermore, the specialization of the variables to roots of unity is considered. The techniques are skein theory on the one side, and the theory of symmetric functions in the formulation of Schur functions on the other side. Many previously known results have been proved here by only using skein theory and without using knowledge about quantum groups.
Euklidische Zerlegungen nicht-kompakter hyperbolischer Mannigfaltigkeiten mit endlichem Volumen
(1998)
Epstein and Penner constructed in [EP88] the Euclidean decomposition of a non-compact hyperbolic n-manifold of finite volume for a choice of cusps, n >= 2. The manifold is cut along geodesic hyperplanes into hyperbolic ideal convex polyhedra. The intersection of the cusps with the Euclidean decomposition determined by them turns out to be rather simple as stated in Theorem 2.2. A dual decomposition resulting from the expansion of the cusps was already mentioned in [EP88]. These two dual hyperbolic decompositions of the manifold induce two dual decompositions in the Euclidean structure of the cusp sections. This observation leads in Theorems 5.1 and 5.2 to easily computable, necessary conditions for an arbitrary ideal polyhedral decomposition of the manifold to be a Euclidean decomposition.
Epstein and Penner constructed in [EP88] the Euclidean decomposition of a non-compact hyperbolic n-manifold of finite volume for a choice of cusps, n >= 2. The manifold is cut along geodesic hyperplanes into hyperbolic ideal convex polyhedra. The intersection of the cusps with the Euclidean decomposition determined by them turns out to be rather simple as stated in Theorem 2.2. A dual decomposition resulting from the expansion of the cusps was already mentioned in [EP88]. These two dual hyperbolic decompositions of the manifold induce two dual decompositions in the Euclidean structure of the cusp sections. This observation leads in Theorems 5.1 and 5.2 to easily computable, necessary conditions for an arbitrary ideal polyhedral decomposition of the manifold to be a Euclidean decomposition.
Die vorliegende Arbeit beschäftigt sich mit der BFV-Reduktion von Hamiltonschen Systemen mit erstklassigen Zwangsbedingungen im Rahmen der klassischen Hamiltonschen Mechanik und im Rahmen der Deformationsquantisierung. Besondere Aufmerksamkeit wird dabei Zwangsbedingungen zuteil, die als Nullfaser singulärer äquivarianter Impulsabbildungen entstehen. Es ist schon länger bekannt, daß für Nullfasern regulärer äquivarianter Impulsabbildungen die in der theoretischen Physik gebräuchliche Methode der BFV-Reduktion zur Phasenraumreduktion nach Marsden/Weinstein äquivalent ist. In [24] konnte gezeigt werden, daß in dieser Situation die BFV-Reduktion sich auch im Rahmen der Deformationsquantisierung natürlich formulieren läßt und erfolgreich zur Konstruktion von Sternprodukten auf Marsden/Weinstein-Quotienten verwendet werden kann. Ein Hauptergebnis der vorliegenden Arbeit besteht in der Verallgemeinerung der Ergebnisse aus [24] auf den Fall singulärer Impulsabbildungen, deren Komponenten 1.) das Verschwindungsideal der Zwangsfläche erzeugen und 2.) einen vollständigen Durchschnitt bilden. Die Argumentation von [24] wird durch Gebrauch der Störungslemmata aus dem Anhang A.1 systematisiert und vereinfacht. Zum Existenzbeweis von stetigen Homotopien und stetiger Fortsetzungsabbildung für die Koszulauflösung werden der Zerfällungssatz und der Fortsetzungssatz von Bierstone und Schwarz [20] benutzt. Außerdem wird ein ’Jacobisches Kriterium’ für die Überprüfung von Bedingung 2.) angegeben. Basierend auf diesem Kriterium und Techniken aus [3] werden die Bedingungen 1.) und 2.) an einer Reihe von Beispielen getestet. Als Korollar erhält man den Beweis dafür, daß es symplektisch stratifizierte Räume gibt, die keine Orbifaltigkeiten sind und dennoch eine stetige Deformationsquantisierung zulassen. Ferner wird (ähnlich zu [92]) eine konzeptionielle Erklärung dafür gegeben, warum im Fall vollständiger Durchschnitte das Problem der Quantisierung der BRST-Ladung eine so einfache Lösung hat. Bildet die Impulsabbildung eine erstklassige Zwangsbedingung, ist aber kein vollständiger Durchschnitt, dann ist es im allgemeinen nicht bekannt, wie entsprechende Quantenreduktionsresultate zu erzielen sind. Ein Hauptaugenmerk der Untersuchung wird es deshalb sein, in dieser Situation die klassische BFV-Reduktion besser zu verstehen – natürlich in der Hoffnung, Grundlagen für eine etwaige (Deformations-)Quantisierung zu liefern. Wir werden feststellen, daß es zwei Gründe gibt, die Tate-Erzeuger (alias: Antigeister höheren Niveaus) notwendig machen: die Topologie der Zwangsfläche und die Singularitätentheorie der Impulsabbildung. Die Zahl der Tate-Erzeuger kann durch Übergang zu projektiven Tate-Erzeugern, also Vektorbündeln, verringert werden. Allerdings sorgt Halperins Starrheitssatz [57] dafür, daß im wesentlichen alle Fälle, für die die Zwangsfläche kein lokal vollständiger Durchschnitt ist, zu unendlich vielen Tate-Erzeugern führen. Erzeugen die Komponenten einer Impulsabbildung einer linearen symplektischen Gruppenwirkung das Verschwindungsideal der Zwangsfläche, so kann man eine lokal endliche Tate-Auflösung finden. Diese besitzt nach dem Fortsetzungssatz und dem Zerfällungssatz von Bierstone und Schwarz stetige, kontrahierende Homotopien. Ausgehend von einer solchen Tate-Auflösung konstruieren wir, die klassische BFV-Konstruktion für vollständige Durchschnitte verallgemeinernd, eine graduierte superkommutative Algebra. Wir können zeigen, daß diese graduierte Algebra auch im Vektorbündelfall eine graduierte Poissonklammer besitzt, die sogenannte Rothstein-Poissonklammer. Die Existenz einer solchen Poissonklammer war bereits von Rothstein [87] für die einfachere Situation einer symplektischen Supermannigfaltigkeit bewiesen worden. Darüberhinaus werden wir sehen, daß es auch im Vektorbündelfall eine BRST-Ladung gibt. Diese sieht im Fall von Impulsabbildungen etwas einfacher aus als für allgemeine erstklassige Zwangsbedingungen. Insgesamt wird also die klassische BFV-Konstruktion [95] auf den Fall projektiver Tate-Erzeuger verallgemeinert, und als eine Homotopieäquivalenz in der additiven Kategorie der Fréchet-Räume interpretiert.
Ein Mathematiker mit universalem Anspruch : über Max Dehn und sein Wirken am Mathematischen Seminar
(2002)
Für eine erste Blüte der Mathematik in Frankfurt gab Max Dehn (1878 –1952) in den Jahren ab 1921 bis 1935 entscheidende Impulse. Seine völlig neuen Ideen zur Knotentheorie und zur Topologie beeinflussten die Entwicklung der Mathematik weit über Deutschland hinaus. 1935 fand sein Wirken in Frankfurt durch den Terror der Nationalsozialisten ein jähes Ende. Nach einer gefahrvollen Flucht über Norwegen, Finnland, die Sowjetunion und Japan erreichte Dehn schließlich, 62-jährig, die Vereinigten Staaten von Nordamerika. Eine seinen Fähigkeiten entsprechende Stellung konnte er dort nicht mehr erlangen. Sein fünfzigster Todestag in diesem Jahr ist Anlass für diese Rückschau.
Binärsuchbäume sind eine wichtige Datenstruktur, die in der Informatik vielfach Anwendung finden. Ihre Konstruktion ist deterministisch, zur Analyse ihrer Eigenschaften wird aber eine rein zufällige Eingabe zugrundegelegt. Viele Größe, wie z.B. Tiefe, Höhe und Pfadlänge werden seit Jahren viel untersucht. Als besonders interessant hat sich die Analyse des Profils, der Anzahl Knoten einer bestimmten Tiefe herausgestellt. In dieser Arbeit wird ein funktionaler Grenzwertsatz für das am Erwartungswert normierte Profil vorgestellt. Dazu werden unterschiedliche Zugänge gewählt, die hauptsächlich auf dem sogenannten Profil-Polynom beruhen. Zunächst wird ein klassischer Zugang mit Hilfe von Martingalen besprochen. Der diskrete Prozess wird dazu auf kanonische Weise in ein zeitstetiges Modell (Yule-Prozess) eingebettet. Ergebnisse im kontinuierlichen Prozess werden dann durch Stoppen auf den diskreten übertragen. Zudem wird ein neuerer Zugang vorgestellt, der auf der Kontraktionsmethode in Banachräumen unter Verwendung der Zolotarev-Metrik beruht.
Concentration of multivariate random recursive sequences arising in the analysis of algorithms
(2006)
Stochastic analysis of algorithms can be motivated by the analysis of randomized algorithms or by postulating on the sets of inputs of the same length some probability distributions. In both cases implied random quantities are analyzed. Here, the running time is of great concern. Characteristics like expectation, variance, limit law, rates of convergence and tail bounds are studied. For the running time, beside the expectation, upper bounds on the right tail are particularly important, since one wants to know large values of the running time not taking place with possibly high probability. In the first chapter game trees are analyzed. The worst case runnig time of Snir's randomized algorithm is specified and its expectation, asymptotic behavior of the variance, a limit law with uniquely characterized limit and tail bounds are identified. Furthermore, a limit law for the value of the game tree under Pearl's probabilistic modell is proved. In the second chapter upper and lower bounds for the Wiener Index of random binary search trees are identified. In the third chapter tail bounds for the generation size of multitype Galton-Watson processes (with immigration) are derived, depending on their offspring distribution. Therefore, the method used to prove the tail bounds in the first chapter is generalized.
Approximating Perpetuities
(2006)
A perpetuity is a real valued random variable which is characterised by a distributional fixed-point equation of the form X=AX+b, where (A,b) is a vector of random variables independent of X, whereas dependencies between A and b are allowed. Conditions for existence and uniqueness of solutions of such fixed-point equations are known, as is the tail behaviour for most cases. In this work, we look at the central area and develop an algorithm to approximate the distribution function and possibly density of a large class of such perpetuities. For one specific example from the probabilistic analysis of algorithms, the algorithm is implemented and explicit error bounds for this approximation are given. At last, we look at some examples, where the densities or at least some properties are known to compare the theoretical error bounds to the actual error of the approximation. The algorithm used here is based on a method which was developed for another class of fixed-point equations. While adapting to this case, a considerable improvement was found, which can be translated to the original method.
Installment Optionen
(2004)
Die vorliegende Arbeit beschäftigt sich im Wesentlichen mit Installment Optionen und deren Bewertung und Hedgemöglichkeiten. Installment Optionen werden vor allem im internationalen Treasurymanagement eingesetzt und dienen der Absicherung von Wechselkursrisiken. Die Besonderheit besteht darin, daß ein Konzern die Optionsprämie über mehrere Zeitpunkte aufteilen kann, zu denen er jeweils entscheidet, ob die Absicherung überhaupt noch benötigt wird. Dies könnte unter Umständen nicht mehr der Fall sein, wenn das zugrunde liegende internationale Geschäft des Konzerns wider Erwarten nicht zustande gekommen ist. Der exakte Wert einer Installment Option im Black-Scholes Modell besteht aus einem Ausdruck von Mehrfachintegralen, wohingegen die Anwendung verschiedener Bewertungsmethoden auf diesen approximierte Werte liefert. Die Untersuchung des Verhaltens mehrerer bekannter Methoden und die Entwicklung einer neuen Bewertungsformel für Installment Option ist Inhalt dieser Arbeit. Weiterhin wird die kontinuierliche Version der Installment Option betrachtet und für diese ein neuer Hedge bewiesen.
Gitter sind diskrete additive Untergruppen des Rn. Praktische Bedeutung erlangte die Gittertheorie durch effziente Algorithmen zur Gitterbasenreduktion, mit deren Hilfe Optimierungsprobleme gelöst werden können. Der erste dieser Algorithmen wurde von Lenstra, Lenstra und Lovasz entwickelt. Schnorr und Euchner entwickelten effizientere Algorithmen. Sie untersuchten die Güte der Reduktion anhand von Rucksack-Problemen. Bei einem Rucksack-Problem der Dimension n müssen aus einer gegebenen Menge von n Gewichten diejenigen bestimmt werden, die zusammen einen gegeben Rucksack genau ausfüllen. Die Algorithmen von Schnorr und Euchner lösen fast alle Rucksack-Probleme der Dimensionen 42 bis 66. Meine neuen verbesserten Algorithmen lösen einen noch größeren Anteil der Rucksack-Probleme in kürzerer Rechenzeit. Gleichzeitig sind sie in Dimensionen 103 bis 151. Coster, Joux, LaMacchia. Odlyzko, Schnorr und Stern geben eine untere Schranke für die Größe der Gewichte von Rucksack-Problemen an, die fast immer gelöst werden können. Die Gewichte werden zufällig aus einem Intervall natüurlicher Zahlen gewählt. Dieses Ergebnis erweitere ich auf k-fache Rucksack-Probleme. Weiterhin kann für für die Wahl jedes Gewichtes eine beliebige Menge ganzer Zahlen festgelegt werden. Ebenso sind Mengen mit nur einem Element zulässig.
Wir verallgemeinern die Reduktionstheorie von Gitterbasen für beliebige Normen. Dabei zeigen wir neue Eigenschaften reduzierter Basen für die verallgemeinerten Reduktionsbegriffe. Wir verallgemeinern den Gauß-Algorithmus zur Reduktion zweidimensionaler Gitterbasen für alle Normen und erhalten eine universelle scharfe obere Schranke für die Zahl seiner Iterationen. Wir entwickeln für spezielle lp-Normen eine Variante des Gauß-Algorithmus mit niedriger Bit-Komplexität. Hierzu wird Schönhages schneller Reduktionsalgorithmus für quadratische Formen auf die Reduktion von Gitterbasen im klassischen zentrierten Fall übertragen.
It is commonly agreed that cortical information processing is based on the electric discharges (spikes') of nerve cells. Evidence is accumulating which suggests that the temporal interaction among a large number of neurons can take place with high precision, indicating that the efficiency of cortical processing may depend crucially on the precise spike timing of many cells. This work focuses on two temporal properties of parallel spike trains that attracted growing interest in the recent years: In the first place, specific delays (phase offsets') between the firing times of two spike trains are investigated. In particular, it is studied whether small phase offsets can be identified with confidence between two spike trains that have the tendency to fire almost simultaneously. Second, the temporal relations between multiple spike trains are investigated on the basis of such small offsets between pairs of processes. Since the analysis of all delays among the firing activity of n neurons is extremely complex, a method is required with which this highly dimensional information can be collapsed in a straightforward manner such that the temporal interaction among a large number of neurons can be represented consistently in a single temporal map. Finally, a stochastic model is presented that provides a framework to integrate and explain the observed temporal relations that result from the previous analyses.
Die zentrale Frage dieser Studie lautet: Wann ist eine stetige Funktion auf einem kompakten Raum, welche Werte in einem lokalkonvexen Raum annimmt, (Pettis-)integrierbar?
Im ersten Kapitel wird definiert, was konvexe Kompaktheit ist. Es wird das Pettis-Integral vorgestellt, und der Zusammenhang zwischen der konvexen Kompaktheitseigenschaft (oder ccp) und dem Pettis-Integral wird erläutert. Außerdem stellt dieses Kapitel dar, inwiefern die ccp aus stärkeren Eigenschaften lokalkonvexer Räume folgt oder schwächere impliziert. Das zweite Kapitel beweist hauptsächlich den Satz von Krein, der einen Zusammenhang zwischen Vollständigkeit unter der Mackey-Topologie und der ccp unter der schwachen Topologie herstellt. Das dritte Kapitel erläutert mit Gegenbeispielen, inwiefern die in Kapitel 1 vorgestellten Vollständigkeitseigenschaften lokalkonvexer Räume notwendig gegeneinander abgegrenzt sind. Das vierte Kapitel stellt zuerst das Bochner-Integral und das starke OperatorIntegral vor, um dann die starke konvexe Kompaktheitseigenschaft oder sccp einzufuhren, eine Eigenschaft, welche der ccp verwandt ist. Es wird fur einen Raum beispielhaft bewiesen, daß er diese Eigenschaft besitzt. Zuletzt wird der Zusammenhang von sccp und ccp ausfuhrlicher dargestellt.
Diese Arbeit wendet sich an Leser, denen die Grundlagen der Theorie lokalkonvexer Räume schon vertraut sind. Insbesondere ist Vertrautheit mit den Begriffen tonneliert, ultrabornologisch, bornologisch, polare Topologie unterstellt. Man findet eine kurze und einfach verständliche Einfuhrung im Werk [RR]. Alle über diese Grundlagen hinausgehenden Resultate werden in dieser Arbeit mit Beweis ausgefuhrt, oder es wird mit Angabe der Fundstelle auf die Literatur verwiesen.
The existence of a mean-square continuous strong solution is established for vector-valued Itö stochastic differential equations with a discontinuous drift coefficient, which is an increasing function, and with a Lipschitz continuous diffusion coefficient. A scalar stochastic differential equation with the Heaviside function as its drift coefficient is considered as an example. Upper and lower solutions are used in the proof.
Die Vorstellung, daß ein Quantensystem zu jedem Zeitpunkt einen bestimmten Zustand (aus einem "klassischen" Phasenraum) einnimmt, ist im Formalismus der Quantenmechanik nicht vorgesehen. Man kann eine solche Vorstellung zwar verträglich mit den Regeln der QM unterhalten, jedoch erweisen sich dann ganz verschiedene Wahrscheinlichkeitsverteilungen auf dem Phasenraum als experimentell ununterscheidbar; solche Modelle postulieren sozusagen die Existenz einer "verborgenenen Information" neben den prüfbaren Fakten. Es wird gezeigt, daß dies für alle Modelle gilt, die mit den von der QM für jede Observable vorhergesagten Wahrscheinlichkeitsverteilung im Einklang stehen, selbst wenn sie erlauben, daß nicht jede Verteilung auf dem Phasenraum durch makroskopische Aparaturen präpariert werden kann bzw. daß das Meßergebnis garnicht deterministisch vom Zustand des Quantensystems abhängt, sondern das Meßgerät selbst einem (vom zu messenden System unabhängigen) Zufall unterliegt. Dazu ist eine gründliche Auseinandersetzung mit der Theorie der Wahrscheinlichkeitsmaße auf distributiven und auf nicht-distributiven Verbänden nötig.
Im Rahmen dieser Arbeit möchte ich nun aufzeigen, dass ein Projekt zu Glücksspielen eine „reichhaltige Lernsituation“ darstellen kann, in der die Schüler Raum, Gelegenheit und Anlass haben, Grunderfahrungen mit zufälligen Vorgängen zu machen, darauf aufbauend wichtige Begriffe zu bilden und schließlich wesentliche stochastische Zusammenhänge zu erkennen. Der Projektmethode entsprechend lag ein Großteil meiner Tätigkeiten im Vorfeld in vorbereitenden und planenden Tätigkeiten. Während der Projektdurchführung trat ich als beratender „Hintergrundlehrer“ auf. Die Schüler arbeiteten weitgehend selbstständig. Der Schwerpunkt dieser Arbeit liegt daher auf meinen didaktischen und methodischen Überlegungen zur Vorbereitung des Projekts.
Wir werden uns in dieser Arbeit vorwiegend mit einem Modell befassen, das Y. Peres, C. Kenyon, W. Evans und L.J. Schulman 1998 in ihrem Artikel \Broadcasting on trees and the Ising-Modell" eingeführt haben.
In diesem Modell wird ein Signal, das die Werte +1 oder -1 annehmen kann, von der Wurzel eines Baumes aus entlang der Äste eines unendlichgroßen Baumes übertragen. Die Kanten des Baumes agieren dabei als Übertragungskanäle zwischen den Knoten. Jede Kante kann das Signal korrekt übertragen oder es flippen, das heißt, das Vorzeichen des Signals umkehren.
Das Übertragungsverhalten der Kanten ist zufällig. Mit einer festen Wahrscheinlichkeit ϵ, mit 0 < ϵ <= 1/2 , verfälscht eine Kante das Signal. Dies geschieht an allen Kanten unabhängig mit der gleichen Wahrscheinlichkeit. Es stellt sich nun die Frage, wie groß diese Fehlerwahrscheinlichkeit höchstens sein darf, damit das, was in der Krone des Baumes ankommt, noch etwas zu tun hat mit dem, was in der Wurzel eingespeist wird. Mit anderen Worte: Sind die Signale auf Knoten, die einen Abstand >= n von der Wurzel haben, für n -> ∞ asymptotisch unabhängig vom Signal in der Wurzel? Eine Möglichkeit, den Grad der Abhängigkeit zu messen, ist die sogenannte Information, der Kullback-Leibler-Abstand von gemeinsamer Verteilung zur Produkt-Verteilung, die in Definition 16 eingeführt wird.
Wir werden sehen, daß es eine kritische Schwelle ϵc;I für Informationsübertragung gibt. Ist die Fehlerwahrscheinlichkeit größer als ϵc;I , so ist die Information, die zwischen Wurzel und Krone übertragen wird, 0. Ist die Fehlerwahrscheinlichkeit kleiner als ϵc;I , so wird Information übertragen. Dieser kritische Wert ϵc;I hängt nur von der Branching-Number, einer Art mittleren Verzweigungszahl, des Baumes (vgl. Definition 1) ab.
Wir werden sehen, daß das Broadcasting-Modell eine elegante Formulierung eines wohlbekannten Modells, des Ising-Modells, mit freien Randbedingungen, ist.
Im Ising-Modell hat jeder Knoten des Baumes einen "magnetischen" Spin, der entweder +1 oder -1 sein kann. Spins direkt benachbarter Knoten beeinflussen sich, in dem sie versuchen, den gleichen Wert anzunehmen. Diesem Effekt wirkt ein thermischer Einfluß entgegen, der mittels eines als Temperatur bezeichneten Parameters modelliert wird.
Die klassische Frage im Ising-Modell ist, ob Phasenübergang stattfindet. Wir wollen Phasenübergang als das Phänomen verstehen, daß die Wurzel des Baumes die Vorgabe von Randbedingungen auf der Krone des Baumes spürt. Ist dies der Fall, so sagen wir, daß Phasenübergang stattfindet. Auch dies ist eine
Form der gegenseitigen Beeinflussung zwischen Wurzel und Krone des Baumes. Russel Lyons hat 1989 in seinem Artikel \The Ising-Model on trees and treelike Graphs" das Ising-Modell auf Bäumen untersucht und gezeigt, daß es eine kritische Temperatur tc für Phasenübergang gibt. Ist die Temperatur höher als tc, so spürt die Wurzel nichts von den Randbedingungen der Krone; ist die Temperatur geringer als tc, so haben die Randbedingungen Einfluß auf die Wurzel. Auch hier hängt die kritische Temperatur nur von der Branching-Number des Baumes ab.
In der Broadcasting-Formulierung des Modells ist der Fluß von Information ein naheliegendes Werkzeug, um die Beeinflussung von Wurzel und Krone zu messen, in der Ising-Formulierung ist die Existenz von Phasenübergang ein ebenso naheliegendes Werkzeug, ebendiesen Einfluß zu messen.
Wir werden die beiden Arten der Beeinflussung miteinander vergleichen und können zeigen, daß für die Übertragung von Information stets eine stärkere Interaktion zwischen den Knoten notwendig ist, als für den Einfluß der Randbedingungen aus der Krone.
Als letztes Phänomen werden wir untersuchen, ob es einen Pfad im Baum gibt, der in der Wurzel startend nur Knoten gleichen Spins besucht und die unendlich weit entfernte Krone erreicht. Wir bezeichnen dieses Phänomen als Spinperkolation.
Wir werden die Berechnung der kritischen Interaktion für Spinperkolation in einem Bernoulli-Feld auf den Kanten rekapitulieren und dann zeigen, daß die Existenz eines Perkolationspfades nur von der Interaktionsstärke des Modells und nicht von etwaigen Randbedingungen abhängt. Dabei kombinieren wir Ergebnisse aus zwei Arbeiten von Lyons und die Erkenntnis, daß Broadcasting- Modell und freies Ising-Modell identisch sind. Wir erhalten so einen neuen, einfachen Beweis über die kritische Interaktion für Spinperkolation in der Plus-Phase des Ising-Modells, die Lyons bereits in [7] berechnet hat.
The synchronization of neuronal firing activity is considered an important mechanism in cortical information processing. The tendency of multiple neurons to synchronize their joint firing activity can be investigated with the 'unitary event' analysis (Grün, 1996). This method is based on the nullhypothesis of independent Bernoulli processes and can therefore not tell whether coincidences observed between more than two processes can be considered "genuine" higher- order coincidences or whether they might be caused by coincidences of lower order that coincide by chance ("chance coincidences"). In order to distinguish between genuine and chance coincidences, a parametric model of independent interaction processes (MIIP) is presented. In the framework of this model, Maximum-Likelihood estimates are derived for the firing rates of n single processes and for the rates with which genuine higher order correlations occur. The asymptotic normality of these estimates is used to derive their asymptotic variance and in order to investigate whether higher order coincidences can be considered genuine or whether they can be explained by chance coincidences. The empirical test power of this procedure for n=2 and n=3 processes and for finite analysis windows is derived with simulations and compared to the asymptotic values. Finally, the model is extended in order to allow for the analysis of correlations that are caused by jittered coincidences.
In dieser Arbeit werden die mathematischen Grundlagen zur Konstruktion der primären Felder der minimalen Modelle der konformen Quantenfeldtheorie beschrieben. Wir untersuchen Verma und Fock-Moduln der Virasoro-Algebra und klassifizieren diese Moduln bezüglich der Struktur der (ko-) singulären Vektoren. Wir definieren die Vertex-Operatoren zwischen gewissen Fock-Moduln (die eine kanonische Hilbertraumstruktur besitzen) und beweisen verschiedene Eigenschaften dieser Operatoren: Unter bestimmten Voraussetzungen sind Vertex-Operatoren dicht definierte, nicht abschließbare Operatoren zwischen den Fock-Moduln. Radialgeordnete Produkte von Vertex-Operatoren existieren auf einem dichten Teilraum. Wir beweisen Kommutatorrelationen zwischen Vertex-Operatoren und den Generatoren der Virasoro-Algebra. Dann definieren wir die integrierten Vertex-Operatoren und zeigen, daß diese Operatoren im wesentlichen wieder die Eigenschaften der nichtintegrierten Vertex-Operatoren haben. Gewisse integrierte Vertex-Operatoren können mit konformen Felder identifiziert werden. Ein unter den Vertex-Operatoren invarianter Unterraum der Fock-Moduln kann mit dem physikalischen Zustandsraum identifiziert werden.
Über die Anzahlfunktion π(x)
(1999)
Bereits Euklid wusste, dass es unendlich viele Primzahlen gibt. Euler zeigte die qualitative Aussage ¼(x) x ! 0 bei x ! 1. Legendre definierte als erster die Anzahlfunktion ¼(x) als die Anzahl aller Primzahlen · x, (x 2 R) und vermutete irrtümlicherweise, dass ¼(x) = x log(x)¡B; wobei lim x!1 B(x) = 1; 083 66 : : : ist. Gauss vermutete, dass die Funktionen ¼(x) und li(x) := lim "!0 ">0 0@ u=1¡" Z u=0 du log(u) + u=x Z u=1+" du log(u)1A asymptotisch Äquivalent sind. Tschebyschew konnte die Legendresche Vermutung widerlegen; außerdem bewies er: Wenn der Grenzwert lim x!1 ¼(x) x log(x) existiert, so muss dieser gleich 1 sein. Dank wegweisender Vorarbeiten von Riemann, gelang es im Jahr 1896 unabhängig voneinander und nahezu zeitgleich Hadamard und De La Vallee Poussin, den Primzahlsatz analytisch zu beweisen. Beide verwendeten entscheidend die Tatsache, dass die Zetafunktion ³ in der Halbebene Re(s) ¸ 1 nicht verschwindet. Die Beweise waren zuerst so lang und kompliziert, dass sie heutzutage nur noch einen historischen Wert besitzen. Es dauerte weitere 84 Jahre bis der Beweis so vereinfacht werden konnte, dass er nur wenige Seiten in Anspruch nimmt. Ein wichtiger Verdienst kommt hierbei der Arbeit von Newman aus dem Jahre 1980 zu. Lange Zeit wurde es für kaum möglich gehalten, einen Beweis des Primzahlsatzes zu finden, der ohne eine gewisse Kenntnis der komplexen Nullstellen der Zetafunktion auskommt. Und doch glückte 1948 ein solcher Beweis durch Selberg und Erdös mit elementaren Mitteln. Erwähnenswert dabei, dass der Beweis noch lange nicht einfach ist. Uns schienen die analytischen Beweise durchsichtiger zu sein. Daher haben wir in dieser Arbeit auf einen elementaren Beweis verzichtet. Der analytischen Weg zum Primzahlsatz von Newman kommt einerseits mit Integration längs endlicher Wege (und der Tatsache ³(s) 6= 0 in ¾ ¸ 1) aus, umgeht also Abschätzungen bei 1; andererseits ist er frei von Sätzen der Fourier-Analysis. Beim Beweis des Primzahlsatzes von Wolke benutzt man anstelle von ³0(s) ³(s) die Funktion ³ 1 k mit großen k. Wegen des Pols bei s=1 bringt dies bei der Integration leichte Komplikationen, hat aber den Vorteil, dass außer der Nullstellen-Freiheit keine nichttriviale Abschätzung für ³ oder ³0 erforderlich ist. Dank der elementaren Äquivalenz zwischen dem Primzahlsatz und der Konvergenz von 1Pn=1 ¹(n) n brauchte Newman nur die Konvergenz von 1Pn=1 ¹(n) n zu zeigen. Dies erreichte er mit Hilfe seines Konvergenzsatzes. Die Legendresche Formel, die auf dem Sieb des Eratosthenes basiert, erlaubt die exakte Berechnung von ¼(x), wenn alle px nicht übersteigenden Primzahlen bekannt sind. Diese prinzipielle Möglichkeit zur Ermittlung von ¼(x) ist in der Praxis natürlich stark limitiert durch die mit x rasch anwachsende Anzahl der rechts in der Legendresche Formel zu berücksichtigenden Summanden. Mit verfeinerten Siebtechniken haben verschiedene Autoren zur Legendresche Formel analoge Formeln ¼(x) ersonnen, bei denen der genannte Nachteil von Legendresche Formel sukzessive reduziert wurde. Zu erwähnen sind hier vor allem Meissel, Lehmer, sowie Lagarias, Miller und Odlyzko. Aus den Graphen von R(x)¡¼(x); li(x)¡¼(x) und x log(x) ¡¼(x) für den betrachteten Bereich x · 1018 konnten wir feststellen, dass R(x); li(x) sowie x log(x) die Anzahlfunktion Pi (x) annähern, wobei R(x) die beste Approximation für Pi(x) von allen drei ist.
Considered are the classes QL (quasilinear) and NQL (nondet quasllmear) of all those problems that can be solved by deterministic (nondetermlnlsttc, respectively) Turmg machines in time O(n(log n) ~) for some k Effloent algorithms have time bounds of th~s type, it is argued. Many of the "exhausUve search" type problems such as satlsflablhty and colorabdlty are complete in NQL with respect to reductions that take O(n(log n) k) steps This lmphes that QL = NQL iff satisfiabdlty is m QL CR CATEGORIES: 5.25
Im Mittelpunkt der vorliegenden Arbeit stehen die Nullstellen der nach Bernhard Riemann benannten Riemannschen Zetafunktion ..(s). Diese Funktion kann für komplexes s mit Res > 1 durch ...(s) = 1 X n=1 1 ns (1.1.1) dargestellt werden. Für andere Werte von s ist ...(s) durch die analytische Fortsetzung der Dirichlet-Reihe in (1.1.1) gegeben. Die ...-Funktion ist in der ganzen komplexen Ebene holomorph, mit Ausnahme des Punktes s = 1, wo sie einen einfachen Pol besitzt. Diese und weitere Eigenschaften von ...(s) setzen wir in dieser Arbeit als bekannt voraus, näheres findet man beispielsweise in [Tit51] oder [Ivi85]. Bereits Euler betrachtete, beispielsweise in [Eul48, Caput XV], die Summe in (1.1.1), allerdings vor allem für ganzzahlige s ... 2. Von ihm stammt die Gleichung 1 X n=1 1 ns =.... die für alle komplexen s mit Res > 1 gültig ist. Dieser Zusammenhang zwischen der ...-Funktion und den Primzahlen war Ausgangspunkt für Riemanns einzige zahlentheoretische, aber dennoch wegweisende Arbeit \ Über die Anzahl der Primzahlen unter einer gegebenen Grösse." ([Rie59]). In dieser 1859 erschienenen Arbeit erkannte Riemann als erster die Bedeutung der Nullstellen der ...-Funktion für die Verteilung der Primzahlen. Bezüglich dieser Nullstellen sei jetzt nur so viel gesagt, daß ...(s) einfache Nullstellen an den negativen geraden Zahlen .... besitzt, und, daß alle weiteren, die sogenannten nicht-trivialen Nullstellen, im kritischen Streifen 0 < Res < 1 liegen. Diese letzteren | unendlich vielen | Nullstellen sind gerade für den Primzahlsatz, also für die Beziehung ...(x) ... li(x);
We study the approximability of the following NP-complete (in their feasibility recognition forms) number theoretic optimization problems: 1. Given n numbers a1 ; : : : ; an 2 Z, find a minimum gcd set for a1 ; : : : ; an , i.e., a subset S fa1 ; : : : ; ang with minimum cardinality satisfying gcd(S) = gcd(a1 ; : : : ; an ). 2. Given n numbers a1 ; : : : ; an 2 Z, find a 1-minimum gcd multiplier for a1 ; : : : ; an , i.e., a vector x 2 Z n with minimum max 1in jx i j satisfying P n...
Wir behandeln Kettenbruchentwicklungen in beliebiger Dimension. Wir geben einen Kettenbruchalgorithmus an, der für beliebige Dimension n simultane diophantische Approximationen berechnet, die bis auf den Faktor 2 exp (n+2)/4 optimal sind. Für einen reellen Eingabevektor x := (x1,...,X n-1, 1) berechnet der Algorithmus eine Folge ganzzahliger Vektoren ....., so daß für i =1, ...., n-1 : | q exp (k) xi -pi exp (k)| <= 2 exp (n+2)/4 sqrt (1 + xi exp 2) / q exp (1/n-1). Nach Sätzen von Dirichlet und Borel ist die Schranke optimal in dem Sinne, als daß der Exponent 1/(n-1) im allgemeinen nicht erhöht werden kann. Der Algorithmus konstruiert eine Folge von Gitterbasen des Zn, welche die Gerade x R approximieren. Für gegebenes E > 0 findet der Algorithmus entweder eine Relation zu x, das heißt einen ganzzahligen zu x orthogonalen Vektor (ungleich Null), mit euklidischer Länge kleiner oder gleich E exp -1, oder er schließt Relationen zu x mit euklidischer Länge kleiner als E exp -1 aus. Der Algorithmus führt in der Dimension n und |log E| polynomial viele arithmetische Operationen auf rellen Zahlen in exakter Arithmetik aus. Für rationale Eingaben x := (p1, ....., pn)/pn, E>0 mit p1,.....,pn Teil von Z besitzt der Algorithmus polynomiale Bitkomplexität in O........ Eine Variante dieses Algorithmus konstruiert für Eingabevektoren x einen (von x nicht notwendigerweise verschiedenen) Nahebeipunkt x' zu x und eine kurze Relation zu x'. Im Falle x<>x können wir die Existenz von Relationen kleiner als (2E)exp -1 für Punkte in einer kleinen offenen Umgebung um x' ausschließen. Wir erhalten in diesem Sinne eine stetige untere Schranke für die Länge der kürzesten Relation zu Punkten in dieser Umgebung. Die für x' berechnete Relation ist bis auf einen in der Dimension n exponentiellen Faktor kürzeste Relation für x'. Zur Implementierung des Kettenbruchalgorithmus stellen wir ein numerisch stabiles Verfahren vor und berichten über experimentelle Ergebnisse. Wir geben untere Schranken für die Approximierbarkeit kürzester Relationen in der Maximum-Norm und minimaler diophantischer Approximationen an: Unter der Annahme, daß die Klasse NP nicht in der deterministischen Zeitklasse O(n exp poly log n) enthalten ist, zeigen wir: Es existiert kein Algorithmus, der für rationale Eingabevektoren x polynomial in der Bitlänge bin(x) von x ist und die in der Maximum-Norm kürzeste Relation bis auf einen Faktor 2 exp (log 0.5 - zeta bin(x)) approximiert. Dabei ist zeta eine beliebig kleine positive Konstante. Wir übertragen dieses Resultat auf das Problem, zu gegebenen rationalen Zahlen x1,....,xn-1 und einem rationalen E > 0 gute simultane diophantische Approximationen zu finden, das heißt rationale Zahlen p1/q,...; (p n-1/)q mit möglichst kleinem Hauptnenner q zu konstruieren, so daß max 1 <=i <= n-1 |q xi - pi| <= E. Wir zeigen unter obiger Annahme, daß kein Algorithmus existiert, der für gegebene rationale Zahlen x1,........,x n-1 und natürlicher Zahl N polynomial-Zeit in der Bitlänge bin(x) von x ist und simultane diophantische Approximationen berechnet, so daß max 1 <=i <= n-1 |q xi - pi| für q gehört zu [1, N] bis auf den Faktor 2 exp (log 0.5 - zeta bin(x)) minimal ist. Hierbei ist zeta wieder eine beliebig kleine positive Konstante.
In der vorliegenden Arbeit wird ein interaktives Beweisprotokoll für das Problem der "überprüfbaren Verschlüsselung" (verifiable encyption) vorgestellt. Mit Hilfe eines Verifiable Encryption Protokolls (VEP) beweist eine Person (der Prover) einer anderen Person (dem Verifier) effizient, daß ein vorher gesendeter Wert alpha die Verschlüsselung eines geheimen Wertes s ist. Den geheimen Wert s muß er dazu nicht offenlegen. Zur Verschlüsselung von s wird ein Public-Key-Verfahren und ein öffentlicher Schlüssel PK benutzt. PK gehört zum Schlüsselpaar einer dritten Partei, die nicht aktiv an der Protokollausführung beteiligt ist und die Rolle eines Notars einnimmt. Dem Verifier steht ein Wert d zur Verfügung, anhand dessen er entscheidet, ob er den Beweis akzeptiert oder verwirft. Akzeptiert der Verifier den Beweis des Provers, so kann er zwar mit an Sicherheit grenzender Wahrscheinlichkeit sagen, daß alpha eine Verschlüsselung von s unter dem öffentlichen Schlüssel PK ist. Er kann s jedoch nicht rekonstruieren, da er nicht im Besitz des zu PK gehörigen geheimen Schlüssels SK ist und der Beweis keine Informationen über s preisgibt.
Gitter sind diskrete, additive Untergruppen des IRm, ein linear unabhängiges Erzeugendensystem eines Gitters heißt Gitterbasis. Die Anzahl der Basisvektoren eines Gitters ist eindeutig bestimmt und heißt Rang des Gitters. Zu jedem Gitter vom Rang n gibt es mehrere Gitterbasen, die man alle erhält, indem man eine Basismatrix B = [b1, · · · , bn] von rechts mit allen Matrizen aus der Gruppe GLn(ZZ) multipliziert. Eine wichtige Fragestellung der Gittertheorie ist es, zu einem gegebenen Gitter einen kürzesten, vom Nullvektor verschiedenen Gittervektor zu finden. Dieses Problem heißt das kürzeste Gittervektorproblem . Ein dazu verwandtes Problem ist das "nächste Gittervektorproblem", das zu einem beliebigen Vektor x aus IRm einen Gittervektor sucht, dessen Abstand zu x minimal ist. Aus dem "kürzesten Gittervektorproblem" entwickelte sich die Gitterbasenreduktion, deren Ziel es ist, eine gegebene Gitterbasis in eine Gitterbasis zu transformieren, deren Vektoren bzgl. der Euklidischen Norm kurz und möglichst orthogonal zueinander sind. Wichtig für die Güte einer Reduktion ist der Begriff der sukzessiven Minima ¸1(L), · · · , ¸n(L) eines Gitters L. Dabei ist ¸i(L) die kleinste reelle Zahl r > 0, für die es i linear unabhängige Vektoren cj 2 L gibt mit kcjk · r für j = 1, · · · , i. Man versucht, für ein Gitter L eine Gitterbasis b1, · · · , bn zu finden, bei der die Größe kbik / ¸i(L) für i = 1, · · · , n möglichst klein ist. Für Gitter vom Rang 2 liefert das Gauß'sche Reduktionsverfahren eine Gitterbasis mit kbik = ¸i(L) für i = 1, 2. Eine Verallgemeinerung der Gauß-Reduktion auf Gitter mit beliebigem Rang ist die im Jahre 1982 von Lenstra, Lenstra, Lovasz vorgeschlagene L3-Reduktion einer Gitterbasis, deren Laufzeit polynomiell in der Bitlänge der Eingabe ist. L3-reduzierte Gitterbasen approximieren die sukzessiven Minima bis auf einen (im Rang des Gitters) exponentiellen Faktor. Die vorliegende Arbeit besteht aus zwei Teilen. Im ersten Teil (Kapitel 1-6) wird ein neues Reduktionskonzept von M. Seysen aus der Arbeit "A Measure for the Non-Orthogonality of a Lattice Basis" behandelt und im zweiten Teil (Kapitel 7) ein aktuelles Ergebnis von M. Ajtai über die Faktorisierung ganzer Zahlen aus "The Shortest Vector Problem in L2 is NP-hard for Randomized Reductions"[2]. Seysen führte in [13] zu einer gegebenen Gitterbasis b1, · · · , bn die Größe ¾(A) ein, die nur von den Einträgen der zugehörigen Gram-Matrix A = [b1, · · · , bn]T · [b1, · · · , bn] und der Inversen A 1 abhängt. Sie hat die Eigenschaft, daß für jede Gitterbasis b1, · · · , bn mit Gram-Matrix A gilt, daß ¾(A) ¸ 1, wobei die Gleichheit genau dann gilt, wenn b1, · · · , bn orthogonal ist. Aus dieser Defintion ergibt sich folgender Reduktionsbegriff: Eine Gitterbasis b1, · · · , bn mit Gram-Matrix A heißt genau dann ¿ -reduziert, wenn ¾(A) minimal für alle Basen des Gitters ist. Der wesentliche Unterschied der ¿-Reduktion zur L3-Reduktion ist, daß die Größe ¾(A) unabhängig von der Reihenfolge der Basisvektoren ist, so daß eine ¿ -reduzierte Gitterbasis bei beliebiger Permutation der Basisvektoren ¿ -reduziert bleibt. Die ¿-Reduktion reduziert also im Gegensatz zur L3-Reduktion die Basisvektoren gleichmäßig. Seysen zeigte, daß man zu jedem Gitter vom Rang n eine Gitterbasis mit Gram-Matrix A findet, so daß ¾(A) durch eO((ln n)2) beschränkt ist. Daraus läßt sich ableiten, daß ¿ -reduzierte Gitterbasen eines Gitters vom Rang n die sukzessiven Minima bis auf den Faktor eO((ln n)2) approximieren. Da es sich bei der ¿-Reduktion um einen sehr starken Reduktionsbegriff handelt, für den es schwer ist, einen effizienten Algorithmus zu finden, definiert man folgenden schwächeren Reduktionsbegriff: b1, · · · , bn heißt genau dann ¿2-reduziert, wenn keine Basistransformation der Form bj := bj +k · bi mit 1 · i 6= j · n und k 2 ZZ die Gr¨oße ¾(A) erniedrigt. Für n = 2 entspricht die ¿-Reduktion sowohl der ¿2- Reduktion als auch der Gauß-Reduktion. Für die ¿2-Reduktion findet man einen effizienten Algorithmus. Wendet man diesen Algorithmus auf Rucksackprobleme an, so ergibt sich, daß durch einen Algorithmus, bestehend aus ¿2-Reduktion und anschließender L3-Reduktion, bei großer Dichte und bei kleiner Dimension wesentlich mehr Rucksackprobleme gelöst werden als durch den L3-Algorithmus. Die Faktorisierung großer ganzer Zahlen ist ein fundamentales Problem mit großer kryptographischer Bedeutung. Schnorr stellte in [11] erstmals einen Zusammenhang zwischen Gitterbasenreduktion und Faktorisierung her, indem er das Faktorisieren ganzer Zahlen auf das "nächste Gittervektorproblem in der Eins-Norm" zurückführte. Adleman führte in [1] das Faktorisieren ganzer Zahlen sogar auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" zurück, allerdings unter zahlentheoretischen Annahmen. In [2] stellte Ajtai ein neues Ergebnis vor, in dem er das Faktorisieren ganzer Zahlen auf das "kürzeste Gittervektorproblem in der Euklidischen Norm" ohne zusätzliche Annahmen zurückführte.
Der Begriff der editierfreundlichen Kryptographie wurde von Mihir Bellare, Oded Goldreich und Shafi Goldwasser 1994 bzw. 1995 eingeführt. Mit einem editierfreundlicher Verschlüsselungs- oder Unterschriftenverfahren kann man aus einer Verschlüsselung bzw. Unterschrift zu einer Nachricht schnell eine Verschlüsselung oder Unterschrift zu einer ähnlichen Nachricht erstellen. Wir geben eine Übersicht über die bekannten editierfreundlichen Verfahren und entwickeln sowohl ein symmetrisches als auch ein asymmetrisches editierfreundliches Unterschriftenverfahren (IncXMACC und IncHSig). Wir zeigen, wie man mit editierfreundlichen Schemata überprüfen kann, ob die Implementierung einer Datenstruktur korrekt arbeitet. Basierend auf den Ideen der editierfreundlichen Kryptographie entwickeln wir effiziente Verfahren für spezielle Datenstrukturen. Diese Ergebnisse sind in zwei Arbeiten [F97a, F97b] zusammengefaßt worden.
In der vorliegenden Diplomarbeit beschäftigen wir uns mit kryptographisch sicheren Pseudozufallsgeneratoren. Diese e±zienten Algorithmen erzeugen zu zufälliger Eingabe deterministisch eine längere Bitfolge, die praktisch von einer Folge zufälliger Münzwürfe nicht unterscheidbar ist. Wir geben die Definitionen von A. Yao sowie M. Blum und S. Micali, beweisen die Äquivalenz und charakterisieren den Unterschied zur klassischen Sichtweise von Zufallsgeneratoren. Mit der Blum-Micali-Konstruktion zeigen wir, wie man aus einer Oneway-Permutation und zugehörigem Hardcore-Prädikat einen kryptographisch sicheren Pseudozufallsgenerator konstruiert: Man wendet auf einen zufälligen Startwert iterativ die Oneway-Funktion an und gibt jeweils das Hardcore-Prädikat des Urbilds aus. Wir stellen das allgemeine Hardcore- Prädikat inneres Produkt modulo 2 von L.A. Levin und O. Goldreich vor und beweisen mit Hilfe des XOR-Lemmas von U.V. Vazirani und V.V. Vazirani die Verallgemeinerung zu einer Hardcore-Funktion, die statt eines Prädikats mehrere Bits ausgibt. Man geht davon aus, daß die Verschlüsselungsfunktionen des RSA- und des Rabin-Public- Key-Kryptosystems Oneway-Permutationen sind. Basierend auf dem Rabin-System haben L. Blum, M. Blum und M. Shub den x2-mod-N-Generator aufgebaut, W. Alexi, B. Chor, O. Goldreich und C.P. Schnorr haben den RSA-Generator konstruiert und den Sicherheitsbeweis zum x2-mod-N-Generator verbessert. Diese Generatoren basieren auf der Blum-Micali-Konstruktion mit dem Hardcore-Prädikat des untersten Bits. Durch neue Ideen können wir die beweisbare Sicherheit der Generatoren deutlich erhöhen, so daß in der Praxis kleinere Schlüssellängen genügen. Bisher war zum Beispiel für den x2-mod-N-Generator bekannt, daß man mit einem Algorithmus A, der das unterste Bit der Wurzel modulo einer n-Bit- Blumzahl mit Wahrscheinlichkeit 1 2 + ² in Zeit |A| = ¡n3¢ berechnet, den Modul in Zeit O¡n3² 9|A|¢ mit Wahrscheinlichkeit ²2 64 faktorisieren kann. Wir verbessern die Laufzeit zu O¡n² 4 log2(n² 1)|A|¢ und Wahrscheinlichkeit 1 9 . Diese neuen Resultate wurden auf der Eurocrypt-Konferenz im Mai 1997 in Konstanz vorgestellt, D.E. Knuth hat sie bereits in die neue Auflage seines Standardwerks The Art of Computer Programming aufgenommen.