Mathematik
Refine
Year of publication
Document Type
- Doctoral Thesis (76) (remove)
Has Fulltext
- yes (76)
Is part of the Bibliography
- no (76)
Keywords
Institute
- Mathematik (76)
- Informatik (3)
During my initial days here in Frankfurt, in October 2020 amidst the pandemic crisis, all my notes revolved around three articles by Bolthausen and Kistler, which now form the starting point of this work.
The ones introduced by Bolthausen and Kistler are abstract mean field spin glass models, reminiscent of Derrida’s Generalized Random Energy Model (GREM), which generalize the GREM while remaining rigorously solvable through large deviations methods and within a classical Boltzmann-Gibbs formalism. This allows to establish, by means of a second moment method, the associated free energy at the thermodynamic limit as an orthodox, infinite-dimensional, Boltzmann-Gibbs variational principle.
Dual Parisi formulas for the limiting free energy associated with these Hamiltonians hold, and are revealed to be the finite-dimensional (”collapsed”) versions of the classical, infinite-dimensional Boltzmann-Gibbs principles.
In the 2nd chapter of this thesis, we uncover the hidden yet essential connection between real-world spin glasses, like the Sherrington-Kirkpatrick (SK) model and the random energy models. The crucial missing element is that of TAP-free energies: integrating it with the framework introduced by Bolthausen and Kistler results in a correction to the Parisi formula for the free energy, which brings it much, much closer to the ”true” Parisi solution for the SK-model. In other words, we can identify the principles that transform the classical Boltzmann-Gibbs maximization into the unorthodox (and puzzling) Parisi minimization.
This arguably stands as the primary achievement of this work.
Komplexität und Zufälligkeit
(1978)
In this thesis, the focus is on the actions of primary school children using digital and analogue materials in comparable mathematical situations. To emphasise actions on different materials in the mathematical learning process, a semiotic perspective according to C. S. Peirce (CP 1931-35) on mathematics learning is adopted. This theoretical research perspective highlights the activity itself on diagrams as a mathematical activity and brings actions to the forefront of interest. The actions on comparable digital and analogue diagrams are the basis for the reconstruction of mathematical interpretations of learners in 3rd and 4th grade.
The research questions investigate to what extent possible differences between the reconstructed interpretations of the learners can be attributed to the different materials and what influence the material has on the mathematical relationships that the learners take into account in their actions to manipulate the diagram.
For the reconstruction of the diagram interpretations based on the learners' actions on the material, a semiotic specification of Vogel's (2017) adaptation of Mayring's (2014) context analysis is used. This specification is based on Peirce's triadic theory of signs (Billion, 2023). The reconstructed interpretations of the analogue and digital diagrams are compared in a second step to identify possible differences and similarities.
The results of the qualitative analyses show, among other things, that despite the different actions of the learners on the digital and analogue diagrams, it is possible to reconstruct the same diagram interpretations if the learners establish the same mathematical relationships between the parts of the diagrams in their actions. There are also passages in the analyses where the same diagram interpretations cannot be reconstructed based on the actions on the digital and analogue materials. If the digital material acts as a tool and automatically creates several relationships between the parts of the diagram triggered by an action, then the reconstruction of the learners' diagram interpretations based on the analysis of their actions is partially possible. If the tool automatically establishes relationships, these must then be interpreted by the learners using gestures and phonetic utterances to understand the newly created diagram. Thus, a tool changes how mathematical relationships are expressed, because learners no longer have to interpret the relationships before their actions to manipulate the diagram itself, but afterwards through gestures and phonetic utterances. Regarding diagrammatic reasoning according to Peirce (NEM IV), this means that with analogue material the focus is on the construction and manipulation of diagrams through rule-guided actions, whereas with digital material, which functions as a tool, there is more emphasis on observing the results of the manipulations on the diagram.
At the end of the thesis, a recommendation for teachers on how to design mathematics lessons for primary school children using digital and analogue materials will be derived from the results.
The literature cited in this summary can be found in the references of the presented thesis.
Interactional niche in the development of geometrical and spatial thinking in the familial context
(2016)
In the analysis of mathematics education in early childhood it is necessary to consider the familial context, which has a significant influence on development in early childhood. Many reputable international research studies emphasize that the more children experience mathematical situations in their families, the more different emerging forms of participation occur for the children that enable them to learn mathematics in the early years. In this sense mathematical activities in the familial context are cornerstones of children’s mathematical development, which is also affected by the ethnic, cultural, educational and linguistic features of their families. Germany has a population of approximately 82 million, about 7.2 million of whom are immigrants (Statisches Bundesamt 2009, pp.28-32). Children in immigrant families grow up with multiculturalism and multilingualism, therefore these children are categorized as a risk group in Germany. “Early Steps in Mathematics Learning – Family Study” (erStMaL-FaSt) is the one of the first familial studies in Germany to deal with the impact of familial socialization on mathematics learning. The study enables us to observe children from different ethnic groups with their family members in different mathematical play situations. The family study (erStMaL-FaSt) is empirically performed within the framework of the erStMaL (Early Steps in Mathematics Learning) project, which relates to the investigation of longitudinal mathematical cognitive development in preschool and early primary-school ages from a socio-constructivist perspective. This study uses two selected mathematical domains, Geometry and Measurement, and four play situations within these two mathematical domains.
My PhD study is situated in erStMaL-FaSt. Therefore, in the beginning of this first chapter, I briefly touch upon IDeA Centre and the erStMaL project and then elaborate on erStMaL-FaSt. As parts of my research concepts, I specify two themes of erStMaL-FaSt: family and play. Thereafter I elaborate upon my research interest. The aim of my study is the research and development of theoretical insights in the functioning of familial interactions for the formation of geometrical (spatial) thinking and learning of children of Turkish ethnic background. Therefore, still in Chapter 1, I present some background on the Turkish people who live in Germany and the spatial development of the children.
This study is designed as a longitudinal study and constructed from interactionist and socio-constructivist perspectives. From a socio-constructivist perspective the cognitive development of an individual is constitutively bound to the participation of this individual in a variety of social interactions. In this regard the presence of each family member provides the child with some “learning opportunities” that are embedded in the interactive process of negotiation of meaning about mathematical play. During the interaction of such various mathematical learning situations, there occur different emerging forms of participation and support. For the purpose of analysing the spatial development of a child in interaction processes in play situations with family members, various statuses of participation are constructed and theoretically described in terms of the concept of the “interactional niche in the development of mathematical thinking in the familial context” (NMT-Family) (Acar & Krummheuer, 2011), which is adapted to the special needs of familial interaction processes. The concept of the “interactional niche in the development of mathematical thinking” (NMT) consists of the “learning offerings” provided by a group or society, which are specific to their culture and are categorized as aspects of “allocation”, and of the situationally emerging performance occurring in the process of meaning negotiation, both of which are subsumed under the aspect of the “situation”, and of the individual contribution of the particular child, which constitutes the aspect of “child’s contribution” (Krummheuer 2011a, 2011b, 2012, 2014; Krummheuer & Schütte 2014). Thereby NMT-Family is constructed as a subconcept of NMT, which offers the advantage of closer analyses and comparisons between familial mathematical learning occasions in early childhood and primary school ages.
Within the scope of NMT-Family, a “mathematics learning support system” (MLSS) is an interactional system which may emerge between the child and the family members in the course of the interaction process of concrete situations in play (Krummheuer & Acar Bayraktar, 2011). All these topics are addressed in Chapter 2 as theoretical approaches and in Chapter 3 as the research method of this study. In Chapter 4 the data collection and analysis is clarified in respect of these approaches...
Aus Sicht der Pädagogischen Psychologie ist Lernen ein Prozess, bei dem es zu überdauernden Änderungen im Verhaltenspotenzial als Folge von Erfahrungen kommt. Aus konstruktivistischer Perspektive lässt sich Lernen am besten als eine individuelle Konstruktion von Wissen infolge des Entdeckens, Transformierens und Interpretierens komplexer Informationen durch den Lernenden selbst beschreiben. Erkennt der Lernende den Sinn und übernimmt, erweitert oder verändert ihn für sich selbst, so ist der Grundstein für nachhaltiges Lernen gelegt.
Lernen ist ein sehr individueller Prozess. Schule muss also individuelles Lernen auch im Klassenverband ermöglichen und der Lehrende muss zum Lerncoach werden, da sonst kein individuelles und eigenaktives Lernen möglich ist. Das Unterrichtskonzept des forschend-entdeckenden Lernens bietet genau diese Möglichkeit. Es erlaubt die Erfüllung der drei Grundbedürfnisse eines Menschen nach Kompetenz, Autonomie und sozialer Eingebundenheit und ermöglicht damit Motivation, Leistung und Wohlbefinden (Ryan & Deci, 2004).
Forschend-entdeckendes Lernen im Mathematikunterricht ist schrittweise geprägt von folgenden Merkmalen:
- eine problemorientierte Organisation
- selbstständiges, eigenaktives und eigenverantwortliches Lernen der Schülerinnen und Schüler
- individuelle Lernwege und Lernprozesse
- Entwicklung eigener Fragestellungen und Vorgehensweisen der Lernenden
- eigenes Aufstellen von Hypothesen und Vermutungen; Überprüfung der Vermutungen; Dokumentation, Interpretation und Präsentation der Ergebnisse
- eine fördernde Atmosphäre, in der die Lernenden nach und nach forschende Arbeitstechniken vermitteln bekommen
- kooperative Lernformen und damit Förderung von Team- und Kommunikationsfähigkeit
- Unterrichtsinhalte mit hohem Realitäts- und Sinnbezug, gesellschaftlicher Relevanz, Möglichkeiten der Interdisziplinarität
- Stetige Angebote der Unterstützung
Das entdeckende Lernen kann als Vorstufe des forschenden Lernens gesehen werden, da hier der wissenschaftliche Fokus noch nicht so stark ausgeprägt ist. Um alle Phasen auf dem Weg zu annähernd wissenschaftlichen forschenden Lernens anzusprechen, verwenden wir den Begriff des forschend-entdeckenden Lernens.
Voraussetzung ist, dass die Lehrkräfte das forschende Lernen als aktiven, produktiven und selbstbestimmten Lernprozess selbst zuvor erlebt haben müssen. Unter anderem können die Lehrkräfte Unterrichtsprozesse danach besser planen und währenddessen unterstützen, da sie selbst forschend-entdeckendem Lernen „ausgesetzt“ waren und vergleichbare Prozesse durchlebt haben.
Hiermit wird deutlich, dass forschendes Lernen nicht bedeuten kann, dass die Schülerinnen und Schüler auf sich gestellt sind. Die gezielte Unterstützung der Lernenden beim Entdecken und Forschen durch die Lehrkraft ist für einen ertragreichen Lernerfolg unverzichtbar und muss Teil der Vorbereitung und des Prozesses sein.
Internationale Studien zeigen, dass forschend-entdeckende Unterrichtsansätze (inquiry-based learning IBL) im Mathematikunterricht bei geeigneter Umsetzung Lernen verbessern, Lernerfolg und Lernleistung steigern und Freude gegenüber Mathematikunterricht erhöhen können. Die Implementierung dieses Unterrichtsansatzes ist trotz der positiven Ergebnisse nicht alltäglich.
Um neue Unterrichtskonzepte in den Schulalltag zu bringen beziehungsweise um bestehende Unterrichtskonzepte neu in den Schulalltag zu bringen bedarf es Fortbildungen zur Professionalisierung von Lehrerinnen und Lehrern.
Although everyone is familiar with using algorithms on a daily basis, formulating, understanding and analysing them rigorously has been (and will remain) a challenging task for decades. Therefore, one way of making steps towards their understanding is the formulation of models that are portraying reality, but also remain easy to analyse. In this thesis we take a step towards this way by analyzing one particular problem, the so-called group testing problem. R. Dorfman introduced the problem in 1943. We assume a large population and in this population we find a infected group of individuals. Instead of testing everybody individually, we can test group (for instance by mixing blood samples). In this thesis we look for the minimum number of tests needed such that we can say something meaningful about the infection status. Furthermore we assume various versions of this problem to analyze at what point and why this problem is hard, easy or impossible to solve.
The problem of unconstrained or constrained optimization occurs in many branches of mathematics and various fields of application. It is, however, an NP-hard problem in general. In this thesis, we examine an approximation approach based on the class of SAGE exponentials, which are nonnegative exponential sums. We examine this SAGE-cone, its geometry, and generalizations. The thesis consists of three main parts:
1. In the first part, we focus purely on the cone of sums of globally nonnegative exponential sums with at most one negative term, the SAGE-cone. We ex- amine the duality theory, extreme rays of the cone, and provide two efficient optimization approaches over the SAGE-cone and its dual.
2. In the second part, we introduce and study the so-called S-cone, which pro- vides a uniform framework for SAGE exponentials and SONC polynomials. In particular, we focus on second-order representations of the S-cone and its dual using extremality results from the first part.
3. In the third and last part of this thesis, we turn towards examining the con- ditional SAGE-cone. We develop a notion of sublinear circuits leading to new duality results and a partial characterization of extremality. In the case of poly- hedral constraint sets, this examination is simplified and allows us to classify sublinear circuits and extremality for some cases completely. For constraint sets with certain conditions such as sets with symmetries, conic, or polyhedral sets, various optimization and representation results from the unconstrained setting can be applied to the constrained case.
We provide extensions of the dual variational method for the nonlinear Helmholtz equation from Evéquoz and Weth. In particular we prove the existence of dual ground state solutions in the Sobolev critical case, extend the dual method beyond the standard Stein Tomas and Kenig Ruiz Sogge range and generalize the method for sign changing nonlinearities.
We study continuous dually epi-translation invariant valuations on certain cones of convex functions containing the space of finite-valued convex functions. Using the homogeneous decomposition of this space, we associate a certain distribution to any homogeneous valuation similar to the Goodey-Weil embedding for translation invariant valuations on convex bodies. The support of these distributions induces a corresponding notion of support for the underlying valuations, which imposes certain restrictions on these functionals, and we study the relation between the support of a valuation and its domain. This gives a partial answer to the question which dually epi-translation invariant valuations on finite-valued convex functions can be extended to larger cones of convex functions.
We also study topological properties of spaces of valuations with support contained in a fixed compact set. As an application of these results, we introduce the class of smooth valuations on convex functions and show that the subspace of smooth dually epi-translation invariant valuations is dense in the space of continuous dually epi-translation invariant valuation on finite-valued convex functions. These smooth valuations are given by integrating certain smooth differential forms over the graph of the differential of a convex function. We use this construction to give a characterization of a dense subspace of all continuous valuations on finite-valued convex functions that are rotation invariant as well as dually epi-translation invariant.
Using results from Alesker's theory of smooth valuations on convex bodies, we also show that any smooth valuation can be written as a convergent sum of mixed Hessian valuations. In particular, mixed Hessian valuations span a dense subspace, which is a version of McMullen’s conjecture for valuations on convex functions.
Strong convergence rates for numerical approximations of stochastic partial differential equations
(2018)
In this thesis and in the research articles which this thesis consists of, respectively, we focus on strong convergence rates for numerical approximations of stochastic partial differential equations (SPDEs). In Part I of this thesis, i.e., Chapter 2 and Chapter 3, we study higher order numerical schemes for SPDEs with multiplicative trace class noise based on suitable Taylor expansions of the Lipschitz continuous coefficients of the SPDEs under consideration. More precisely, Chapter 2 proves strong convergence rates for a linear implicit Euler-Milstein scheme for SPDEs and is based on an unpublished manuscript written by the author of this thesis. This chapter extends an earlier result1 by slightly lowering the assumptions posed on the diffusion coefficient and a different approximation of the semigroup. In Chapter 3 we introduce an exponential Wagner-Platen type numerical scheme for SPDEs and prove that this numerical approximation method converges in the strong sense with oder up to 3/2−. Moreover, we illustrate how the (mixed) iterated stochastic-deterministic integrals, that are part of our numerical scheme, can be simulated exactly under suitable assumptions.
The second part of this thesis, i.e. Chapter 4 and Chapter 5, is devoted to strong convergence rates for numerical approximations of SPDEs with superlinearly growing nonlinearities driven by additive space-time white noise. More specifically, in Chapter 4, we prove strong convergence with rate in the time variable for a class of nonlinearity-truncated numerical approximation schemes for SPDEs and provide examples that fit into our abstract setting like stochastic Allen-Cahn equations. Finally, in Chapter 5, we extend this result with spatial approximations and establish strong convergence rates for a class of full-discrete nonlinearity truncated numerical approximation schemes for SPDEs. Moreover, we apply our strong convergence result to stochastic Allen-Cahn equations and provide lower and upper bounds which show that our strong convergence result can, in general, not essentially be improved.
We study exchangeable coalescent trees and the evolving genealogical trees in models for neutral haploid populations.
We show that every exchangeable infinite coalescent tree can be obtained as the genealogical tree of iid samples from a random marked metric measure space when the marks are added to the metric distances. We apply this representation to generalize the tree-valued Fleming-Viot process to include the case with dust in which the genealogical trees have isolated leaves.
Using the Donnelly-Kurtz lookdown approach, we describe all individuals ever alive in the population model by a random complete and separable metric space, the lookdown space, which we endow with a family of sampling measures. This yields a pathwise construction of tree-valued Fleming-Viot processes. In the case of coming down from infinity, we also read off a process whose state space is endowed with the Gromov-Hausdorff-Prohorov topology. This process has additional jumps at the extinction times of parts of the population.
In the case with only binary reproduction events, we construct the lookdown space also from the Aldous continuum random tree by removing the root and the highest leaf, and by deforming the metric in a way that corresponds to the time change that relates the Fleming-Viot process with a Dawson-Watanabe process. The sampling measures on the lookdown space are then image measures of the normalized local time measures.
We also show invariance principles for Markov chains that describe the evolving genealogy in Cannings models. For such Markov chains with values in the space of distance matrix distributions, we show convergence to tree-valued Fleming-Viot processes under the conditions of Möhle and Sagitov for the convergence of the genealogy at a fixed time to a coalescent with simultaneous multiple mergers. For the convergence of Markov chains with values in the space of marked metric measure spaces, an additional assumption is needed in the case with dust.
Random constraint satisfaction problems have been on the agenda of various sciences such as discrete mathematics, computer science, statistical physics and a whole series of additional areas of application since the 1990s at least. The objective is to find a state of a system, for instance an assignment of a set of variables, satisfying a bunch of constraints. To understand the computational hardness as well as the underlying random discrete structures of these problems analytically and to develop efficient algorithms that find optimal solutions has triggered a huge amount of work on random constraint satisfaction problems up to this day. Referring to this context in this thesis we present three results for two random constraint satisfaction problems. ...
The condensation phase transition and the number of solutions in random graph and hypergraph models
(2016)
This PhD thesis deals with two different types of questions on random graph and random hypergraph structures.
One part is about the proof of the existence and the determination of the location of the condensation phase transition. This transition will be investigated for large values of $k$ in the problem of $k$-colouring random graphs and in the problem of 2-colouring random $k$-uniform hypergraphs, where in the latter case we investigate a more general model with finite inverse temperature.
The other part deals with establishing the limiting distribution of the number of solutions in these structures in density regimes below the condensation threshold.
Algorithms for the Maximum Cardinality Matching Problem which greedily add edges to the solution enjoy great popularity. We systematically study strengths and limitations of such algorithms, in particular of those which consider node degree information to select the next edge. Concentrating on nodes of small degree is a promising approach: it was shown, experimentally and analytically, that very good approximate solutions are obtained for restricted classes of random graphs. Results achieved under these idealized conditions, however, remained unsupported by statements which depend on less optimistic assumptions.
The KarpSipser algorithm and 1-2-Greedy, which is a simplified variant of the well-known MinGreedy algorithm, proceed as follows. In each step, if a node of degree one (resp. at most two) exists, then an edge incident with a minimum degree node is picked, otherwise an arbitrary edge is added to the solution.
We analyze the approximation ratio of both algorithms on graphs of degree at most D. Families of graphs are known for which the expected approximation ratio converges to 1/2 as D grows to infinity, even if randomization against the worst case is used. If randomization is not allowed, then we show the following convergence to 1/2: the 1-2-Greedy algorithm achieves approximation ratio (D-1)/(2D-3); if the graph is bipartite, then the more restricted KarpSipser algorithm achieves the even stronger factor D/(2D-2). These guarantees set both algorithms apart from other famous matching heuristics like e.g. Greedy or MRG: these algorithms depend on randomization to break the 1/2-barrier even for paths with D=2. Moreover, for any D our guarantees are strictly larger than the best known bounds on the expected performance of the randomized variants of Greedy and MRG.
To investigate whether KarpSipser or 1-2-Greedy can be refined to achieve better performance, or be simplified without loss of approximation quality, we systematically study entire classes of deterministic greedy-like algorithms for matching. Therefore we employ the adaptive priority algorithm framework by Borodin, Nielsen, and Rackoff: in each round, an adaptive priority algorithm requests one or more edges by formulating their properties---like e.g. "is incident with a node of minimum degree"---and adds the received edges to the solution. No constraints on time and space usage are imposed, hence an adaptive priority algorithm is restricted only by its nature of picking edges in a greedy-like fashion. If an adaptive priority algorithm requests edges by processing degree information, then we show that it does not surpass the performance of KarpSipser: our D/(2D-2)-guarantee for bipartite graphs is tight and KarpSipser is optimal among all such "degree-sensitive" algorithms even though it uses degree information merely to detect degree-1 nodes. Moreover, we show that if degrees of both nodes of an edge may be processed, like e.g. the Double-MinGreedy algorithm does, then the performance of KarpSipser can only be increased marginally, if at all. Of special interest is the capability of requesting edges not only by specifying the degree of a node but additionally its set of neighbors. This enables an adaptive priority algorithm to "traverse" the input graph. We show that on general degree-bounded graphs no such algorithm can beat factor (D-1)/(2D-3). Hence our bound for 1-2-Greedy is tight and this algorithm performs optimally even though it ignores neighbor information. Furthermore, we show that an adaptive priority algorithm deteriorates to approximation ratio exactly 1/2 if it does not request small degree nodes. This tremendous decline of approximation quality happens for graphs on which 1-2-Greedy and KarpSipser perform optimally, namely paths with D=2. Consequently, requesting small degree nodes is vital to beat factor 1/2.
Summarizing, our results show that 1-2-Greedy and KarpSipser stand out from known and hypothetical algorithms as an intriguing combination of both approximation quality and conceptual simplicity.
Die letzten Jahrzehnte brachten einen enormen Zuwachs des Wissens und Verständnisses über die molekularen Prozesse des Lebens.Möglich wurde dieser Zuwachs durch die Entwicklung diverser Methoden, mit denen beispielsweise gezielt die Konzentration einzelner Stoffe gemessen werden kann oder gar alle anwesenden Metaboliten eines biologischen Systems erfasst werden können. Die großflächige Anwendung dieser Methoden führte zur Ansammlung vieler unterschiedlicher -om-Daten, wie zum Beispiel Metabolom-, Proteom- oder Transkriptoms-Datensätzen. Die Systembiologie greift auf solche Daten zurück, um mathematische Modelle biologischer Systeme zu erstellen, und ermöglicht so ein Studium biologischer Systeme auch außerhalb des Labors.
Für größere biologische Systeme stehen jedoch meistens nicht alle Informationen über Stoffkonzentrationen oder Reaktionsgeschwindigkeiten zur Verfügung, um eine quantitative Modellierung, also die Beschreibung von Änderungsraten kontinuierlicher Variablen, durchführen zu können. In einem solchen Fall wird auf Methoden der qualitativen Modellierung zurückgegriffen. Eine dieser Methoden sind die Petrinetze (PN), welche in den 1960er Jahren von Carl Adam Petri entwickelt wurden, um nebenläufige Prozesse im technischen Umfeld zu beschreiben. Seit Anfang der 1990er Jahre finden PN auch Anwendung in der Systembiologie, um zum Beispiel metabolische Systeme oder Signaltransduktionswege zu modellieren. Einer der Vorteile dieser Methode ist zudem, dass Modelle als qualitative Beschreibung des Systems begonnen werden können und im Laufe der Zeit um quantitative Beschreibungen ergänzt werden können.
Zur Modellierung und Analyse von PN existieren bereits viele Anwendungen. Da das Konzept der PN jedoch ursprünglich nicht für die Systembiologie entwickelt wurde und meist im technischen Bereich verwendet wird, existierten kaum Anwendungen, die für den Einsatz in der Systembiologie entwickelt wurden. Daher ist auch die Durchführung der für die Systembiologie entwickelten Analysemethoden für PN nicht mit diesen Anwendungen möglich. Die Motivation des ersten Teiles dieser Arbeit war daher, eine Anwendung zu schaffen, die speziell für die PN-Modellierung und Analyse in der Systembiologie gedacht ist, also in ihren Analysemethoden und ihrer Terminologie sich an den Bedürfnissen der Systembiologie orientiert. Zudem sollte die Anwendung den Anwender bei der Auswertung der Resultate der Analysemethoden visuell unterstützen, indem diese direkt visuell im Kontext des PN gesetzt werden. Da bei komplexeren PN die Resultate der Analysemethoden in ihrer Zahl drastisch anwachsen, wird eine solche Auswertung dieser notwendig. Aus dieser Motivation heraus entstand die Anwendung MonaLisa, dessen Implementierung und Funktionen im ersten Teil der vorliegenden Arbeit beschrieben werden. Neben den klassischen Analysemethoden für PN, wie den Transitions- und Platz-Invarianten, mit denen grundlegende funktionale Module innerhalb eines PN gefunden werden können, wurden weitere, meist durch die Systembiologie entwickelte, Analysemethoden implementiert. Dazu zählen zum Beispiel die Minimal Cut Sets, die Maximal Common Transitions Sets oder Knock-out-Analysen. Mit MonaLisa ist aber auch die Simulation des dynamischen Verhaltens des modellierten biologischen Systems möglich. Hierzu stehen sowohl deterministische als auch stochastische Verfahren, beispielsweise der Algorithmus von Gillespie zur Simulation chemischer Systeme, zur Verfügung. Für alle zur Verfügung gestellten Analysemethoden wird ebenfalls eine visuelle Repräsentation ihrer Resultate bereitgestellt. Im Falle der Invarianten werden deren Elemente beispielsweise in der Visualisierung des PN eingefärbt. Die Resultate der Simulationen oder der topologischen Analyse können durch verschiedene Graphen ausgewertet werden. Um eine Schnittstelle zu anderen Anwendungen zu schaffen, wurde für MonaLisa eine Unterstützung einiger gängiger Dateiformate der Systembiologie geschaffen, so z.B. für SBML und KGML.
Der zweite Teil der Arbeit beschäftigt sich mit der topologischen Analyse eines Datensatzes von 2641 Gesamtgenom Modellen aus der path2models-Datenbank. Diese Modelle wurden automatisiert aus dem vorhandenen Wissen der KEGG- und der MetaCyc-Datenbank erstellt. Die Analyse der topologischen Eigenschaften eines Graphen ermöglicht es, grundlegende Aussagen über die globalen Eigenschaften des modellierten Systems und dessen Entstehungsprozesses zu treffen. Daher ist eine solche Analyse oft der erste Schritt für das Verständnis eines komplexen biologischen Systems. Für die Analyse der Knotengrade aller Reaktionen und Metaboliten dieser Modelle wurden sie in einem ersten Schritt in PN transformiert. Die topologischen Eigenschaften von metabolischen Systemen werden in der Literatur schon sehr gut beschrieben, wobei die Untersuchungen meist auf einem Netzwerk der Metaboliten oder der Reaktionen basieren. Durch die Verwendung von PN wird es möglich, die topologischen Eigenschaften von Metaboliten und Reaktionen in einem gemeinsamen Netzwerk zu untersuchen. Die Motivation hinter diesen Untersuchungen war, zu überprüfen, ob die schon beschriebenen Eigenschaften auch für eine Darstellung als PN zutreffen und welche neuen Eigenschaften gefunden werden können. Untersucht wurden der Knotengrad und der Clusterkoeffizient der Modelle. Es wird gezeigt, dass einige wenige Metaboliten mit sehr hohem Knotengrad für eine ganze Reihe von Effekten verantwortlich sind, wie beispielsweise dass die Verteilung des Knotengrades und des Clusterkoeffizienten, im Bezug auf Metaboliten, skalenfrei sind und dass sie für die Vernetzung der Nachbarschaft von Reaktionen verantwortlich sind. Weiter wird gezeigt, dass die Größe eines Modelles Einfluss auf dessen topologische Eigenschaften hat. So steigt die Vernetzung der Nachbarschaft eines Metaboliten, je mehr Metaboliten in einem biologischen System vorhanden sind, gleiches gilt für den durchschnittlichen Knotengrad der Metaboliten.
Given an Abelian semi-group (A, +), an A-valued curvature measure is a valuation with values in A-valued measures. If A = R, complete classifications of Hausdorff-continuous translation-invariant SO(n)-invariant valuations and curvature measures were obtained by Hadwiger and Schneider, respectively. More recently, characterisation results have been achieved for curvature measures with values in A = Sym^p R^n and A = Sym^2 Λ^q R^n for p, q ≥ 1 with varying assumptions as for their invariance properties.
In the present work, we classify all smooth translation-invariant SO(n)-covariant curvature measures with values in any SO(n)-representation in terms of certain differential forms on the sphere bundle S R^n and describe their behaviour under the globalisation map. The latter result also yields a similar classification of all continuous SO(n)-module-valued SO(n)-covariant valuations. Furthermore, a decomposition of the space of smooth translation-
invariant scalar-valued curvature measures as an SO(n)-module is obtained. As a corollary, we construct explicit bases of continuous translation-invariant scalar-valued valuations and smooth translation-invariant scalar-valued curvature measures.
Die Populationsgenetik beschäftigt sich mit dem Einfluss von zufälliger Reproduktion, Rekombination, Migration, Mutation und Selektion auf die genetische Struktur einer Population.
In dieser Arbeit mit dem englischen Titel "Ancestral lines under mutation and selection" wird das Zusammenspiel von zufälliger Reproduktion, gerichteter Selektion und Zweiwegmutation untersucht.
Dazu betrachten wir eine haploide Population in der jedes Individuum zu jedem Zeitpunkt genau einen von zwei Typen aus S:={0,1} trägt. Dabei sei 1 der neutrale und 0 der selektiv bevorzugte Typ. Im Diffusionslimes sehr großer Populationen modellieren wir den Prozess der Frequenz der Typ-0-Individuen durch eine Wright-Fisher-Diffusion X:=(X_t) mit Mutation und gerichteter Selektion.
Zu jedem Zeitpunkt s gibt es genau ein Individuum, dessen Nachkommen ab einem bestimmten zukünftigen Zeitpunkt t>s die gesamte Population ausmachen werden. Wir nennen dieses Individuum den gemeinsamen Vorfahren zum Zeitpunkt s, da alle Individuen zu allen Zeitpunkten r>t von ihm abstammen. Sei R_{s} dessen Typ zum Zeitpunkt s. Wir nehmen an, dass der Prozess X zum Zeitpunkt 0 im Gleichgewicht ist und definieren die Wahrscheinlichkeit, dass der gemeinsame Vorfahre zum Zeitpunkt 0 Typ 0 hat, durch h(x):= P(R_{0}=0|X_{0}=x). Eine Darstellung von h(x) wurde bereits von Fearnhead (2002) und Taylor (2007) gefunden und dort mit vorwiegend analytischen Methoden bewiesen. In dieser Arbeit entwickeln wir in Kapitel 3 ein neues Teilchenbild, den pruned lookdown ancestral selection graph (pruned LD-ASG), der für sich selbst genommen interessant ist und eine neue probabilistische Interpretation der Darstellung von h(x) liefert.
Durch Erweiterung des Teilchenbildes auf Nachkommenverteilungen mit schweren Tails und mit Hilfe einer Siegmund Dualität gelingt es uns in Kapitel 4 das Resultat für h(x) von klassischen Wright-Fisher-Diffusionen auf Lambda-Wright-Fisher-Diffuison zu erweitern.
Eine Verbindung zwischen Ideen von Taylor (2007), der den gemeinsamen Prozess (X,R) untersucht hat, und einem von Fearnhead (2002) betrachteten Prozess (R,V), der die Entwicklung des Typs R des gemeinsamen Vorfahren in einer Umgebung von V sogenannten virtuellen Linien beschreibt, stellen wir in Kapitel 6 her. Wir bestimmen die gemeinsame Dynamik des Tripels (X,R,V). In Kapitel 7 betrachten wir ein diskretes Bild mit endlicher Populationsgröße N und schlagen dort eine Brücke zu Resultaten von Kluth, Hustedt und Baake (2013).
Des Weiteren entwickeln wir in Kapitel 5 dieser Arbeit einen Algorithmus zur Simulation der Typen einer Stichprobe von m Individuen, die aus einer Wright-Fisher-Population mit Mutation und Selektion im Gleichgewicht gezogen wird. Mittels dieses Algorithmus illustrieren wir die Typenverteilung für verschiedene Parameterwerte und Stichprobengrößen.
The behaviour of electronic circuits is influenced by ageing effects. Modelling the behaviour of circuits is a standard approach for the design of faster, smaller, more reliable and more robust systems. In this thesis, we propose a formalization of robustness that is derived from a failure model, which is based purely on the behavioural specification of a system. For a given specification, simulation can reveal if a system does not comply with a specification, and thus provide a failure model. Ageing usually works against the specified properties, and ageing models can be incorporated to quantify the impact on specification violations, failures and robustness. We study ageing effects in the context of analogue circuits. Here, models must factor in infinitely many circuit states. Ageing effects have a cause and an impact that require models. On both these ends, the circuit state is highly relevant, an must be factored in. For example, static empirical models for ageing effects are not valid in many cases, because the assumed operating states do not agree with the circuit simulation results. This thesis identifies essential properties of ageing effects and we argue that they need to be taken into account for modelling the interrelation of cause and impact. These properties include frequency dependence, monotonicity, memory and relaxation mechanisms as well as control by arbitrary shaped stress levels. Starting from decay processes, we define a class of ageing models that fits these requirements well while remaining arithmetically accessible by means of a simple structure.
Modeling ageing effects in semiconductor circuits becomes more relevant with higher integration and smaller structure sizes. With respect to miniaturization, digital systems are ahead of analogue systems, and similarly ageing models predominantly focus on digital applications. In the digital domain, the signal levels are either on or off or switching in between. Given an ageing model as a physical effect bound to signal levels, ageing models for components and whole systems can be inferred by means of average operation modes and cycle counts. Functional and faithful ageing effect models for analogue components often require a more fine-grained characterization for physical processes. Here, signal levels can take arbitrary values, to begin with. Such fine-grained, physically inspired ageing models do not scale for larger applications and are hard to simulate in reasonable time. To close the gap between physical processes and system level ageing simulation, we propose a data based modelling strategy, according to which measurement data is turned into ageing models for analogue applications. Ageing data is a set of pairs of stress patterns and the corresponding parameter deviations. Assuming additional properties, such as monotonicity or frequency independence, learning algorithm can find a complete model that is consistent with the data set. These ageing effect models decompose into a controlling stress level, an ageing process, and a parameter that depends on the state of this process. Using this representation, we are able to embed a wide range of ageing effects into behavioural models for circuit components. Based on the developed modelling techniques, we introduce a novel model for the BTI effect, an ageing effect that permits relaxation. In the following, a transistor level ageing model for BTI that targets analogue circuits is proposed. Similarly, we demonstrate how ageing data from analogue transistor level circuit models lift to purely behavioural block models. With this, we are the first to present a data based hierarchical ageing modeling scheme. An ageing simulator for circuits or system level models computes long term transients, solutions of a differential equation. Long term transients are often close to quasi-periodic, in some sense repetitive. If the evaluation of ageing models under quasi-periodic conditions can be done efficiently, long term simulation becomes practical. We describe an adaptive two-time simulation algorithm that basically skips periods during simulation, advancing faster on a second time axis. The bottleneck of two-time simulation is the extrapolation through skipped frames. This involves both the evaluation of the ageing models and the consistency of the boundary conditions. We propose a simulator that computes long term transients exploiting the structure of the proposed ageing models. These models permit extrapolation of the ageing state by means of a locally equivalent stress, a sort of average stress level. This level can be computed efficiently and also gives rise to a dynamic step control mechanism. Ageing simulation has a wide range of applications. This thesis vastly improves the applicability of ageing simulation for analogue circuits in terms of modelling and efficiency. An ageing effect model that is a part of a circuit component model accounts for parametric drift that is directly related to the operation mode. For example asymmetric load on a comparator or power-stage may lead to offset drift, which is not an empiric effect. Monitor circuits can report such effects during operation, when they become significant. Simulating the behaviour of these monitors is important during their development. Ageing effects can be compensated using redundant parts, and annealing can revert broken components to functional. We show that such mechanisms can be simulated in place using our models and algorithms. The aim of automatized circuit synthesis is to create a circuit that implements a specification for a certain use case. Ageing simulation can identify candidates that are more reliable. Efficient ageing simulation allows to factor in various operation modes and helps refining the selection. Using long term ageing simulation, we have analysed the fitness of a set of synthesized operational amplifiers with similar properties concerning various use cases. This procedure enables the selection of the most ageing resilient implementation automatically.
Random ordinary differential equations (RODEs) are ordinary differential equations (ODEs) which have a stochastic process in their vector field functions. RODEs have been used in a wide range of applications such as biology, medicine, population dynamics and engineering and play an important role in the theory of random dynamical systems, however, they have been long overshadowed by stochastic differential equations.
Typically, the driving stochastic process has at most Hoelder continuous sample paths and the resulting vector field is, thus, at most Hoelder continuous in time, no matter how smooth the vector function is in its original variables, so the sample paths of the solution are certainly continuously differentiable, but their derivatives are at most Hoelder continuous in time. Consequently, although the classical numerical schemes for ODEs can be applied pathwise to RODEs, they do not achieve their traditional orders.
Recently, Gruene and Kloeden derived the explicit averaged Euler scheme by taking the average of the noise within the vector field. In addition, new forms of higher order Taylor-like schemes for RODEs are derived systematically by Jentzen and Kloeden.
However, it is still important to build higher order numerical schemes and computationally less expensive schemes as well as numerically stable schemes and this is the motivation of this thesis. The schemes by Gruene and Kloeden and Jentzen and Kloeden are very general, so RODEs with special structure, i.e., RODEs with Ito noise and RODEs with affine structure, are focused and numerical schemes which exploit these special structures are investigated.
The developed numerical schemes are applied to several mathematical models in biology and medicine. In order to see the performance of the numerical schemes, trajectories of solutions are illustrated. In addition, the error vs. step sizes as well as the computational costs are compared among newly developed schemes and the schemes in literature.
In the qualitative analysis of solutions of partial differential equations, many interesting questions are related to the shape of solutions. In particular, the symmetries of a given solution are of interest. One of the first more general results in this direction was given in 1979 by Gidas, Ni and Nirenberg... The main tool in proving this symmetry and monotonicity result is the moving plane method. This method, which goes back to Alexandrov’s work on constant mean curvature surfaces in 1962, was introduced in 1971 by Serrin in the context of partial differential equations to analyze an overdetermined problem...
Containment problems belong to the classical problems of (convex) geometry. In the proper sense, a containment problem is the task to decide the set-theoretic inclusion of two given sets, which is hard from both the theoretical and the practical perspective. In a broader sense, this includes, e.g., radii or packing problems, which are even harder. For some classes of convex sets there has been strong interest in containment problems. This includes containment problems of polyhedra and balls, and containment of polyhedra, which have been studied in the late 20th century because of their inherent relevance in linear programming and combinatorics.
Since then, there has only been limited progress in understanding containment problems of that type. In recent years, containment problems for spectrahedra, which naturally generalize the class of polyhedra, have seen great interest. This interest is particularly driven by the intrinsic relevance of spectrahedra and their projections in polynomial optimization and convex algebraic geometry. Except for the treatment of special classes or situations, there has been no overall treatment of that kind of problems, though.
In this thesis, we provide a comprehensive treatment of containment problems concerning polyhedra, spectrahedra, and their projections from the viewpoint of low-degree semialgebraic problems and study algebraic certificates for containment. This leads to a new and systematic access to studying containment problems of (projections of) polyhedra and spectrahedra, and provides several new and partially unexpected results.
The main idea - which is meanwhile common in polynomial optimization, but whose understanding of the particular potential on low-degree geometric problems is still a major challenge - can be explained as follows. One point of view towards linear programming is as an application of Farkas' Lemma which characterizes the (non-)solvability of a system of linear inequalities. The affine form of Farkas' Lemma characterizes linear polynomials which are nonnegative on a given polyhedron. By omitting the linearity condition, one gets a polynomial nonnegativity question on a semialgebraic set, leading to so-called Positivstellensaetze (or, more precisely Nichtnegativstellensaetze). A Positivstellensatz provides a certificate for the positivity of a polynomial function in terms of a polynomial identity. As in the linear case, these Positivstellensaetze are the foundation of polynomial optimization and relaxation methods. The transition from positivity to nonnegativity is still a major challenge in real algebraic geometry and polynomial optimization.
With this in mind, several principal questions arise in the context of containment problems: Can the particular containment problem be formulated as a polynomial nonnegativity (or, feasibility) problem in a sophisticated way? If so, how are positivity and nonnegativity related to the containment question in the sense of their geometric meaning? Is there a sophisticated Positivstellensatz for the particular situation, yielding certificates for containment? Concerning the degree of the semialgebraic certificates, which degree is necessary, which degree is sufficient to decide containment?
Indeed, (almost) all containment problems studied in this thesis can be formulated as polynomial nonnegativity problems allowing the application of semialgebraic relaxations. Other than this general result, the answer to all the other questions (highly) depends on the specific containment problem, particularly with regard to its underlying geometry. An important point is whether the hierarchies coming from increasing the degree in the polynomial relaxations always decide containment in finitely many steps.
We focus on the containment problem of an H-polytope in a V-polytope and of a spectrahedron in a spectrahedron. Moreover, we address containment problems concerning projections of H-polyhedra and spectrahedra. This selection is justified by the fact that the mentioned containment problems are computationally hard and their geometry is not well understood.
This thesis covers the analysis of radix sort, radix select and the path length of digital trees under a stochastic input assumption known as the Markov model.
The main results are asymptotic expansions of mean and variance as well as a central limit theorem for the complexity of radix sort and the path length of tries, PATRICIA tries and digital search trees.
Concerning radix select, a variety of different models for ranks are discussed including a law of large numbers for the worst case behavior, a limit theorem for the grand averages model and the first order asymptotic of the average complexity in the quantile model.
Some of the results are achieved by moment transfer techniques, the limit laws are based on a novel use of the contraction method suited for systems of stochastic recurrences.
This work is concerned with two topics at the intersection of convex algebraic geometry and optimization.
We develop a new method for the optimization of polynomials over polytopes. From the point of view of convex algebraic geometry the most common method for the approximation of polynomial optimization problems is to solve semidefinite programming relaxations coming from the application of Positivstellensätze. In optimization, non-linear programming problems are often solved using branch and bound methods. We propose a fused method that uses Positivstellensatz-relaxations as lower bounding methods in a branch and bound scheme. By deriving a new error bound for Handelman's Positivstellensatz, we show convergence of the resulting branch and bound method. Through the application of Positivstellensätze, semidefinite programming has gained importance in polynomial optimization in recent years. While it arises to be a powerful tool, the underlying geometry of the feasibility regions (spectrahedra) is not yet well understood. In this work, we study polyhedral and spectrahedral containment problems, in particular we classify their complexity and introduce sufficient criteria to certify the containment of one spectrahedron in another one.
The cones of nonnegative polynomials and sums of squares arise as central objects in convex algebraic geometry and have their origin in the seminal work of Hilbert ([Hil88]). Depending on the number of variables n and the degree d of the polynomials, Hilbert famously characterizes all cases of equality between the cone of nonnegative polynomials and the cone of sums of squares. This equality precisely holds for bivariate forms, quadratic forms and ternary quartics ([Hil88]). Since then, a lot of work has been done in understanding the difference between these two cones, which has major consequences for many practical applications such as for polynomial optimization problems. Roughly speaking, minimizing polynomial functions (constrained as well as unconstrained) can be done efficiently whenever certain nonnegative polynomials can be written as sums of squares (see Section 2.3 for the precise relationship). The underlying reason is the fundamental difference that checking nonnegativity of polynomials is an NP-hard problem whenever the degree is greater or equal than four ([BCSS98]), whereas checking whether a polynomial can be written as a sum of squares is a semidefinite feasibility problem (see Section 2.2). Although the complexity status of the semidefinite feasibility problem is still an open problem, it is polynomial for fixed number of variables. Hence, understanding the difference between nonnegative polynomials and sums of squares is highly desirable both from a theoretical and a practical viewpoint.
We consider a class of nonautonomous nonlinear competitive parabolic systems on bounded radial domains under Neumann or Dirichlet boundary conditions. We show that, if the initial profiles satisfy a reflection inequality with respect to a hyperplane, then bounded positive solutions are asymptotically (in time) foliated Schwarz symmetric with respect to antipodal points. Additionally, a related result for (positive and sign changing solutions) of scalar equations with Neumann or Dirichlet boundary conditions is given. The asymptotic shape of solutions to cooperative systems is also discussed.
A multiple filter test for the detection of rate changes in renewal processes with varying variance
(2014)
The thesis provides novel procedures in the statistical field of change point detection in time series.
Motivated by a variety of neuronal spike train patterns, a broad stochastic point process model is introduced. This model features points in time (change points), where the associated event rate changes. For purposes of change point detection, filtered derivative processes (MOSUM) are studied. Functional limit theorems for the filtered derivative processes are derived. These results are used to support novel procedures for change point detection; in particular, multiple filters (bandwidths) are applied simultaneously in oder to detect change points in different time scales.
The work presented in this thesis is devoted to two classes of mathematical population genetics models, namely the Kingman-coalescent and the Beta-coalescents. Chapters 2, 3 and 4 of the thesis include results concerned with the first model, whereas Chapter 5 presents contributions to the second class of models.
We study the price-setting problem of market makers under perfect competition in continuous time. Thereby we follow the classic Glosten-Milgrom model that defines bid and ask prices as the expectation of a true value of the asset given the market makers partial information that includes the customers trading decisions. The true value is modeled as a Markov process that can be observed by the customers with some noise at Poisson times.
We analyze the price-setting problem by solving a non-standard filtering problem with an endogenous filtration that depends on the bid and ask price process quoted by the market maker. Under some conditions we show existence and uniqueness of the price processes. In a different setting we construct a counterexample to uniqueness. Further, we discuss the behavior of the spread by a convergence result and simulations.
In this thesis, the asymptotic behaviour of Pólya urn models is analyzed, using an approach based on the contraction method. For this, a combinatorial discrete time embedding of the evolution of the composition of the urn into random rooted trees is used. The recursive structure of the trees is used to study the asymptotic behavior using ideas from the contraction method.
The approach is applied to a couple of concrete Pólya urns that lead to limit laws with normal distributions, with non-normal limit distributions, or with asymptotic periodic distributional behavior.
Finally, an approach more in the spirit of earlier applications of the contraction method is discussed for one of the examples. A general transfer theorem of the contraction method is extended to cover this example, leading to conditions on the coefficients of the recursion that are not only weaker but also in general easier to check.
A stochastic model for the joint evaluation of burstiness and regularity in oscillatory spike trains
(2013)
The thesis provides a stochastic model to quantify and classify neuronal firing patterns of oscillatory spike trains. A spike train is a finite sequence of time points at which a neuron has an electric discharge (spike) which is recorded over a finite time interval. In this work, these spike times are analyzed regarding special firing patterns like the presence or absence of oscillatory activity and clusters (so called bursts). These bursts do not have a clear and unique definition in the literature. They are often fired in response to behaviorally relevant stimuli, e.g., an unexpected reward or a novel stimulus, but may also appear spontaneously. Oscillatory activity has been found to be related to complex information processing such as feature binding or figure ground segregation in the visual cortex. Thus, in the context of neurophysiology, it is important to quantify and classify these firing patterns and their change under certain experimental conditions like pharmacological treatment or genetical manipulation. In neuroscientific practice, the classification is often done by visual inspection criteria without giving reproducible results. Furthermore, descriptive methods are used for the quantification of spike trains without relating the extracted measures to properties of the underlying processes.
For that reason, a doubly stochastic point process model is proposed and termed 'Gaussian Locking to a free Oscillator' - GLO. The model has been developed on the basis of empirical observations in dopaminergic neurons and in cooperation with neurophysiologists. The GLO model uses as a first stage an unobservable oscillatory background rhythm which is represented by a stationary random walk whose increments are normally distributed. Two different model types are used to describe single spike firing or clusters of spikes. For both model types, the distribution of the random number of spikes per beat has different probability distributions (Bernoulli in the single spike case or Poisson in the cluster case). In the second stage, the random spike times are placed around their birth beat according to a normal distribution. These spike times represent the observed point process which has five easily interpretable parameters to describe the regularity and the burstiness of the firing patterns.
It turns out that the point process is stationary, simple and ergodic. It can be characterized as a cluster process and for the bursty firing mode as a Cox process. Furthermore, the distribution of the waiting times between spikes can be derived for some parameter combination. The conditional intensity function of the point process is derived which is also called autocorrelation function (ACF) in the neuroscience literature. This function arises by conditioning on a spike at time zero and measures the intensity of spikes x time units later. The autocorrelation histogram (ACH) is an estimate for the ACF. The parameters of the GLO are estimated by fitting the ACF to the ACH with a nonlinear least squares algorithm. This is a common procedure in neuroscientific practice and has the advantage that the GLO ACF can be computed for all parameter combinations and that its properties are closely related to the burstiness and regularity of the process. The precision of estimation is investigated for different scenarios using Monte-Carlo simulations and bootstrap methods.
The GLO provides the neuroscientist with objective and reproducible classification rules for the firing patterns on the basis of the model ACF. These rules are inspired by visual inspection criteria often used in neuroscientific practice and thus support and complement usual analysis of empirical spike trains. When applied to a sample data set, the model is able to detect significant changes in the regularity and burst behavior of the cells and provides confidence intervals for the parameter estimates.
We investigate multivariate Laurent polynomials f \in \C[\mathbf{z}^{\pm 1}] = \C[z_1^{\pm 1},\ldots,z_n^{\pm 1}] with varieties \mathcal{V}(f) restricted to the algebraic torus (\C^*)^n = (\C \setminus \{0\})^n. For such Laurent polynomials f one defines the amoeba \mathcal{A}(f) of f as the image of the variety \mathcal{V}(f) under the \Log-map \Log : (\C^*)^n \to \R^n, (z_1,\ldots,z_n) \mapsto (\log|z_1|, \ldots, \log|z_n|). I.e., the amoeba \mathcal{A}(f) is the projection of the variety \mathcal{V}(f) on its (componentwise logarithmized) absolute values. Amoebas were first defined in 1994 by Gelfand, Kapranov and Zelevinksy. Amoeba theory has been strongly developed since the beginning of the new century. It is related to various mathematical subjects, e.g., complex analysis or real algebraic curves. In particular, amoeba theory can be understood as a natural connection between algebraic and tropical geometry.
In this thesis we investigate the geometry, topology and methods for the approximation of amoebas.
Let \C^A denote the space of all Laurent polynomials with a given, finite support set A \subset \Z^n and coefficients in \C^*. It is well known that, in general, the existence of specific complement components of the amoebas \mathcal{A}(f) for f \in \C^A depends on the choice of coefficients of f. One prominent key problem is to provide bounds on the coefficients in order to guarantee the existence of certain complement components. A second key problem is the question whether the set U_\alpha^A \subseteq \C^A of all polynomials whose amoeba has a complement component of order \alpha \in \conv(A) \cap \Z^n is always connected.
We prove such (upper and lower) bounds for multivariate Laurent polynomials supported on a circuit. If the support set A \subset \Z^n satisfies some additional barycentric condition, we can even give an exact description of the particular sets U_\alpha^A and, especially, prove that they are path-connected.
For the univariate case of polynomials supported on a circuit, i.e., trinomials f = z^{s+t} + p z^t + q (with p,q \in \C^*), we show that a couple of classical questions from the late 19th / early 20th century regarding the connection between the coefficients and the roots of trinomials can be traced back to questions in amoeba theory. This yields nice geometrical and topological counterparts for classical algebraic results. We show for example that a trinomial has a root of a certain, given modulus if and only if the coefficient p is located on a particular hypotrochoid curve. Furthermore, there exist two roots with the same modulus if and only if the coefficient p is located on a particular 1-fan. This local description of the configuration space \C^A yields in particular that all sets U_\alpha^A for \alpha \in \{0,1,\ldots,s+t\} \setminus \{t\} are connected but not simply connected.
We show that for a given lattice polytope P the set of all configuration spaces \C^A of amoebas with \conv(A) = P is a boolean lattice with respect to some order relation \sqsubseteq induced by the set theoretic order relation \subseteq. This boolean lattice turns out to have some nice structural properties and gives in particular an independent motivation for Passare's and Rullgard's conjecture about solidness of amoebas of maximally sparse polynomials. We prove this conjecture for special instances of support sets.
A further key problem in the theory of amoebas is the description of their boundaries. Obviously, every boundary point \mathbf{w} \in \partial \mathcal{A}(f) is the image of a critical point under the \Log-map (where \mathcal{V}(f) is supposed to be non-singular here). Mikhalkin showed that this is equivalent to the fact that there exists a point in the intersection of the variety \mathcal{V}(f) and the fiber \F_{\mathbf{w}} of \mathbf{w} (w.r.t. the \Log-map), which has a (projective) real image under the logarithmic Gauss map. We strengthen this result by showing that a point \mathbf{w} may only be contained in the boundary of \mathcal{A}(f), if every point in the intersection of \mathcal{V}(f) and \F_{\mathbf{w}} has a (projective) real image under the logarithmic Gauss map.
With respect to the approximation of amoebas one is in particular interested in deciding membership, i.e., whether a given point \mathbf{w} \in \R^n is contained in a given amoeba \mathcal{A}(f). We show that this problem can be traced back to a semidefinite optimization problem (SDP), basically via usage of the Real Nullstellensatz. This SDP can be implemented and solved with standard software (we use SOSTools and SeDuMi here). As main theoretic result we show that, from the complexity point of view, our approach is at least as good as Purbhoo's approximation process (which is state of the art).
Der im Jahr 2004 am IWR Heidelberg entwickelte Neuronen Rekonstruktions-Algorithmus NeuRA extrahiert die Oberflächenmorphologie oder ein Merkmalskelett von Neuronenzellen, die mittels konfokaler oder Zwei-Photon-Mikroskopie als Bildstapel aufgenommen wurden. Hierbei wird zunächst das Signal-zu-Rausch-Verhältnis der Rohdaten durch Anwendung des speziell entwickelten trägheitsbasierten anisotropen Diffusionsfilters verbessert, dann das Bild nach der statistischen Methode von Otsu segmentiert und anschließend das Oberflächengitter der Neuronenzellen durch den Regularisierten Marching-Tetrahedra-Algorithmus rekonstruiert oder das Merkmalskelett mit einer speziellen Thinning-Methode extrahiert. In einschlägigen Vorarbeiten wurde mit Hilfe solcher Rekonstruktionen von Neuronenzellkernen gezeigt, dass diese, entgegen der vorher üblichen Meinung, nicht notwendigerweise rund sind, sondern Einstülpungen, sogenannte Invaginationen, aufweisen können. Der Einfluss der Invaginationen auf die Ausbreitung von Calciumionen innerhalb solcher Zellkerne konnte durch entsprechende numerische Simulationen systematisch untersucht werden.
Um diese Rekonstruktionsmethode auf hochaufgelöste Mikroskopaufnahmen anwenden zu können, wurden im Rahmen der vorliegenden Arbeit, die in NeuRA verwendeten Verfahren auf Basis von Nvidia CUDA auf moderner Grafikhardware parallelisiert und unter dem Namen NeuRA2 optimiert und neu implementiert. Erzielte Beschleunigungen von bis zu einem Faktor 100, bei Verwendung einer Hochleistungsgrafikkarte, zeigen, dass sich die moderne Grafikarchitektur besonders für die Parallelisierung von Bildverarbeitungsoperatoren eignet. Insbesondere das Herzstück des Rekonstruktions-Algorithmus - der sehr rechenintensive trägheitsbasierte anisotrope Diffusionsfilter - wurde durch eine clusterbasierte Implementierung, welche die parallele Verwendung beliebig vieler Grafikkarten ermöglicht, immens beschleunigt.
Darüber hinaus wurde in dieser Arbeit das Konzept von NeuRA verallgemeinert, um nicht nur Neuronenzellen aus konfokalen oder Zwei-Photon-Bildstapeln rekonstruieren zu können, sondern vielmehr die Oberflächenmorphologie oder Merkmalskelette von allgemeinen Objekten aus beliebigen Bildstapeln zu extrahieren. Dabei wird das ursprüngliche Konzept von Rauschreduktion, Bildsegmentierung und Rekonstruktion beibehalten. Für die einzelnen Schritte stehen aber nun eine Vielfalt von Bildverarbeitungs- und Rekonstruktionsmethoden zur Verfügung, die abhängig von der Beschaffenheit der Daten und den Anforderungen an die Rekonstruktion, ausgewählt werden können. Die meisten dieser Verfahren wurden ebenfalls auf Basis moderner Grafikhardware parallelisiert.
Die weiterentwickelten Rekonstruktionsverfahren wurden in mehreren Anwendungen eingesetzt: Einerseits wurden Oberflächen- und Volumengitter aus konfokalen Bildstapeln und Computertomographie-Aufnahmen generiert, die für verschiedene numerische Simulationen eingesetzt wurden oder eingesetzt werden sollen. Des Weiteren wurden über zwanzig antike Keramikgefäße und Fragmente anderer antiker Keramiken rekonstruiert. Hierbei wurde jeweils die Rohdichte und bei den komplett erhaltenen Gefäßen das Füllvolumen berechnet. Es konnte gezeigt werden, dass dieses Verfahren exakter ist als die in der Archäologie üblichen Methoden zur Volumenbestimmung von Gefäßen. Außerdem zeigt sich eine Abhängigkeit der Rohdichte der rekonstruierten Objekte vom jeweils verwendeten Keramiktyp. Eine Analyse, wie genau die Krümmung von Objekten durch die Approximation von Dreiecksgittern dargestellt werden kann, wurde ebenfalls durchgeführt.
Zusätzlich wurde ein Verfahren zur Rekonstruktion der Merkmalskelette lebender Neuronenzellen oder Teilen von Neuronenzellen entwickelt. Bei den damit rekonstruierten Daten wurden einzelne dendritische Dornfortsätze, auch Spines genannt, hochaufgelöst mikroskopiert. Auf Basis dieser Rekonstruktionen kann die Länge von Dendriten oder einzelner Spines, der Winkel zwischen Dendritenverzweigungen, sowie das Volumen einzelner Spines automatisch berechnet werden. Mit Hilfe dieser Daten kann der Einfluss pharmakologischer Präparate und mechanischer Eingriffe in das Nervensystem von lebenden Versuchstieren systematisch untersucht werden.
Eine Adaption der beschriebenen Rekonstruktionsverfahren ist aufgrund deren einfacher Erweiterbarkeit und flexibler Verwendbarkeit für zukünftige Anwendungen leicht möglich.
Die anaerobe Fermentation beschreibt den Abbau organischen Materials unter Ausschluss von Sauerstoff und setzt sich aus vier Prozessphasen (Hydrolyse, Acidogenese, Acetogenese und Methanogenese) zusammen. Im Rahmen dieser Arbeit konnte die Aufteilung dieser vier Prozessphasen auf die beiden Stufen eines zweistufigen zweiphasigen Biogas-Reaktors genau bestimmt werden. Die Aufteilung ist von entscheidender Bedeutung für zukünftige Arbeiten, da dadurch genau festgelegt werden kann, welche Stoffe bei den Messungen und bei der Modellierung berücksichtigt werden müssen.
Im Jahre 2002 wurde von der IWA Taskgroup das ADM1-Modell, welches alle vier Prozessphasen der anaeroben Fermentation berücksichtigt, veröffentlicht. In der vorliegenden Arbeit wird ein räumlich aufgelöstes Modell für die anaerobe Fermentation erarbeitet, in dem das ADM1-Modell mit einem Strömungsmodell gekoppelt wird. Anschließend wird ein reduziertes Simulationsmodell für acetoklastische Methanogenese in einem zweistufigen zweiphasigen Biogasreaktor erstellt. Anhand von Messdaten wird gezeigt, dass der Abbau von Essigsäure zu Methan innerhalb des Reaktors durch das Simulationsmodell gut wiedergegeben werden kann.
Anschließend wird das validierte Modell verwendet um Regeln für eine optimale Steuerung des Reaktors herzuleiten und weiterhin wird mit Hilfe der lokalen Methanproduktion die Effektivität des Reaktors bestimmt. Die erlangten Informationen können verwendet werden, um den Biogas-Reaktor zu optimieren.
Within the last twenty years, the contraction method has turned out to be a fruitful approach to distributional convergence of sequences of random variables which obey additive recurrences. It was mainly invented for applications in the real-valued framework; however, in recent years, more complex state spaces such as Hilbert spaces have been under consideration. Based upon the family of Zolotarev metrics which were introduced in the late seventies, we develop the method in the context of Banach spaces and work it out in detail in the case of continuous resp. cadlag functions on the unit interval. We formulate sufficient conditions for both the sequence under consideration and its possible limit which satisfies a stochastic fixed-point equation, that allow to deduce functional limit theorems in applications. As a first application we present a new and considerably short proof of the classical invariance principle due to Donsker. It is based on a recursive decomposition. Moreover, we apply the method in the analysis of the complexity of partial match queries in two-dimensional search trees such as quadtrees and 2-d trees. These important data structures have been under heavy investigation since their invention in the seventies. Our results give answers to problems that have been left open in the pioneering work of Flajolet et al. in the eighties and nineties. We expect that the functional contraction method will significantly contribute to solutions for similar problems involving additive recursions in the following years.
We provide a mathematical framework to model continuous time trading in limit order markets of a small investor whose transactions have no impact on order book dynamics. The investor can continuously place market and limit orders. A market order is executed immediately at the best currently available price, whereas a limit order is stored until it is executed at its limit price or canceled. The limit orders can be chosen from a continuum of limit prices.
In this framework we show how elementary strategies (hold limit orders with only finitely many different limit prices and rebalance at most finitely often) can be extended in a suitable
way to general continuous time strategies containing orders with infinitely many different limit prices. The general limit buy order strategies are predictable processes with values in the set of nonincreasing demand functions (not necessarily left- or right-continuous in the price variable). It turns out that this family of strategies is closed and any element can be approximated by a sequence of elementary strategies.
Furthermore, we study Merton’s portfolio optimization problem in a specific instance of this framework. Assuming that the risky asset evolves according to a geometric Brownian
motion, a proportional bid-ask spread, and Poisson execution times for the limit orders of the small investor, we show that the optimal strategy consists in using market orders to keep the
proportion of wealth invested in the risky asset within certain boundaries, similar to the result for proportional transaction costs, while within these boundaries limit orders are used to profit from the bid-ask spread.
Forschungsbedarf. Wenn man die mathematische Entwicklung in der frühen Kindheit als einen ganzheitlichen Prozess betrachtet, so gilt es, die Forschungsperspektive für unterschiedliche Lernorte zu öffnen. Einer dieser Lernorte ist die Familie, in welchem mathematische Bildungsprozesse der frühen Kindheit entscheidend von elterlichem Support beeinflusst werden. Bei der Untersuchung dieses Lernortes ist in der deutschsprachigen Mathematik-didaktik bisher eine Beschränkung auf Interviewstudien zu beobachten, in denen die Vorstellungen und Überzeugungen der Eltern zum Mathematiklernen und zur Mathematik rekonstruiert werden. Beobachtungsstudien, welche unabhängig von der Perspektive der Eltern Realisierungen von Support untersuchen, liegen bisher nicht vor. Die vorliegende Dissertation liefert einen Beitrag zur Bearbeitung dieses spezifischen Forschungsbedarfs in der deutschsprachigen Mathematikdidaktik.
Die Studie. Die durchgeführte, längsschnittlich angelegte Videostudie, die der Dissertation zugrunde liegt, ist der rekonstruktiven Sozialforschung und im Speziellen der Interpretativen Forschung in der Mathematikdidaktik zuzuordnen. Es wurden zehn Vorschulkinder und ihre Mütter ein Jahr lang in offenen Vorlese- und Spielsituationen begleitet. Als Grundlage der Analyse dienen Transkripte von ausgewählten Szenen. Die Transkriptanalyse ist durchgehend am Prinzip der Komparation orientiert und erfolgt zweischrittig: In einer Interaktionsanalyse wird zunächst die interaktionale Entwicklung des mathematischen Themas in der jeweiligen Szenen nachgezeichnet; darauf aufbauend wird die Diskursszene in einer Support-Fokussierung im Hinblick auf das hergestellte Support-System ausgedeutet.
Der Forschungsgegenstand. Gemäß der Verortung in der Interpretativen Forschung wird der Forschungsgegenstand aus sozialkonstruktivistisch-interaktionistischer Perspektive betrachtet. Demzufolge ist der Support in mathematischen Mutter-Kind-Diskursen kein einseitiges Helfen der Mutter, sondern ein von Mutter und Kind gemeinsam in der Interaktion hergestelltes Support-System.
Ergebnisse. Der Support in mathematischen Mutter-Kind-Diskursen wird in der vorliegenden Dissertation als ein Mathematics Acquisition Support System (MASS) beschrieben und aus zwei unterschiedlichen Perspektiven beleuchtet.
Die erste Perspektive ist eine allgemein sozialisationstheoretische und zeigt, dass das MASS in mathematischen Mutter-Kind-Diskursen auf unterschiedliche übergeordnete Aufgaben ausgerichtet sein kann: auf ein Mitmachen, auf einen Entwicklungsfortschritt oder auf eine freie Erkundung des Kindes. Diese Typisierung von Support-Jobs verdeutlicht, dass sich Support-Systeme gegenstandsspezifisch unterscheiden. Während das Discourse Acquisition Support System (DASS), welches im Hinblick auf die Entwicklung von Erzählkompetenz beschrieben
wurde (vgl. Hausendorf und Quasthoff 2005), ausschließlich auf eine übergeordnete Aufgabe ausgerichtet ist, kann das MASS über die Arbeit an unterschiedlichen Support-Jobs hergestellt werden. So sind Vorschulkinder im familialen Kontext in mathematische Diskurse eingebunden, die an unterschiedlichen Support-Jobs ausgerichtet sind. Dieses Ergebnis gewinnt dadurch zusätzliche Bedeutung, dass die Support-Jobs in den mathematischen Mutter-Kind-Diskursen als charakterisierend für die jeweiligen Mutter-Kind-Paare rekonstruiert werden konnten. Sowohl in Komparationen über die Zeit als auch in solchen über das Material etablieren und bearbeiten Mutter und Kind mit einer gewissen Stabilität einen spezifischen Support-Job. Die Biographie von Vorschulkindern als Mathematiklerner wird in der Familie also auf spezifische Weise geprägt.
Die zweite Perspektive ist eine genuin mathematikdidaktische und gliedert sich in zwei Teilperspektiven auf. Eine fokussiert auf das Mathematiklernen, die andere auf die Mathematik. In der Perspektive des Mathematiklernens werden Realisierungen von alltagspädagogischen Konzepten typisiert. Dabei zeigt sich, wie unterschiedlich Vorschulkinder als Mathematiklerner in Support-Systeme eingebunden werden: als Sachkundiger, als Wissender und als Denker (vgl. Olson und Bruner 1996). Anhand dieser gebildeten Typen wird das Forschungsfeld dahingehend strukturiert, welchen Konzepten vom Mathematiklernen und -lehren Vorschulkinder im familialen Kontext begegnen. In der Perspektive der Mathematik wird schließlich erarbeitet, wie Vorschulkinder und ihre Mütter in und mit ihrem je spezifischen MASS die Mathematik in den Sinnbereich ihres Alltags einbinden (vgl. Bachmair 2007): als Hilfsmittel, als Lernstoff und als Beschreibungs- und Denkmittel. Damit sind drei Typen mathematischer Sozialisation im familialen Kontext beschrieben.
Insgesamt macht die Verbindung aus einer allgemein sozialisationstheoretischen und einer mathematikdidaktischen Perspektive umfassend beschreibbar, wie Kinder im familialen Kontext in Support-Systeme zum Mathematiklernen eingebunden sind. Die Bildung unterschiedlicher Typen konnte sowohl im Hinblick auf die allgemeine Fokussierung des MASS als auch im Hinblick auf die damit realisierten Konzepte von Mathematiklernen und Mathematik vor-genommen werden. Damit ist der Lernort der Familie für die frühe mathematische Bildung und den Forschungsgegenstand des Supports strukturiert und anhand von Fallstudien beschrieben. Dieses Forschungsergebnis ist eine neue Einsicht über den bisher nur wenig erforschten Lernort der Familie und gleichzeitig eine Herausforderung für den Mathematikunterricht der Grundschule. Denn im Sinne einer Passung zwischen Familie und Schule gilt es, an die jeweiligen Interaktionserfahrungen der Kinder anzuknüpfen.
In recent years using symmetry has proven to be a very useful tool to simplify computations in semidefinite programming. This dissertation examines the possibilities of exploiting discrete symmetries in three contexts: In SDP-based relaxations for polynomial optimization, in testing positivity of symmetric polynomials, and combinatorial optimization. In these contexts the thesis provides new ways for exploiting symmetries and thus deeper insight in the paradigms behind the techniques and studies a concrete combinatorial optimization question.
In der folgenden Arbeit werden Eigenschaften von Verzweigungsprozessen in zufälliger Umgebung (engl. branching processes in random environment, kurz BPREs) untersucht. Das Modell geht auf Smith (1969) und Athreya (1971) zurück. Ein BPRE ist ein einfaches mathematisches Modell für die Entwicklung einer Population von apomiktischen (d.h. sich ungeschlechtlich fortpflanzenden) Individuen in diskreter Zeit, wobei die Umgebungsbedingungen einen Einfluß auf den Fortpflanzungserfolg der Individuen haben. Dabei wird angenommen, dass die Umgebungsbedingungen in den einzelnen Generationen zufällig sind, und zwar unabhängig und identisch verteilt von Generation zu Generation. Man denke z.B. an eine Population von Pflanzen mit einem einjährigen Zyklus, die in jedem Jahr anderen Witterungsbedingungen ausgesetzt sind, wobei angenommen wird, dass diese sich unabhängig und identisch verteilt ändern. In Kapitel 1 wird eines der wichtigsten Hilfsmittel zur Beschreibung von BPREs, die sogenannte zugehörige Irrfahrt, eingeführt und die Klassifizierung von BPREs beschrieben. In Kapitel 2 werden bekannte Resultate, insbesondere zu kritischen, schwach subkritischen und stark subkritischen Verzweigungsprozessen, wiederholt. In Kapitel 3 wird der sogenannte intermediär subkritische Fall behandelt. Mithilfe von funktionalen Grenzwertsätzen für bedingte Irrfahrten wird die genaue Asymptotik der Überlebenswahrscheinlichkeit des Prozesses, die bereits in Vatutin (2004) bewiesen wurde, unter etwas allgemeineren Voraussetzungen gezeigt. Anschließend wird untersucht, wie häufig der Prozess, bedingt auf Überleben, nur noch aus einem Individuum besteht. Im letzten Teil des Kapitels wird ein funktionaler Grenzwertsatz für die zugehörige Irrfahrt, bedingt aufs Überleben des Prozesses, gezeigt. Diese konvergiert, richtig skaliert, gegen einen Levy-Prozess, der darauf bedingt ist, sein Minimum am Ende anzunehmen. In Kapitel 4 werden große Abweichungen von BPREs untersucht. Die Ratenfunktion des BPRE wird sowohl für den Fall mindestens geometrisch schnell abfallender Tails, als auch für den Fall von Nachkommenverteilungen mit schweren Tails bestimmt. Wie sich herausstellt, hängt die Ratenfunktion von der Ratenfunktion der zugehörigen Irrfahrt, der exponentiellen Abfallrate der Überlebenswahrscheinlichkeit sowie, bei Nachkommenverteilungen mit schweren Tails, auch von den Tails derselben ab. In der Ratenfunktion spiegeln sich die wahrscheinlichsten Wege, um Ereignisse der großen Abweichungen zu realisieren, wider, was in Kapitel 4.3 beschrieben wird. In Kapitel 4.4 wird im speziellen Fall von Nachkommenverteilungen mit gebrochen-linearer Erzeugendenfunktion die Ratenfunktion für Ereignisse bestimmt, bei denen ein superkritischer BPRE überlebt, aber klein im Vergleich zum Erwartungswert bleibt. In Kapitel 4.5 werden die großen Abweichungen, bedingt auf die Umgebung untersucht (engl. quenched). In diesem Fall können unwahrscheinliche Ereignisse nur über den Verzweigungsmechanismus und nicht mehr über eine außergewöhnliche Umgebung realisiert werden. Zum Abschluss der Dissertation werden Verzweigungsprozesse in zufälliger Umgebung, bedingt auf Überle-ben, simuliert. Dazu wird eine Konstruktion nach Geiger (1999) angewendet. Diese erlaubt es, Galton-Watson Bäume in variierender Umgebung, bedingt auf Überleben, entlang einer Ahnenlinie zu konstruieren. Der Fall geometrischer Nachkommenverteilungen, auf den wir uns in Kapitel 5 beschränken, erlaubt die explizite Berechnung der benötigten Verteilungen. Als Anwendung des Grenzwertsatzes aus Kapitel 3.1 können nun intermediär subkritische Verzweigungsprozesse, bedingt auf Überleben, wie folgt simuliert werden: Zunächst wird die Umgebung zufällig bestimmt, und zwar als Irrfahrt, bedingt darauf ihr Minimum am Ende anzunehmen. Anschließend wird, der Geiger-Konstruktion folgend, ein Verzweigungsprozess in dieser Umgebung, bedingt auf Überleben, simuliert. Zum Abschluss wird in einem kurzen Ausblick auf aktuelle Forschung verwiesen. Im Anhang befinden sich einige technische Resultate.
Die vorliegende Dissertation analysiert Großinvestorhandelsstrategien in illiquiden Finanzmärkten. Ein Großinvestor beeinflusst die Preise der Wertpapiere, die er handelt, so dass der daraus resultierende Feedbackeffekt berücksichtigt werden muss. Der Preisprozess wird durch eine Familie von cadlag Semimartingalen modelliert, die in dem zusätzlichen Parameter stetig differenzierbar ist. Ziel ist es, eine möglichst allgemeine Strategiemenge zu bestimmen, für die eine Vermögensdynamik definiert werden kann. Es sind dies vorhersehbare Prozesse von wohldefinierter quadratischer Variation entlang Stoppzeiten. Sie erweisen sich als laglad. Die Vermögensdynamikzerlegung zeigt, dass bei stetigen adaptierten Strategien von endlicher Variation (zahme Strategien) die quadratischen Transaktionskostenterme verschwinden und der Gewinnprozess nur noch aus einem nichtlinearen stochastischen Integral besteht. Es wird gezeigt, unter welchen Bedingungen gewisse Approximationen vorhersehbarer laglad Strategien durch adaptierte stetige Strategien von endlicher Variation möglich sind. Im Fall, dass der Approximationsfehler für die Risikoeinstellung des Großinvestors erträglich ist, kann er seine Investmentziele durch Verwendung dieser zahmen Strategien, Liquiditätskosten vermeidend, erreichen. In diesem Fall ist der Gewinnprozess durch das nicht-lineare stochastische Integral gegeben.
Dessins d'enfants (children's drawings) may be defined as hypermaps, i.e. as bipartite graphs embedded in compact Riemann surfaces. They are very important objects in order to describe the surface of the embedding as an algebraic curve. Knowing the combinatorial properties of the dessin may, in fact, help us determining defining equations or the field of definition of the surface. This task is easier if the automorphism group of the dessin is "large". In this thesis we consider a special type of dessins, so-called Wada dessins, for which the underlying graph illustrates the incidence structure of points and of hyperplanes of projective spaces. We determine under which conditions they have a large orientation-preserving automorphism group. We show that applying algebraic operations called "mock" Wilson operations to the underlying graph we may obtain new dessins. We study the automorphism group of the new dessins and we show that the dessins we started with are coverings of the new ones.
Tropical geometry is the geometry of the tropical semiring \[\mathbb{T}:=(\mathbb{R}\cup\{\infty\},\min,+).\] Classical algebraic structures correspond to tropical structures. If $I\lhd K[x_1,\ldots,x_n]$ is an ideal in a polynomial ring over a field $K$ with valuation $v$, then the classical algebraic variety correspond to the tropical variety $T(I)$. It is the set of all points $w$, such that the minimum $\min\{v(c_\alpha)+w\cdot\alpha\}$ is achieved twice for all $f=\sum_\alpha c_\alpha x^\alpha\in I$. So tropical geometry relates algebraic geometric problems with discrete geometric problems. In this thesis we obtain a tropical version of the Eisenbud-Evans Theorem which states that every algebraic variety in $\mathbb{R}^n$ is the intersection of $n$ hypersurfaces. We find out that in the tropical setting every tropical variety $T(I)$ can be written as an intersection of only $(n+1)$ tropical hypersurfaces. So we get a finite generating system of $I$ such that the corresponding tropical hypersurfaces intersect to the tropical variety, a so-called tropical basis. Let $I \lhd K[x_1,\ldots,x_n]$ be a prime ideal generated by the polynomials $f_1, \ldots, f_r$. Then there exist $g_0,\ldots,g_{n} \in I$ such that \[ T(I) \ = \ \bigcap_{i=0}^{n}T(g_i)\] and thus $\mathcal{G} := \{f_1, \ldots, f_r, g_0, \ldots, g_{n}\}$ is a tropical basis for $I$ of cardinality $r+n+1$. Tropical bases are discussed by Bogart, Jensen, Speyer, Sturmfels and Thomas where it is shown that tropical bases of linear polynomials of a linear ideal have to be very large. We do not restrict the tropical basis to consist of linear polynomials and therefore we get a shorter tropical basis. But the degrees of our polynomials can be very large. The main ingredient to get a short tropical basis is the use of projections, in particular geometrically regular projections. Together with the fact that preimages of projections of tropical varieties are themselves tropical varieties of a certain elimination ideal we get the desired result. Let $I \lhd K[x_1, \ldots, x_n]$ be an $m$-dimensional prime ideal and $\pi : \mathbb{R}^n \to \mathbb{R}^{m+1}$ be a rational projection. Then $\pi^{-1}(\pi(T(I)))$ is a tropical variety, namely \[ \pi^{-1}(\pi(T(I))) \ = \ T(J \cap K[x_1, \ldots, x_n]) \,\] Here $J$ is an ideal in $K[x_1,\ldots,x_n,\lambda_1,\ldots,\lambda_{n-m-1}]$ derived from the ideal $I$. We show that this elimination ideal is a principal ideal which yields a polynomial in our tropical basis. The advantage of our method is that we find our polynomials by projections and therefore we can use the results of Gelfand, Kapranov and Zelevinsky , of Esterov and Khovanskii , and of Sturmfels, Tevelev and Yu. With mixed fiber polytopes we get the structure and combinatorics of the image of a tropical variety and therefore the structure of the polynomials in our tropical basis. Let $I=\lhd K[x_1,\ldots,x_n]$ an $m$-dimensional ideal, generated by generic polynomials $f_1,\ldots, f_{n-m}$, $\pi:\mathbb{R}^n\to\mathbb{R}^{m+1}$ a projection and $\psi$ a projection presented by a matrix with a rowspace equal to the kernel of $\pi$. Then up to affine isomorphisms, the cells of the dual subdivision of $\pi^{-1} \pi T(I)$ are of the form \[ \sum_{i=1}^p \Sigma_{\psi} (C_{i1}^{\vee}, \ldots, C_{i{k}}^{\vee}) \] for some $p\in\mathbb{N}$ and faces $F_1, \ldots, F_p$ of $T(f_1)\cap\ldots\cap T(f_k)$ and the dual cell of $F_i\subseteq U = T(f_1)\cup\ldots\cup T(f_k)$ is given by $F_i^\vee=C_{i1}^{\vee}+ \ldots+ C_{ik}^{\vee}$ with faces $C_{i1}, \ldots, C_{i k}$ of $T(f_1), \ldots, T(f_{k})$. In case that we project a tropical curve we want to find the number of $(n-1)$-cells of the above form with $p>1$, i.e. the cells which are dual to vertices of $\pi(T(I))$ which are the intersection of the images of two non-adjacent $1$-cells of $T(I)$. Vertices of this type are called selfintersection points. We show that there exist a tropcal line $L_n\subset\mathbb{R}^n$ and a projection $\pi:\mathbb{R}^n\to\mathbb{R}^2$, such that $L_n$ has $\sum_{i=1}^{n-2}i$ selfintersection points. Furthermore we find tropical curves $\mathcal{C}\subset\mathbb{R}^n$, which are transversal intersections of $n-1$ tropical hypersurfaces of degrees $d_1,\ldots,d_{n-1}$ and a projection $\pi:\mathbb{R}^n\to\mathbb{R}^2$, such that $\mathcal{C}$ has at least $(d_1\cdot\ldots\cdot d_{n-1})^2\cdot \sum_{i=1}^{n-2}i) $ selfintersection points. A caterpillar is a certain simple type of a tropical line and for this type we show that it can have at most $\sum_{i=1}^{n-2}i$ selfintersection points.
Gegenstand dieser Arbeit sind Galoisoperationen auf quasiplatonischen Riemannschen Flächen mit einer Automorphismengruppe isomorph zu PSL(2,F(q)). Quasiplatonische Riemannsche Flächen werden durch torsionsfreie Normalteiler N in einer Dreiecksgruppe D uniformisiert, d.h. N ist die universelle Überlagerungsgruppe und die Flächen, die man auch als algebraische Kurven beschreiben kann, sind isomorph zu N\U, wenn U die obere Halbebene bezeichnet. Bzgl. der Größe der Automorphismengruppen bilden die quasiplatonischen Kurven die lokalen Maxima im Modulraum. Die absoluten Maxima liegen bei den Hurwitz-Kurven; hier hat die Automorphismengruppe die maximale Größe von 84(g-1), wenn g>1 das Geschlecht der Kurve ist. Der Normalisator in PSL(2,R) der Überlagerungsgruppe N ist dann die Dreiecksgruppe mit Signatur (2,3,7). Macbeath hat die Bedingungen dafür gefunden, wann PSL(2,F(q)) eine Hurwitz-Gruppe ist. Von besonderem Interesse ist dabei der Fall, dass q=p eine Primzahl kongruent +-1 mod 7 ist. Hier hat man drei nicht-isomorphe Kurven, die jedoch alle galoiskonjugiert zueinander sind. In der Arbeit werden Bedingungen angegeben, unter denen sich dieses Resultat auf Dreiecksgruppen D mit einer Signatur der Form (2,m_1,m_2) verallgemeinern lässt. Dabei gehen einerseits Ergebnisse von Frye ein, der die Anzahl der verschiedenen torsionsfreien Normalteiler N<D mit Quotienten PSL(2,F(q)) über die Spurtupel der Erzeugenden von D bestimmt hat. Andererseits wird eine Methode von Streit verwendet, mit der man die Galoisoperation auf den Kurven anhand des Verhaltens der Multiplikatoren der Erzeugenden in der Automorphismengruppe nachvollziehen kann. Es zeigt sich, dass sich Spur- und Multiplikatortupel entsprechen, woraus man die Anzahl und Länge der Galois-Orbits erhält. Außerdem lässt sich der Definitionskörper der Kurven bestimmen. Offen bleibt das genaue Verhalten bei Signaturen (m_0,m_1,m_2) mit m_i ungleich 2 für alle i. Hier gibt es zu jedem Multiplikatortupel zwei verschiedene Spurtupel. Kann man die Kurven durch die Multiplikatoren beschreiben, dann erhält man Projektionen D->>PSL(2,F(q)) auch über die Quaternionenalgebra, die die Dreiecksgruppe über ihrem Spurkörper erzeugt. Die Normalteiler erweisen sich dann als Schnitt der Dreiecksgruppe mit einer Hauptkongruenzuntergruppe nach einem Primideal P|char(F(q)) in der Norm-1-Gruppe einer Ordnung der Quaternionenalgebra. Dabei ist das Spurtripel in PSL(2,F(q)) gerade das Spurtripel aus D modulo P. Ändert man P, so erhält man ein anderes Spurtripel in PSL(2,F(q)), also auch einen anderen Normalteiler. Bilden die zugehörigen Kurven eine Bahn unter der Galoisoperation, dann ergeben sich alle Normalteiler auf diese Weise. Die Galoisoperation auf den Tripeln der Multiplikatoren, also die Galoisoperation auf den Kurven, ist verträglich mit der Operation, die die Primideale P|char(F(q)) permutiert. Wir erhalten also eine natürliche Korrespondenz zwischen der Galoisoperation auf den Kurven einerseits und der Operation auf den Primidealen andererseits.
Mixed volumes, mixed Ehrhart theory and applications to tropical geometry and linkage configurations
(2009)
The aim of this thesis is the discussion of mixed volumes, their interplay with algebraic geometry, discrete geometry and tropical geometry and their use in applications such as linkage configuration problems. Namely we present new technical tools for mixed volume computation, a novel approach to Ehrhart theory that links mixed volumes with counting integer points in Minkowski sums, new expressions in terms of mixed volumes of combinatorial quantities in tropical geometry and furthermore we employ mixed volume techniques to obtain bounds in certain graph embedding problems.
Deformation quantization on symplectic stacks and applications to the moduli of flat connections
(2008)
It is a common problem in mathematical physics to describe and quantize the Poisson algebra on a symplectic quotient [...] given in terms of some moment map [...] on a symplectic manifold [...] with a hamiltonian action by a Lie group G. Among others, problems may arise in two parts of the process: c might be a singular value of the moment map and the quotient might not be well-behaving; in the interesting cases the quotient often is singular. By the famous result of Sjamaar and Lerman ([102]) X is a symplectic stratified space. We are interested in cases for which we can give a deformation quantization of the possibly singular Poisson algebra of X. To that purpose we introduce a Poisson algebra on the associated stack [...] for special cases and consider its deformations and their classification. We dedicate ourselves to use the rather geometric methods introduced by Fedosov for symplectic manifolds in [37]. That leads to the question how to perform differential geometry on a smooth stack. The Lie groupoid atlas of a smooth stack is a nice model for the same space (Tu, Xu and Laurent-Gengoux in [107] and Behrend and Xu in [16]), but both have different topoi. We give a morphism (P,R) that compares the topologies of a smooth stack and its atlas. This yields a method to transport sheaves and their sections between a smooth stack and its Lie groupoid atlas. A symplectic stack is a smooth separated Deligne-Mumford stack with a 2-form which is closed and non-degenerate in an atlas. Via (P,R) a deformation quantization on a symplectic stack can be performed in terms of an atlas. We also give a classification functor for the quantizations in the spirit of Deligne ([35]) based on the geometric interpretation given by Gutt and Rawnsely in [49]. As an application we give a deformation quantization for the moduli stack of flat connections in particular configurations. We use Darboux charts provided by Huebschmann (e.g. in [54]) to construct the corresponding Lie groupoid. This captures the symplectic form arising in the reduction process and differs from other approaches using gerbes of bundles (e.g. Teleman [105]).
In this work, we extend the Hegselmann and Krause (HK) model, presented in [16] to an arbitrary metric space. We also present some theoretical analysis and some numerical results of the condensing of particles in finite and continuous metric spaces. For simulations in a finite metric space, we introduce the notion "random metric" using the split metrics studies by Dress and al. [2, 11, 12].
Funktionen beschränkter mittlerer Oszillation wurden von F. John und L. Nirenberg in ihrer Arbeit von 1961 eingeführt. Das Konzept der beschränkten mittleren Oszillation findet erste Verwendung beim Beweis der Harnackschen Ungleichung für elliptische partielle Differentialgleichungen durch Moser. In dieser Arbeit wird die Idee der beschränkten mittleren Oszillation auf harmonische Räume (X,H) übertragen. Erstmals wurde dieses Konzept von H. Leutwiler in einem Artikel für allgemeine harmonische Räume entwickelt. Da die Mehrzahl der Ergebnisse in Leutwilers Arbeit nur für Brelotsche Räume oder sogar nur für die Laplacegleichung auf der oberen Halbebene gezeigt werden konnten, sind diese zum Beispiel nicht auf harmonische Räume anwendbar, die durch einen parabolischen Differentialoperator, wie die klassische Wärmeleitungsgleichung, erzeugt wurden. Ziel dieser Arbeit ist es nun die Theorie der harmonischen Funktionen beschränkter mittlerer Oszillation für allgemeine harmonische Räume zu entwickeln und unter anderem die Leutwilerschen Resultate zu beweisen. Naturgemäß lassen sich die Beweise aus Leutwilers Arbeit im Allgemeinen nicht einfach übertragen. Vielmehr mußten zum Teil neue Beweisideen und Methoden gefunden werden. Insbesondere wird konsequent von Bezugsmaßen Gebrauch gemacht, die eine allgemeine Harnacksche Ungleichung für diesen Rahmen zur Verfügung stellen. Ausgehend von Resultaten von T. Lyons kann im zweiten Kapitel eine Charakterisierung des Raumes BMO(X) gezeigt werden, wie sie bisher nur im klassischen Fall bekannt war. Aufbauend auf eine Arbeit von Bliedtner und Loeb wird im dritten Kapitel zuerst eine abstrakte Integraldarstellung quasibeschränkter Funktionen hergeleitet, die in Theorem 3.1.9 ihren Niederschlag findet. Dieses Theorem erlaubt eine Darstellung der kleinsten harmonischen Majorante gewisser subharmonischer Funktionen in Theorem 3.1.15. Ausgehend von diesen Resultaten werden schließlich in Theorem 3.2.2 und Korollar 3.2.3 Charakterisierungen harmonischer Funktionen beschränkter mittlerer Oszillation durch ihr Randverhalten erzielt, wie sie bisher nur im klassischen Fall der Laplacegleichung auf der oberen Halbebene in einer späteren Arbeit von Leutwiler gezeigt werden konnten. Im vierten Kapitel werden die harmonischen Räume (X,H) der Laplace- und Wärmeleitungsgleichung als grundlegende Beispiele betrachtet. Im fünften Kapitel wird die Vollständigkeit gewisser Teilmengen des Raumes (BMO(X)/R) untersucht. In Theorem 5.1.10 wird durch Modifikation der Norm gezeigt, daß dieser so modifizierte Raum ein Banachraum ist, allerdings zu dem Preis, daß sämtliche Funktionen in diesem Raum beschränkt sind. Aus Theorem 5.2.4 ergibt sich als Korollar 5.2.6 ein neuer Beweis der Tatsache, daß im Spezialfall Brelotscher harmonischer Räume der Raum (BMO(X)/R) ein Banachraum ist. Schließlich zeigt Theorem 5.2.12, daß gewisse Teilmengen von (BMO(X)/R) vollständig bezüglich der BMO-Norm sind, ohne daß man dabei zusätzliche Bedingungen (wie etwa Brelotscher Raum) an (X,H) stellen muß.
Das libor Markt Modell (LMM) ist seit seiner Entwicklung in den Veröffentlichungen von Brace, Gatarek, Musiela (1997), einerseits, und unabhängig von diesen von Miltersen, Sandmann, Sondermann (1997), andererseits, zu dem anerkanntesten Instrument zur Modellierung der Zinsstruktur und der damit verbundenen Preisfindung für relevante Finanzderivate geworden. libor steht dabei für London Inter-Bank Offered Rate, ein täglich in London fixierter Referenz-Zins für kurzfristige Anlagen. Drei- oder sechsmonatige Laufzeiten sind in Verbindung mit dem LMM üblich. Die Forschung zur Verbesserung dieses Modells hat in den letzten Jahren an Zuwachs gewonnen. Beim Versuch den Fehler der Anpassung an die täglich beobachteten Preise von Zinsoptionen wie Caps und Swaptions zu verringern, erhält man in der Folge auch genauere Bewertungen für andere, exotischere, Derivate. Die zugrunde liegende und zentrale Idee des LMM besteht darin, die Forward (Termin) Zinsen direkt als primären (Vektor) Prozess mehrerer libor Sätze zu betrachten und diese simultan zu modellieren, anstatt sie nur herzuleiten aus einem übergeordneten, unendlich dimensionalen Forward Zinsprozess, wie im zeitlich früher entwickelten Heath-Jarrow-Morton Modell. Das überzeugendste Argument für diese Diskretisierung ist, dass die libor Sätze direkt im Markt beobachtbar sind und ihre Volatilitäten auf eine natürliche Weise in Beziehung gebracht werden können zu bereits liquide gehandelten Produkten, eben jenen Caps und Swaptions. Dennoch beinhaltet das Modell eine gravierende Insuffizienz, indem es keine Krümmung der Volatilitätsoberfläche, im Hinblick auf Optionen mit verschiedenen Basiszinsen, abbildet. Wie im einfachen eindimensionalen Black-Scholes Modell prägen sich auch hier die Ungenauigkeiten der Verteilung in fehlenden heavy tails deutlich aus. Smile und Skew Effekte sind erkennbar. Im klassischen liborMarkt Modell wird in Richtung der Basiszinsdimension nur eine affine Struktur erzeugt, welche bestenfalls als Approximation für die erwünschte Oberfläche dienen kann. Die beobachteten Verzerrungen führen naturgemäss zu einer ungenauen Abbildung der Realität und fehlerhaften Reproduktion der Preise in Regionen, die ein wenig entfernt vom Bereich am Geld liegen. Derartig ungewollte Dissonanzen in Gewinn und Verlustzahlen führten z.B. in 1998 zu gravierenden Verlusten im Zinsderivateportfolio der heutigen Royal Bank of Scotland. ...
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 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.
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.
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.
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.
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.
Komplexität von Gitterproblemen : Nicht-Approximierbarkeit und Grenzen der Nicht-Approximierbarkeit
(2000)
Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P <> NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO exp(1/log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n/ sqrt(log n) unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q >= N, so daß maxi minp2Z |q alpha i - p| minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen. Ein Gitter vom Rang n ist die Menge der ganzzahligen Linerkombinationen von n linear unabhängigen Vektoren im Rm. Unter der Annahme P 6= NP beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der eine kürzeste Gitterbasis bis auf einen Faktor nO(1= log log n) berechnet, wobei die Länge einer Menge von Vektoren durch die maximale Euklidische Länge der Vektoren definiert ist. Weiter zeigen wir, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=plog n unter plausiblen Annahmen nicht möglich ist. Ein simultaner Diophantischer Best Approximations Nenner für reelle Zahlen alpha1, .... , alpha n und Hauptnennerschranke N ist eine natürliche Zahl q mit 1 <= q <= N, so daß maxi ...... minimal ist. Unter der Annahme, daß die Klasse NP keine fast-polynomiellen Algorithmen besitzt, beweisen wir, daß kein Polynomialzeit-Algorithmus existiert, der für gegebene rationale Zahlen alpha1,......, alphan und eine Hauptnennerschranke N einen Nenner ~q mit 1 <= ~q <= f(n)N berechnet, so daß ~q bis auf einen Faktor f(n) = nO(1= log0:5+epsilon n) ein Best Approximations Nenner ist, wobei epsilon > 0 eine beliebige Konstante ist. Wir zeigen, daß eine Verbesserung dieses Resultates bis hin zu einem Faktor n=log n unter plausiblen Annahmen nicht mölich ist. Wir untersuchen die Konsequenzen dieser Resultate zur Konstruktion von im Durchschnitt schwierigen Gitterproblemen.
Es steht außer Zweifel, daß digitale Signaturen schon bald zu unserem Alltag gehören wer- den. Spätestens mit dem Inkrafttreten des Gesetzes zur digitalen Signatur (siehe [BMB]) sind sie zu einem wichtigen Instrument in der Telekommunikation geworden. Dabei kommt der Verwendung von Chipkarten eine wichtige Bedeutung zu: In ihnen lassen sich die sensiblen Daten (z.B. der geheime Schlüssel) auslesesicher aufbewahren; gleichzeitig können sie bequem mitgeführt werden. Aus diesen Gründen erlebt die Verwendung von Chipkarten zur Erzeugung von digitalen Signaturen zur Zeit einen enormen Aufschwung. Problematisch ist jedoch der oft unverhältnismäßig große Berechnungsaufwand für die Erzeugung von digitalen Signaturen. Ziel dieser Arbeit ist es, Methoden zu entwickeln und/oder zu untersuchen, welche die Berechnung digitaler Unterschriften wesentlich beschleunigen. Dabei spiegelt sich die Zweiteilung der in der Praxis hauptsächlich verwendeten Typen von Signaturverfahren in der Struktur der Arbeit wider. Der erste Teil dieser Arbeit untersucht Verfahren zur effizienten Berechnung von RSA-Unterschriften. Dabei entstanden die Untersuchungen in den Abschnitten 3.2.3 und 3.2.4 in Zusammenarbeit mit R. Werchner und der Inhalt der Abschnitte 3.1 - 3.2.4 ist bereits in [MW98] veröffentlicht. Im zweiten Teil entwickeln wir Verfahren zur effizienteren Generierung von Unterschriften, die auf dem diskreten Logarithmus basieren, und untersuchen deren Sicherheit. Dabei entstanden die Untersuchungen in den Abschnitten 4.2 (bis auf 4.2.2) und 4.3.1 in Zusammenarbeit mit C. P. Schnorr und sind teilweise in [MS98] zusammengefaßt. Obwohl diese Arbeit eine mathematische Abhandlung darstellt, versuchen wir, die praktische Anwendung nicht aus den Augen zu verlieren. So orientieren sich die betrachteten Verfahren stets an den durch die verfügbare Technologie gegebenen Rahmenbedingungen. Darüber hinaus richten wir unser Augenmerk weniger auf das asymptotische Verhalten der betrachteten Verfahren, als vielmehr auf konkrete, für die Anwendung relevante Beispiele.
Wir führen eine neue Unterklasse der Fourier Hyperfunktionen mit polynomialen Wachstumsbedingungen ein mit dem Ziel, asymptotische Entwicklungen von Hyperfunktionen studieren zu wollen, wie sie für gewisse Distributionenklassen bekannt sind. Wir entwickeln zuerst die Theorie analytischer Funktionale auf Räumen integrabler Funktionen bezüglich Maßen mit Wachstum O(|Re z|^gamma), wobei gamma in R ist, im Unendlichen. Ein an das berühmte Phragmén-Lindelöf-Prinzip erinnerndes, einfaches analytisches Resultat bildet die Basis der Dualitätstheorie dieser Räume zu Funktionen mit festgelegtem Wachstumstyp. Wir studieren diese Dualität analytischer Funktionale mit Wachstumsbedingungen und unbeschränkten Trägern gründlich in einer Dimension unter Verwendung des von den Fourier Hyperfunktionen her bekannten exponentiell abfallenden Cauchy-Hilbert-Kerns. Daraus ergeben sich Analoga zu den Theoremen von Runge und Mittag-Leffler, die die Grundlage für die Garbentheorie der Hyperfunktionen mit polynomialen Wachstumsbedingungen sind, die wir sodann entwickeln. Die für uns wichtigsten neuen Klassen von Fourier Hyperfunktionen sind die von unendlichem Typ, das heißt solche, die wie eine beliebige Potenz wachsen beziehungsweise schneller als jede Potenz abfallen. In n Dimensionen benutzen wir die Fouriertransformation und Dualität um das Verhältnis dieser temperierten beziehungsweise asymptotischen Hyperfunktionen zu bekannten Distributionenräumen zu studieren. Wir leiten Theoreme vom Paley-Wiener-Typ her, die es uns erlauben, unsere Hyperfunktionen in ein Schema zu ordnen, das Wachstumsordnung und Singularität gegenüberstellt. Wir zeigen, daß dieses Schema eine sinvolle Erweiterung des von Gelfand und Shilow zur Charakterisierung von Testfunktionenräumen eingeführten Schemas der Räume S(alpha,beta) um verallgemeinerte Funktionen ist. Schließlich zeigen wir die Nuklearität der temperierten und asymptotischen Hyperfunktionen. Wir zeigen, daß die asymptotischen Hyperfunktionen genau die Klasse bilden, die Moment-asymptotische Entwicklungen erlauben, wie sie von Estrada et al. für Distributionen betrachtet wurden. Estradas Theorie ist damit ein Spezialfall der unsrigen. Für Hyperfunktionen lassen sich aber dank des Konzeptes der standard definierenden Funktionen die Moment-asymptotischen Entwicklungen als klassische asymptotische Entwicklungen von analytischen Funktionen verstehen. Wir zeigen die einfache Beziehung zwischen der Moment-asymptotischen Entwicklung und der Taylorentwicklung der Fouriertransformierten und benutzen dann ein Resultat von Estrada, um die Vollständigkeit unseres Moment-asymptotischen Schemas abzuleiten. Wir geben genaue Bedingungen für die Moment-Folgen von Hyperfunktionen mit kompaktem Träger an, die kürzlich von Kim et al. gefunden wurden. Die asymptotischen Entwicklungen übertragen wir auf den höherdimensionalen Fall, indem wir die von Kaneko und Takiguchi eingeführte Radontransformation für Hyperfunktionen verwenden. Die wohlbekannte Beziehung zwischen Radon- und Fouriertransformation zeigt wiederum das enge Verhältnis von asymptotischer Entwicklung zur Taylorentwicklung der Fouriertransformierten. Wir benutzen Kims Resultate, um die Moment-Folgen von Hyperfunktionen zu charakterisieren, die von Kugeln mit endlichem Radius getragen werden. Schließlich verwenden wir das Träger-Theorem der Radontransformation, um ein Resultat über das Singularitätenspektrum aus Bedingungen an die Radontransformierte abzuleiten.
Die in Englisch verfasste Dissertation, die unter der Betreuung von Herrn Prof. Dr. H. F. de Groote, Fachbereich Mathematik, entstand, ist der Mathematischen Physik zuzuordnen. Sie behandelt Stonesche Spektren von Neumannscher Algebren, observable Funktionen sowie einige Anwendungen in der Physik. Das abschließende Kapitel liefert eine Verallgemeinerung des Kochen-Specker-Theorems. Stonesche Spektren und observable Funktionen wurden von de Groote eingeführt. Das Stonesche Spektrum einer von Neumann-Algebra ist eine Verallgemeinerung des Gelfand-Spektrums, die observablen Funktionen verallgemeinern die Gelfand-Transformierten. Da de Grootes Ergebnisse zum großen Teil unveröffentlicht sind, folgt nach dem Einleitungskapitel im zweiten Kapitel eine Übersichtsdarstellung dieser Ergebnisse. Das dritte Kapitel behandelt die Stoneschen Spektren endlicher von Neumann-Algebren. Für Algebren vom Typ In wird eine vollständige Charakterisierung des Stoneschen Spektrums entwickelt. Zu Typ-II1-Algebren werden einige Resultate vorgestellt. Das vierte Kapitel liefert. einige einfache Anwendungen des Formalismus auf die Physik. Das fünfte Kapitel gibt erstmals einen funktionalanalytischen Beweis des Kochen-Specker-Theorems und liefert die Verallgemeinerung dieses Satzes, wobei die Situation für alle von Neumann-Algebren geklärt wird.
In der vorliegenden Arbeit beschäftigen wir uns mit der Verallgemeinerung des Satzes von Belyi [B]. Dieser besagt, dass eine Riemannsche Fläche Y genau dann als algebraische Kurve über einem Zahlkörper definiert ist, wenn es auf Y eine nicht-konstante holomorphe Funktion gibt, die über höchstens drei Punkten verzweigt. Die Arbeit gliedert sich in zwei Teile. Wir untersuchen darin jeweils die Verallgemeinerung einer der beiden Implikationen aus dem Satz von Belyi auf Varietäten der Dimension zwei und höher. Im ersten Teil der Arbeit zeigen wir, dass eine n-dimensionale projektive komplex algebraische Varietät über einem Zahlkörper definiert ist, falls sie den Pn (oder eine beliebige projektive über Q definierte Varietät) endlich und höchstens über einem rationalen Divisor verzweigt überlagert. Dazu beschreiben wir im ersten Kapitel den Zusammenhang zwischen Varietäten und komplex analytischen Räumen. Wir zeigen, dass die Kategorie der endlichen algebraischen Überlagerungen einer projektiven komplexen Varietät äquivalent zur Kategorie der endlichen verzweigten analytischen Überlagerungen des assoziierten komplex analytischen Raumes ist. Außerdem erläutern wir den Zusammenhang zwischen topologisch unverzweigten Überlagerungen und deren Algebraisierung, den étalen Morphismen zwischen Varietäten. Im zweiten Kapitel führen wir Definitionskörper und Modulkörper von Varietäten ein. Anschließend untersuchen wir die Operation von Körperautomorphismen s E Aut (C/Q) auf komplexen Varietäten. Im dritten Kapitel zeigen wir zunächst, dass der Modulkörper einer endlichen Überlagerung eines geeigneten Grundraumes ein Zahlkörper ist. Danach stellen wir das Resultat von Derome [D] vor, nachdem es einen Definitionskörper im algebraischen Abschluss des Modulkörpers gibt. Daraus folgern wir die Verallgemeinerung dieser Richtung des Satzes von Belyi. Im zweiten Teil beschäftigen wir uns mit der Frage, wie der Verzweigungsdivisor D im Pn aussehen sollte, damit jede über Q definierte Varietät ein Modell besitzt, dass Pn endlich und nur über D verzweigt überlagert. Im vierten Kapitel stellen eine Heuristik zur Korrespondenz zwischen topologischen Überlagerungen und Körpererweiterungen von Q vor. Daraus leitet sich folgende Vermutung ab: Zu jeder über einem Zahlkörper definierten n-dimensionalen Varietät Y gibt es eine birational äquivalente normale Varietät Y und einen Morphismus f : Y -> Pn, der nur über dem Komplement von M0,n+3 verzweigt. Die Vermutung steht im Einklang mit dem eindimensionalen Satz von Belyi. Alle Modulräume erfüllen die Voraussetzung für die im dritten Kapitel bewiesene Umkehrung. Im letzten Kapitel beschäftigen wir uns mit komplex algebraischen Flächen. Wir zeigen, dass die Vermutung aus dem vierten Kapitel für abelsche Flächen richtig ist. Dieses Ergebnis haben wir gemeinsam mit Horst Hammer (Karlsruhe) erzielt. Anschließend geben wir einen Überblick über weitere Resultate in dieser Richtung. Schließlich beschreiben wir die topologischen Überlagerungen von M0,5 und stellen eine Verallgemeinerung der Dessins d'Enfants vor.
Große Stammbäume
(2003)
Sei T ein kritischer oder subkritischer Galton-Watson Stammbaum (GW-Baum) mit einer Kinderzahlverteilung endlicher oder unendlicher Varianz. Wir sind an der Struktur von T , bedingt darauf, dass T "groß" ist, interessiert. Der klassische sowie naheliegende Zugang ist, T auf eine große Gesamtgröße oder eine große Höhe zu bedingen. In dieser Arbeit werden drei, zum GW-Baum eng verwandte Typen von zufälligen Stammbäumen vorgestellt, deren Analyse aufschlussreiche Einsichten über große GW-Stammbäume liefert. Zur Untersuchung dieser auf große Gesamtgröße bedingten Stammbäume schlagen wir eine Familie von zufälligen, größenverzerrten Bäumen vor, deren auf Größe bedingte Verteilung mit der des, auf gegebener Größe bedingten, Baumes T übereinstimmt. Diese zufälligen Stammbäume besitzen eine einfache probabilistische Struktur, wenn man sie entlang der Ahnenlinien von rein zufällig gezogenen Knoten zerlegt. Die Verwandschaftsstruktur des von den gezogenen Knoten und der Wurzel aufgespannten Teilbaumes hängt im wesentlichen von dem asymptotischen Verhalten der Kinderzahlverteilung ab. Während bei endlicher Varianz diese Teilbäume asymptotisch binär sind, können bei unendlicher Varianz im Limes auch andere Formen auftreten. Wir zeigen, dass diese Teilbäume GW-Bäume bedingt auf ihre Gesamtblätterzahl sind. Mit Hilfe der Zerlegung entlang der Ahnenlinien erhalten wir zudem einen Grenzwertsatz für die reskalierte Gesamtgröße des Baumes mit einer Gamma-Verteilung als Limes. Die Analyse großer Bäume führen wir unter dem Aspekt des Größenverzerrens fort, indem wir eine weitere Familie zufälliger Bäume vorschlagen. Diese erhalten wir durch Größenverzerrung in der n-ten Generationsgröße. Wir werden sehen, dass der dadurch gewonnene zufällige Stammbaum eine ähnliche probabilistische Struktur wie der in der Gesamtgröße größenverzerrte Baum besitzt. Hier beweisen wir mit einfachen Überlegungen Aussagen über die Generation des jüngsten gemeinsamen Vorfahren (MRCA) von uniform aus Generation n gezogenen Knoten, sowie die Struktur des von diesen Knoten aufgespannten Skeletts. Schließlich betrachten wir die in [15] vorgestellte probabilistische Zerlegung des auf Mindesthöhe n bedingten GW-Baumes. Damit werden wir klassische Sätze über die Höhe des MRCA und die Grenzverteilung der reskalierten n-ten Generationsgröße für den Fall einer Kinderzahlverteilung mit unendlicher Varianz auf alternativem und anschaulichem Weg beweisen. Zudem erhalten wir eine Grenzverteilung für die Anzahl der Kinder des MRCA.
We consider the long-time behaviour of spatially extended random populations with locally dependent branching. We treat two classes of models: 1) Systems of continuous-time random walks on the d-dimensional grid with state dependent branching rate. While there are k particles at a given site, a branching event occurs there at rate s(k), and one of the particles is replaced by a random number of offspring (according to a fixed distribution with mean 1 and finite variance). 2) Discrete-time systems of branching random walks in random environment. Given a space-time i.i.d. field of random offspring distributions, all particles act independently, the offspring law of a given particle depending on its position and generation. The mean number of children per individual, averaged over the random environment, equals one The long-time behaviour is determined by the interplay of the motion and the branching mechanism: In the case of recurrent symmetrised individual motion, systems of the second type become locally extinct. We prove a comparison theorem for convex functionals of systems of type one which implies that these systems also become locally extinct in this case, provided that the branching rate function grows at least linearly. Furthermore, the analysis of a caricature model leads to the conjecture that local extinction prevails generically in this case. In the case of transient symmetrised individual motion the picture is more complex: Branching random walks with state dependent branching rate converge towards a non-trivial equilibrium, which preserves the initial intensity, whenever the branching rate function grows subquadratically. Systems of type 1) and systems of type 2) with quadratic branching rate function show very similar behaviour. They converge towards a non-trivial equilibrium if a conditional exponential moment of the collision time of two random walks of an order that reflects the variability in the branching mechanism is finite almost surely. The equilibrium population has finite variance of the local particle number if the corresponding unconditional exponential moment is finite. These results are proved by means of genealogical representations of the locally size-biased population. Furthermore, we compute the threshold values for existence of conditional exponential moments of the collision time of two random walks in terms of the entropy of the transition functions, using tools from large deviations theory. Our results prove in particular that - in contrast to the classical case of independent branching - there is a regime of equilibria with variance of the local number of particles.
Okamoto (Crypto 1992) hat die RSA-Repräsentation als Basis eines gegen aktive Angreifer sicheren Identifikationsschemas eingeführt. Eine RSA- Repräsentation von X E Z * N ist ein Paar (x; r) E Z e x Z * N mit X = g x r e (mod N) für vorgegebenes g E ZN , RSA-Modul N und primen RSA- Exponenten e. Das zugehörige Repräsentationsproblem, also das Auffinden eines Wertes X samt zweier verschiedener Darstellungen, ist äquivalent zum RSA-Problem, der Berechnung einer e-ten Wurzel von g modulo N . Von Brassard, Chaum und Crépeau (Journal Computing System Science, 1988) sowie Damgard (Journal of Cryptology, 1995) stammt eine analoge Konstruktion der Form X = g x r 2 t (mod N) mit x E Z 2 t für den Spezialfall der Blum-Zahlen als Modul N und gegebenes t größer gleich 1, wo die Möglichkeit, zwei verschiedene Repräsentationen zu berechnen, gleichbedeutend zur Zerlegung des Moduls in die Primfaktoren ist. Im ersten Abschnitt der vorliegenden Arbeit verallgemeinern wir dieses Konzept systematisch auf beliebige (RSA-)Module durch die Einführung eines Anpassungsparameters r:= r (N ), so dass X = g x r 2 r t (mod N) mit x E Z 2 t. Basierend auf dieser als Faktorisierungsrepräsentation bezeichneten Darstellung leiten wir Identifikations-, Signatur- und Blinde-Unterschriften-Verfahren her. Im zweiten Teil verwenden wir sowohl RSA- als auch Faktorisierungsrepräsentation als Grundlage sogenannter non-malleable Commitment-Schemata zur Hinterlegung (Verbriefung) einer geheimen Nachricht. Bei dem von Dolev, Dwork und Naor (SIAM Journal on Computing, 2000) eingeführten Begriff der Non-Malleability soll ein Angreifer außer Stande sein, die Hinterlegung einer Nachricht m so abzuändern, dass er diese später dann mit einem in Relation zu m stehenden Wert, man denke zum Beispiel an m 1, aufdecken kann. Von Dolev, Dwork und Naor stammt ein allgemeiner Ansatz zur Konstruktion von non-malleable Commitment-Schemata aufbauend auf einem sogenannten Knowledge-Extraktor. Für die RSA-Darstellung verfügt das von Okamoto entworfene Protokoll als Proof-Of-Knowledge über einen solchen Extraktor, bei dem im Fall der Faktorisierungsrepräsentation von uns entwickelten Verfahren fehlt allerdings der Extraktor. Aus diesem Grund stellen wir mit Hilfe des Chinesischen Restsatzes ein neues, auf Commitments zugeschnittenes Protokoll mit Knowledge-Extraktor vor, das in Verbindung mit der Faktorisierungsrepräsentation ein effizientes Hinterlegungsschema ergibt. Zum Abschluß wird bei einem Commitment- Verfahren mit abgeschwächter Non-Malleability-Eigenschaft von Di Crescenzo, Katz, Ostrovsky und Smith (Eurocrypt 2001) die RSA- durch die Faktorisierungsrepräsentation ersetzt und das Schema vereinfacht.
Informally, commitment schemes can be described by lockable steely boxes. In the commitment phase, the sender puts a message into the box, locks the box and hands it over to the receiver. On one hand, the receiver does not learn anything about the message. On the other hand, the sender cannot change the message in the box anymore. In the decommitment phase the sender gives the receiver the key, and the receiver then opens the box and retrieves the message. One application of such schemes are digital auctions where each participant places his secret bid into a box and submits it to the auctioneer. In this thesis we investigate trapdoor commitment schemes. Following the abstract viewpoint of lockable boxes, a trapdoor commitment is a box with a tiny secret door. If someone knows the secret door, then this person is still able to change the committed message in the box, even after the commitment phase. Such trapdoors turn out to be very useful for the design of secure cryptographic protocols involving commitment schemes. In the first part of the thesis, we formally introduce trapdoor commitments and extend the notion to identity-based trapdoors, where trapdoors can only be used in connection with certain identities. We then recall the most popular constructions of ordinary trapdoor protocols and present new solutions for identity-based trapdoors. In the second part of the thesis, we show the usefulness of trapdoors in commitment schemes. Deploying trapdoors we construct efficient non-malleable commitment schemes which basically guarantee indepency of commitments. Furthermore, applying (identity-based) trapdoor commitments we secure well-known identification protocols against a new kind of attack. And finally, by means of trapdoors, we show how to construct composable commitment schemes that can be securely executed as subprotocols within complex protocols.
In dieser Arbeit werden Darstellungen der Artinschen Zopfgruppen als Gruppen von Automorphismen der Homologie iterativ konstruierter äquivarianter Kettenkomplexe betrachtet. Es werden azyklische Komplexe freier Moduln bzw. freie Auflösungen der ganzen Zahlen für nichtpermutierte Artinsche Zopfgruppen konstruiert, die als iterierte semidirekte Produkte freier Gruppen darstellbar sind. Als Tensorprodukte der freien Auflösungen mit Moduln zu den fraglichen iterierten semidirekten Produkten freier Gruppen erhält man äquivariante Komplexe, deren von Eigenschaften der Koeffizientenmoduln abhängige Homologiegruppen bestimmt werden. Diese Homologiegruppen erlauben Automorphismendarstellungen der (permutierten) Artinschen Zopfgruppe, die gewissermaßen die Artinschen Darstellungen als Automorphismengruppen freier Gruppen iterieren und linearisieren. Insbesondere werden Darstellungen gewonnen, die die bekannten Burau- und Gassner-Darstellungen der Zopfgruppen verallgemeinern und die als Monodromiegruppen verallgemeinerter hypergeometrischer Integrale interpretiert werden können.
In der vorliegenden Arbeit untersuchen wir die Verteilung der Nullstellen Dirichletscher L-Reihen auf oder in der Nähe der kritischen Geraden. Diese Funktionen und ihre Nullstellen stehen im Mittelpunkt des Interesses bei einer Vielzahl klassischer zahlentheoretischer Fragestellungen; beispielsweise besagt die Verallgemeinerte Riemannsche Vermutung, daß sämtliche Nullstellen dieser Funktionen auf der kritischen Geraden liegen. Unsere Ergebnisse gehen unter anderem über die besten bislang bekannten Abschätzungen - für den Anteil der Nullstellen der Dirichletschen L-Reihen, die auf der kritischen Geraden liegen, - für den Anteil einfacher beziehungsweise m-facher Nullstellen sowie - über Nullstellen in der Nähe der kritischen Geraden hinaus. Wir setzen hiermit Arbeiten von A. Selberg, N. Levinson, J. B. Conrey und anderen fort und verallgemeinern Ergebnisse, die für die Riemannsche #-Funktion gültig sind, auf alle Dirichletschen LReihen beziehungsweise verbessern bisherige Resultate. Nach einer ausführlicheren Darstellung der Hintergründe zeigen wir einen Satz über Mittelwerte "geglätteter" L-Reihen, d.h. mit einem geeigneten Dirichlet-Polynom multiplizierte L-Reihen. Solche Mittelwertsätze stellen ein wesentliches Hilfsmittel zur Untersuchung der Nullstellenverteilung dar. Die in unserem Hauptsatz gegebene asymptotische Darstellung dieses Mittelwertes können wir dann nutzen, um die genannten Ergebnisse herzuleiten.