Mathematik
Refine
Year of publication
Document Type
- Article (112)
- Doctoral Thesis (76)
- Preprint (48)
- diplomthesis (39)
- Book (25)
- Report (22)
- Conference Proceeding (18)
- Bachelor Thesis (8)
- Contribution to a Periodical (8)
- Diploma Thesis (8)
Has Fulltext
- yes (377) (remove)
Is part of the Bibliography
- no (377)
Keywords
- Kongress (6)
- Kryptologie (5)
- Mathematik (5)
- Stochastik (5)
- Doku Mittelstufe (4)
- Doku Oberstufe (4)
- Online-Publikation (4)
- Statistik (4)
- Finanzmathematik (3)
- LLL-reduction (3)
Institute
- Mathematik (377) (remove)
[Nachruf] Wolfgang Schwarz
(2013)
Based on the quadratic residuosity assumption we present a non-interactive crypto-computing protocol for the greater-than function, i.e., a non-interactive procedure between two parties such that only the relation of the parties' inputs is revealed. In comparison to previous solutions our protocol reduces the number of modular multiplications significantly. We also discuss applications to conditional oblivious transfer, private bidding and the millionaires' problem.
We propose a fast variant of the Gaussian algorithm for the reduction of two dimensional lattices for the l1-, l2- and l-infinite- norm. The algorithm runs in at most O(nM(B) logB) bit operations for the l-infinite- norm and in O(n log n M(B) logB) bit operations for the l1 and l2 norm on input vectors a, b 2 ZZn with norm at most 2B where M(B) is a time bound for B-bit integer multiplication. This generalizes Schönhages monotone Algorithm [Sch91] to the centered case and to various norms.
We consider versions of the FIND algorithm where the pivot element used is the median of a subset chosen uniformly at random from the data. For the median selection we assume that subsamples of size asymptotic to c⋅nα are chosen, where 0<α≤12, c>0 and n is the size of the data set to be split. We consider the complexity of FIND as a process in the rank to be selected and measured by the number of key comparisons required. After normalization we show weak convergence of the complexity to a centered Gaussian process as n→∞, which depends on α. The proof relies on a contraction argument for probability distributions on càdlàg functions. We also identify the covariance function of the Gaussian limit process and discuss path and tail properties.
Viewing of ambiguous stimuli can lead to bistable perception alternating between the possible percepts. During continuous presentation of ambiguous stimuli, percept changes occur as single events, whereas during intermittent presentation of ambiguous stimuli, percept changes occur at more or less regular intervals either as single events or bursts. Response patterns can be highly variable and have been reported to show systematic differences between patients with schizophrenia and healthy controls. Existing models of bistable perception often use detailed assumptions and large parameter sets which make parameter estimation challenging. Here we propose a parsimonious stochastic model that provides a link between empirical data analysis of the observed response patterns and detailed models of underlying neuronal processes. Firstly, we use a Hidden Markov Model (HMM) for the times between percept changes, which assumes one single state in continuous presentation and a stable and an unstable state in intermittent presentation. The HMM captures the observed differences between patients with schizophrenia and healthy controls, but remains descriptive. Therefore, we secondly propose a hierarchical Brownian model (HBM), which produces similar response patterns but also provides a relation to potential underlying mechanisms. The main idea is that neuronal activity is described as an activity difference between two competing neuronal populations reflected in Brownian motions with drift. This differential activity generates switching between the two conflicting percepts and between stable and unstable states with similar mechanisms on different neuronal levels. With only a small number of parameters, the HBM can be fitted closely to a high variety of response patterns and captures group differences between healthy controls and patients with schizophrenia. At the same time, it provides a link to mechanistic models of bistable perception, linking the group differences to potential underlying mechanisms.
For genus g=2i≥4 and the length g−1 partition μ=(4,2,…,2,−2,…,−2) of 0, we compute the first coefficients of the class of D¯¯¯¯(μ) in PicQ(R¯¯¯¯g), where D(μ) is the divisor consisting of pairs [C,η]∈Rg with η≅OC(2x1+x2+⋯+xi−1−xi−⋯−x2i−1) for some points x1,…,x2i−1 on C. We further provide several enumerative results that will be used for this computation.
For genus g=2i≥4 and the length g−1 partition μ=(4,2,…,2,−2,…,−2) of 0, we compute the first coefficients of the class of D¯¯¯¯(μ) in PicQ(R¯¯¯¯g), where D(μ) is the divisor consisting of pairs [C,η]∈Rg with η≅OC(2x1+x2+⋯+xi−1−xi−⋯−x2i−1) for some points x1,…,x2i−1 on C. We further provide several enumerative results that will be used for this computation.
For genus g=2i≥4 and the length g−1 partition μ=(4,2,…,2,−2,…,−2) of 0, we compute the first coefficients of the class of D¯¯¯¯(μ) in PicQ(R¯¯¯¯g), where D(μ) is the divisor consisting of pairs [C,η]∈Rg with η≅OC(2x1+x2+⋯+xi−1−xi−⋯−x2i−1) for some points x1,…,x2i−1 on C. We further provide several enumerative results that will be used for this computation.
For genus g=2i≥4 and the length g−1 partition μ=(4,2,…,2,−2,…,−2) of 0, we compute the first coefficients of the class of D¯¯¯¯(μ) in PicQ(R¯¯¯¯g), where D(μ) is the divisor consisting of pairs [C,η]∈Rg with η≅OC(2x1+x2+⋯+xi−1−xi−⋯−x2i−1) for some points x1,…,x2i−1 on C. We further provide several enumerative results that will be used for this computation.
We contribute to the foundations of tropical geometry with a view toward formulating tropical moduli problems, and with the moduli space of curves as our main example. We propose a moduli functor for the moduli space of curves and show that it is representable by a geometric stack over the category of rational polyhedral cones. In this framework, the natural forgetful morphisms between moduli spaces of curves with marked points function as universal curves.
Our approach to tropical geometry permits tropical moduli problems—moduli of curves or otherwise—to be extended to logarithmic schemes. We use this to construct a smooth tropicalization morphism from the moduli space of algebraic curves to the moduli space of tropical curves, and we show that this morphism commutes with all of the tautological morphisms.
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.
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.
In this article we use techniques from tropical and logarithmic geometry to construct a non-Archimedean analogue of Teichmüller space T¯g whose points are pairs consisting of a stable projective curve over a non-Archimedean field and a Teichmüller marking of the topological fundamental group of its Berkovich analytification. This construction is closely related to and inspired by the classical construction of a non-Archimedean Schottky space for Mumford curves by Gerritzen and Herrlich. We argue that the skeleton of non-Archimedean Teichmüller space is precisely the tropical Teichmüller space introduced by Chan–Melo–Viviani as a simplicial completion of Culler–Vogtmann Outer space. As a consequence, Outer space turns out to be a strong deformation retract of the locus of smooth Mumford curves in T¯g.
We reconsider estimates for the heat kernel on weighted graphs recently found by Metzger and Stollmann. In the case that the weights satisfy a positive lower bound as well as a finite upper bound, we obtain a specialized lower estimate and a proper generalization of a previous upper estimate. Reviews: Math. Rev. 1979406, Zbl. Math. 0934.46042
The existence of a mean-square continuous strong solution is established for vector-valued Itö stochastic differential equations with a discontinuous drift coefficient, which is an increasing function, and with a Lipschitz continuous diffusion coefficient. A scalar stochastic differential equation with the Heaviside function as its drift coefficient is considered as an example. Upper and lower solutions are used in the proof.
We study the following problem: given x element Rn either find a short integer relation m element Zn, so that =0 holds for the inner product <.,.>, or prove that no short integer relation exists for x. Hastad, Just Lagarias and Schnorr (1989) give a polynomial time algorithm for the problem. We present a stable variation of the HJLS--algorithm that preserves lower bounds on lambda(x) for infinitesimal changes of x. Given x \in {\RR}^n and \alpha \in \NN this algorithm finds a nearby point x' and a short integer relation m for x'. The nearby point x' is 'good' in the sense that no very short relation exists for points \bar{x} within half the x'--distance from x. On the other hand if x'=x then m is, up to a factor 2^{n/2}, a shortest integer relation for \mbox{x.} Our algorithm uses, for arbitrary real input x, at most \mbox{O(n^4(n+\log \alpha))} many arithmetical operations on real numbers. If x is rational the algorithm operates on integers having at most \mbox{O(n^5+n^3 (\log \alpha)^2 + \log (\|q x\|^2))} many bits where q is the common denominator for x.
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.
Therapy evasion – and subsequent disease progression – is a major challenge in current oncology. An important role in this context seems to be played by various forms of cancer cell dormancy. For example, therapy-induced dormancy, over short timescales, can create serious obstacles to aggressive treatment approaches such as chemotherapy, and long-term dormancy may lead to relapses and metastases even many years after an initially successful treatment. The underlying dormancy-related mechanisms are complex and highly diverse, so that the analysis even of basic patterns of the population-level consequences of dormancy requires abstraction and idealization, as well as the identification of the relevant specific scenarios.
In this paper, we focus on a situation in which individual cancer cells may switch into and out of a dormant state both spontaneously as well as in response to treatment, and over relatively short time-spans. We introduce a mathematical ‘toy model’, based on stochastic agent-based interactions, for the dynamics of cancer cell populations involving individual short-term dormancy, and allow for a range of (multi-drug) therapy protocols. Our analysis shows that in our idealized model, even a small initial population of dormant cells can lead to therapy failure under classical (and in the absence of dormancy successful) single-drug treatments. We further investigate the effectiveness of several multidrug regimes (manipulating dormant cancer cells in specific ways) and provide some basic rules for the design of (multi-)drug treatment protocols depending on the types and parameters of dormancy mechanisms present in the population.
The main subject of this survey are Belyi functions and dessins d'enfants on Riemann surfaces. Dessins are certain bipartite graphs on 2-mainfolds defining there are conformal and even an algebraic structure. In principle, all deeper properties of the resulting Riemann surfaces or algebraic curves should be encoded in these dessins, but the decoding turns out to be difficult and leads to many open problems. We emphasize arithmetical aspects like Galois actions, the relation to the ABC theorem in function filds and arithemtic questions in uniformization theory of algebraic curves defined over number fields.
Gleichungen mit mehreren Unbekannten zu lösen, üben Schüler schon in der Mittelstufe. Für die einen ist es eine spannende mathematische Knobelei, für die anderen eher Quälerei. Doch den wenigsten ist bewusst, wie viele Leben dadurch jeden Tag gerettet werden. Die moderne medizinische Bildgebung beruht darauf, sehr viele Gleichungen nach sehr vielen Unbekannten aufzulösen.
We consider Schwarz maps for triangles whose angles are rather general rational multiples of pi. Under which conditions can they have algebraic values at algebraic arguments? The answer is based mainly on considerations of complex multiplication of certain Prym varieties in Jacobians of hypergeometric curves. The paper can serve as an introduction to transcendence techniques for hypergeometric functions, but contains also new results and examples.
Im Rahmen dieser Arbeit wird der aktuelle Stand auf dem Gebiet des Lokalen Lovász Lemmas (LLL) beschrieben und ein Überblick über die Arbeiten zu konstruktiven Beweisen und Anwendungen gegeben. Ausgehend von Jószef Becks Arbeit zu einer algorithmischen Herangehensweise, haben sich in den letzten Jahren im Umfeld von Moser und Tardos und ihren Arbeiten zu einem konstruktiven Beweis des LLL eine erneute starke Beschäftigung mit dem Thema und eine Fülle von Verbesserungen entwickelt.
In Kapitel 1 wird als Motivation eine kurze Einführung in die probabilistische Methode gegeben. Mit der First- und Second Moment Method werden zwei einfache Vorgehensweisen vorgestellt, die die Grundidee dieses Beweisprinzips klar werden lassen. Von Paul Erdős eröffnet, beschreibt es Wege, Existenzbeweise in nicht-stochastischen Teilgebieten der Mathematik mithilfe stochastischer Überlegungen zu führen. Das Lokale Lemma als eine solche Überlegung entstammt dieser Idee.
In Kapitel 2 werden verschiedene Formen des LLL vorgestellt und bewiesen, außerdem wird anhand einiger Anwendungsbeispiele die Vorgehensweise bei der Verwendung des LLL veranschaulicht.
In Kapitel 3 werden algorithmische Herangehensweisen beschrieben, die geeignet sind, von der (mithilfe des LLL gezeigten) Existenz gewisser Objekte zur tatsächlichen Konstruktion derselben zu gelangen.
In Kapitel 4 wird anhand von Beispielen aus dem reichen Schatz neuerer Veröffentlichungen gezeigt, welche Bewegung nach der Arbeit von Moser und Tardos entstanden ist. Dabei beleuchtet die Arbeit nicht nur einen anwendungsorientierten Beitrag von Haeupler, Saha und Srinivasan, sondern auch einen Beitrag Terence Taos, der die Beweistechnik Mosers aus einem anderen Blickwinkel beleuchtet.
We determine that the continuous-state branching processes for which the genealogy, suitably time-changed, can be described by an autonomous Markov process are precisely those arising from $\alpha$-stable branching mechanisms. The random ancestral partition is then a time-changed $\Lambda$-coalescent, where $\Lambda$ is the Beta-distribution with parameters $2-\alpha$ and $\alpha$, and the time change is given by $Z^{1-\alpha}$, where $Z$ is the total population size. For $\alpha = 2$ (Feller's branching diffusion) and $\Lambda = \delta_0$ (Kingman's coalescent), this is in the spirit of (a non-spatial version of) Perkins' Disintegration Theorem. For $\alpha =1$ and $\Lambda$ the uniform distribution on $[0,1]$, this is the duality discovered by Bertoin & Le Gall (2000) between the norming of Neveu's continuous state branching process and the Bolthausen-Sznitman coalescent.
We present two approaches: one, exploiting the `modified lookdown construction', draws heavily on Donnelly & Kurtz (1999); the other is based on direct calculations with generators.
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.
In this paper we deal with an implementation as well as numerical experiments for the coupling of interior and exterior problems of the elastodynamic wave equation with transparent boundary conditions in 3D as described in a previous paper by this author. In more detail, the FEM‐BEM‐coupling as well as the time discretization by using leapfrog and convolution quadrature is considered. Our aim is to provide an insight into the necessary steps of the implementation. Based on this, we present numerical experiments for a non‐convex domain and analyze the errors.
Several novel imaging and non-destructive testing technologies are based on reconstructing the spatially dependent coefficient in an elliptic partial differential equation from measurements of its solution(s). In practical applications, the unknown coefficient is often assumed to be piecewise constant on a given pixel partition (corresponding to the desired resolution), and only finitely many measurement can be made. This leads to the problem of inverting a finite-dimensional non-linear forward operator F: D(F)⊆Rn→Rm , where evaluating ℱ requires one or several PDE solutions.
Numerical inversion methods require the implementation of this forward operator and its Jacobian. We show how to efficiently implement both using a standard FEM package and prove convergence of the FEM approximations against their true-solution counterparts. We present simple example codes for Comsol with the Matlab Livelink package, and numerically demonstrate the challenges that arise from non-uniqueness, non-linearity and instability issues. We also discuss monotonicity and convexity properties of the forward operator that arise for symmetric measurement settings.
This text assumes the reader to have a basic knowledge on Finite Element Methods, including the variational formulation of elliptic PDEs, the Lax-Milgram-theorem, and the Céa-Lemma. Section 3 also assumes that the reader is familiar with the concept of Fréchet differentiability.
We analyse a continued fraction algorithm (abbreviated CFA) for arbitrary dimension n showing that it produces simultaneous diophantine approximations which are up to the factor 2^((n+2)/4) best possible. Given a real vector x=(x_1,...,x_{n-1},1) in R^n this CFA generates a sequence of vectors (p_1^(k),...,p_{n-1}^(k),q^(k)) in Z^n, k=1,2,... with increasing integers |q^{(k)}| satisfying for i=1,...,n-1 | x_i - p_i^(k)/q^(k) | <= 2^((n+2)/4) sqrt(1+x_i^2) |q^(k)|^(1+1/(n-1)) By a theorem of Dirichlet this bound is best possible in that the exponent 1+1/(n-1) can in general not be increased.
The synchronization of neuronal firing activity is considered an important mechanism in cortical information processing. The tendency of multiple neurons to synchronize their joint firing activity can be investigated with the 'unitary event' analysis (Grün, 1996). This method is based on the nullhypothesis of independent Bernoulli processes and can therefore not tell whether coincidences observed between more than two processes can be considered "genuine" higher- order coincidences or whether they might be caused by coincidences of lower order that coincide by chance ("chance coincidences"). In order to distinguish between genuine and chance coincidences, a parametric model of independent interaction processes (MIIP) is presented. In the framework of this model, Maximum-Likelihood estimates are derived for the firing rates of n single processes and for the rates with which genuine higher order correlations occur. The asymptotic normality of these estimates is used to derive their asymptotic variance and in order to investigate whether higher order coincidences can be considered genuine or whether they can be explained by chance coincidences. The empirical test power of this procedure for n=2 and n=3 processes and for finite analysis windows is derived with simulations and compared to the asymptotic values. Finally, the model is extended in order to allow for the analysis of correlations that are caused by jittered coincidences.
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.
Given a real vector alpha =(alpha1 ; : : : ; alpha d ) and a real number E > 0 a good Diophantine approximation to alpha is a number Q such that IIQ alpha mod Zk1 ", where k \Delta k1 denotes the 1-norm kxk1 := max 1id jx i j for x = (x1 ; : : : ; xd ). Lagarias [12] proved the NP-completeness of the corresponding decision problem, i.e., given a vector ff 2 Q d , a rational number " ? 0 and a number N 2 N+ , decide whether there exists a number Q with 1 Q N and kQff mod Zk1 ". We prove that, unless ...
Approximating Perpetuities
(2006)
A perpetuity is a real valued random variable which is characterised by a distributional fixed-point equation of the form X=AX+b, where (A,b) is a vector of random variables independent of X, whereas dependencies between A and b are allowed. Conditions for existence and uniqueness of solutions of such fixed-point equations are known, as is the tail behaviour for most cases. In this work, we look at the central area and develop an algorithm to approximate the distribution function and possibly density of a large class of such perpetuities. For one specific example from the probabilistic analysis of algorithms, the algorithm is implemented and explicit error bounds for this approximation are given. At last, we look at some examples, where the densities or at least some properties are known to compare the theoretical error bounds to the actual error of the approximation. The algorithm used here is based on a method which was developed for another class of fixed-point equations. While adapting to this case, a considerable improvement was found, which can be translated to the original method.
The purpose of the present paper is to explain the fake projective plane constructed by J. H. Keum from the point of view of arithmetic ball quotients. Beside the ball quotient associated with the fake projective plane, we also analize two further naturally related ball quotients whose minimal desingularizations lead to two elliptic surfaces, one already considered by J. H. Keum as well as the one constructed by M. N. Ishida in terms of p-adic uniformization.
2000 Mathematics Subject Classification: 11F23,14J25,14J27
Der Hoppe-Baum ist eine zufällig wachsende, diskrete Baumstuktur, wobei die stochastische Dynamik durch die Entwicklung der Hoppe Urne wie folgt gegeben ist: Die ausgezeichnete Kugel mit der die Hoppe Urne startet entspricht der Wurzel des Hoppe Baumes. In der Hoppe Urne wird diese Kugel mit Wahrscheinlichkeit proportional zu einem Parameter theta>0 gezogen, alle anderen Kugeln werden mit Wahrscheinlichkeit proportional zu 1 gezogen. Wann immer eine Kugel gezogen wird, wird sie zusammen mit einer neuen Kugel in die Urne zurückgelegt, was in unserem Baum dem Einfügen eines neuen Kindes an den gezogenen Knoten entspricht. Im Spezialfall theta=1 erhält man einen zufälligen rekursiven Baum.
In der Arbeit werden Erwartungswerte, Varianzen und Grenzwertsätze für Tiefe, Höhe, Pfadlänge und die Anzahl der Blätter gegeben.
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.
We introduce algorithms for lattice basis reduction that are improvements of the famous L3-algorithm. If a random L3-reduced lattice basis b1,b2,...,bn is given such that the vector of reduced Gram-Schmidt coefficients ({µi,j} 1<= j< i<= n) is uniformly distributed in [0,1)n(n-1)/2, then the pruned enumeration finds with positive probability a shortest lattice vector. We demonstrate the power of these algorithms by solving random subset sum problems of arbitrary density with 74 and 82 many weights, by breaking the Chor-Rivest cryptoscheme in dimensions 103 and 151 and by breaking Damgard's hash function.
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.
In der vorliegenden Arbeit werden Aspekte autonomer und nichtautonomer dynamischer Systeme behandelt, wobei Attraktoren und verwandte Objekte eine wichtige Rolle spielen werden. Zunächst findet man in einem Kapitel über dynamische Systeme die Definition der grundlegenden Begriffe Attraktor, Repeller und Schiefproduktfluss, gefolgt von zwei hinreichenden Bedingungen für die Existenz von Attraktoren. Mit den Attraktoren und Repellern können dann im nächsten Kapitel Morsemengen eingeführt werden. Dadurch kann das Verhalten eines dynamischen Systems qualitativ beschrieben werden. Des weiteren wird auf die Bedeutung der Kettenrekurrenzmenge für die Morsemengen eingegangen. Im Kapitel über Kontrolltheorie wird, nach einer kurzen Einführung in dieses Gebiet, gezeigt, dass der dort definierte Lift einer Kettenkontrollmenge unter gewissen Voraussetzungen eine Morsemenge ist. Im letzten Kapitel geht es um Pullback-Attraktoren, die unter den angegebenen Bedingungen als Attraktoren für den Schiefproduktfluss interpretiert werden können.
Die Mathematik ist gleichermaßen eine Kulturwissenschaft mit langer Tradition als auch treibende Kraft hinter vielen modernen Technologien und damit Schlüsseldisziplin des Informationszeitalters. Zum einen zielt die Mathematik darauf ab, abstrakte Strukturen und ihre Zusammenhänge zu verstehen; zum anderen entwickelt sie kraftvolle Methoden, um Frage- und Problemstellungen in zahlreichen Wissenschaftsdisziplinen zu behandeln. Moderne Anwendungen der Mathematik liegen beispielsweise in den Bereichen der Datensicherheit und -kompression, der Verkehrssteuerung, der Bewertung und Optimierung von Finanzinstrumenten oder der medizinischen Operationsplanung.
In dieser Broschüre stellen wir Ihnen das Profil der Frankfurter Mathematik in Forschung und Lehre sowie speziell die Studiengänge
• Bachelor Mathematik
• Master Mathematik
vor. An der Goethe-Universität ist es auch möglich, Mathematik auf Lehramt (L1, L2, L3, L5) zu studieren. ...
In dem Artikel ,,Zur Axiomatik der Mengenlehre" habe ich die Axiome, die sich mit den Gebieten der Äquivalenz, der Mengenteilung und Mengenuergleichung beschäftigen, einer Erörterung unterzogen. An zwei Resultate dieses Artikels knüpfe ich hier an. Erstens einmal, da die in ihm durchgeführten Untersuchungen auf die Elemente der Mengen gar nicht eingehen, so stellen sie, allgemein gesprochen, axiomatische Betrachtungen über Größen und Größenbeziehungen dar, an denen die Mengen ja Teil haben; und zweitens hatte eine der dort analysierten Beziehungen den Gedanken nahegelegt, auch Größen entgegengesetzter Art (resp. Mengen von zweierlei Art von Elementen) in Betracht zu ziehen, und auf sie die oben genannten Operationen auszudehnen. Hier nun gebe ich im folgenden einige Ergänzungen. Bereits a. a. O.war bemerkt worden, daß es naturgemäß der Untersuchung bedarf, ob für die so charakterisierten Mengen die weiteren allgemeinen Sätze der Cantorschen Theorie in Kraft bleiben. Inzwischen hat mir Herr A. Fränkel mitgetelt, daß für das von mir konstruierte Beispiel schon ein Teil der in meinem Artikel zugrunde gelegten Axiome versagt; und zwar ein Teil der Axiome über Teilmengen. Über Teilmengen habe ich zwei Axiome an die Spitze gestellt. ......
Diese Arbeit beschäaftigt sich mit den Eigenschaften dynamischer Systeme, die in Form von autonomen Differentialgleichungen vorliegen. Genauer: Das Langzeitverhalten dieser dynamischen Systeme soll untersucht werden. Es läßtt sich beschreiben durch für das jeweilige System charakteristische Mengen, die attrahierenden Mengen und deren Einzugsbereiche. Attrahierende Mengen sind bezüglich eines dynamischen Systems invariante Mengen, die Trajektorien des dynamischen Systems, die in ihrer Umgebung starten, anziehen. Der Einzugsbereich einer attrahierenden Menge ist die Menge aller Punkte, die von der attrahierenden Menge angezogen werden. Betrachtet werden Systeme, die von einer Eingangsfunktion abhängen. Diese Eingangsfunktion kann je nach Zusammenhang eine Störung des dynamischen Systems oder eine Kontrolle desselben darstellen. Werden Störungen betrachtet, so sind Eigenschaften des dynamischen Systems, die für alle Eingangsfunktionen gelten, zu untersuchen. Diese werden in dieser Arbeit als starke Eigenschaften bezeichnet. Werden Kontrollen betrachtet, sind Eigenschaften des dynamischen Systems, die nur für mindestens eine Eingangsfunktion erfüllt sind, zu untersuchen. Sie werden hier als schwache Eigenschaften bezeichnet. Man betrachte beispielsweise einen Punkt, der zu einer invarianten Menge gehört. Zu jeder Eingangsfunktion gibt es eine zugehörige Trajektorie, die an diesem Punkt startet. Starke Invarianz bedeutet, daß keine dieser Trajektorien jemals die invariante Menge verläßt, schwache Invarianz, da mindestens eine dieser Trajektorien niemals die invariante Menge verläßt. Der Schwerpunkt dieser Arbeit liegt auf der Untersuchung der schwachen Einzugsbereiche. Sie lassen sich nur in Ausnahmefällen durch theoretische Überlegungen finden. Daher ist es von Nutzen, diese Mengen numerisch zu berechnen. Hier soll deshalb die benötigte Theorie bereitgestellt werden, um schwache Einzugsbereiche mit einem Unterteilungsalgorithmus anzunähern. Ein Unterteilungsalgorithmus dient allgemein dazu, innerhalb einer vorgegebenen Grundmenge eine Menge, die eine bestimmte Eigenschaft hat, zu finden. Die Idee eines solchen Algorithmus ist es einfach, die Grundmenge in "Zellen" zu unterteilen und für jede dieser Zellen zu prüfen, ob sie ganz, gar nicht oder teilweise zur gesuchten Menge gehört. Gehört eine Zelle nur teilweise zur gesuchten Menge, so wird sie weiter unterteilt und für die "Teilzellen" erneut entschieden, ob sie zur gesuchten Menge gehören. Für die Berechnung eines schwachen Einzugsbereiches bedeutet dies, daß für jede Zelle überprüft werden muß, ob es eine Kontrollfunktion gibt, mit deren Hilfe Trajektorien der betrachteten Differentialgleichung, die innerhalb der Zelle starten, in eine gegebene schwach attrahierende Menge (bzw. eine passend gewählte Umgebung dieser Menge) gesteuert werden können.
Black box cryptanalysis applies to hash algorithms consisting of many small boxes, connected by a known graph structure, so that the boxes can be evaluated forward and backwards by given oracles. We study attacks that work for any choice of the black boxes, i.e. we scrutinize the given graph structure. For example we analyze the graph of the fast Fourier transform (FFT). We present optimal black box inversions of FFT-compression functions and black box constructions of collisions. This determines the minimal depth of FFT-compression networks for collision-resistant hashing. We propose the concept of multipermutation, which is a pair of orthogonal latin squares, as a new cryptographic primitive that generalizes the boxes of the FFT. Our examples of multipermutations are based on the operations circular rotation, bitwise xor, addition and multiplication.
Let b1, . . . , bm 2 IRn be an arbitrary basis of lattice L that is a block Korkin Zolotarev basis with block size ¯ and let ¸i(L) denote the successive minima of lattice L. We prove that for i = 1, . . . ,m 4 i + 3 ° 2 i 1 ¯ 1 ¯ · kbik2/¸i(L)2 · ° 2m i ¯ 1 ¯ i + 3 4 where °¯ is the Hermite constant. For ¯ = 3 we establish the optimal upper bound kb1k2/¸1(L)2 · µ3 2¶m 1 2 1 and we present block Korkin Zolotarev lattice bases for which this bound is tight. We improve the Nearest Plane Algorithm of Babai (1986) using block Korkin Zolotarev bases. Given a block Korkin Zolotarev basis b1, . . . , bm with block size ¯ and x 2 L(b1, . . . , bm) a lattice point v can be found in time ¯O(¯) satisfying kx vk2 · m° 2m ¯ 1 ¯ minu2L kx uk2.
We generalize the concept of block reduction for lattice bases from l2-norm to arbitrary norms. This extends the results of Schnorr. We give algorithms for block reduction and apply the resulting enumeration concept to solve subset sum problems. The deterministic algorithm solves all subset sum problems. For up to 66 weights it needs in average less then two hours on a HP 715/50 under HP-UX 9.05.
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.