Browsing by study line "Matematiikka"

This thesis provides a program to compute minimal values of polynomials of degree two to get a transcendence measure for e, Napier’s (Neper’s) number. This is an indication of how close to zero some non-zero integer coefficient polynomial can come at e: Since e is transcendental, no such polynomial can actually attain zero. The thesis concentrates on the case of second degree polynomials. The program is written in the R5RS dialect of the programming language Scheme, a reasonably modern LISP version that offers integer and rational arithmetic only limited by the memory. The program is validated by comparison to results computed by hand, using another programming language, J. The program was also rewritten in the programming language C, providing the relevant rational number arithmetic by the library gmp. Performance characteristics of the programs are briefly compared. To appoximate the needed value of e, the programs use continued fractions. Relevant mathematical background for the subject is presented. Symmetries of the grid that represents the polynomial coefficients are used to speed up the computation: The symmetry with respect to the origin effectively halves the number of polynomial evaluations needed. The others employed are interesting but less significant. The idea came from a description of a chess endgame program of Ken Thompson by Jon Bentley, although it is likely to be older. These lead to employing the concept of a layer of polynomials with integer coefficients, the border of a punctured grid, in a sense. Layers turned out to rather nicely fit the handling of the accuracy requirements for e. The complexity of the program is still bounded from below by the number of points in the grid of polynomials, partitioned by the layers, making it bounded from below by a second degree polynomial in H, Omega(H²), where H is the natural number bounding the absolute values of the coefficients of the second and first power of e in the polynomial. The program is reasonably easily changed to handle any transcendental number other than e, in particular, if there is a convenient continued fraction to compute approximations to the number. Strictly speaking, the program does not compute the full transcendence measure, that is, a safe upper bound for each integer coefficient polynomial considered, but if this larger output is actually needed, only a minor change in the program is required.

This thesis surveys the vast landscape of uncertainty principles of the Fourier transform. The research of these uncertainty principles began in the mid 1920’s following a seminal lecture by Wiener, where he first gave the remark that condenses the idea of uncertainty principles: "A function and its Fourier transform cannot be simultaneously arbitrarily small". In this thesis we examine some of the most remarkable classical results where different interpretations of smallness is applied. Also more modern results and links to active fields of research are presented.We make great effort to give an extensive list of references to build a good broad understanding of the subject matter.Chapter 2 gives the reader a sufficient basic theory to understand the contents of this thesis. First we talk about Hilbert spaces and the Fourier transform. Since they are very central concepts in this thesis, we try to make sure that the reader can get a proper understanding of these subjects from our description of them. Next, we study Sobolev spaces and especially the regularity properties of Sobolev functions. After briefly looking at tempered distributions we conclude the chapter by presenting the most famous of all uncertainty principles, Heisenberg’s uncertainty principle.In chapter 3 we examine how the rate of decay of a function affects the rate of decay of its Fourier transform. This is the most historically significant form of the uncertainty principle and therefore many classical results are presented, most importantly the ones by Hardy and Beurling. In 2012 Hedenmalm gave a beautiful new proof to the result of Beurling. We present the proof after which we briefly talk about the Gaussian function and how it acts as the extremal case of many of the mentioned results.In chapter 4 we study how the support of a function affects the support and regularity of its Fourier transform. The magnificent result by Benedicks and the results following it work as the focal point of this chapter but we also briefly talk about the Gap problem, a classical problem with recent developments.Chapter 5 links density based uncertainty principle to Fourier quasicrystals, a very active field of re-search. We follow the unpublished work of Kulikov-Nazarov-Sodin where first an uncertainty principle is given, after which a formula for generating Fourier quasicrystals, where a density condition from the uncertainty principle is used, is proved. We end by comparing this formula to other recent formulas generating quasicrystals.

Tässä tutkielmassa esitellään lyhyesti PCP-teoreema, minkä jälkeen tutkielmassa pala palalta käydään läpi teoreeman todistamiseen tarvittavia työkaluja. Tutkielman lopussa todistetaan PCP-teoreema. Vaativuusluokka PCP[O(log n), O(1)] sisältää ne ongelmat, joilla on olemassa todistus, josta vakio määrän bittejä lukien probabilistinen Turingin kone kykenee ratkaisemaan ongelman käyttäen samalla vain logaritmisen määrän satunnaisuutta suhteessa syötteen kokoon. PCP-teoreema väittää vaativuusluokan NP kuuluvan vaativuusluokkaan PCP[O(log n), O(1)]. Väritys on funktio, joka yhdistää kuhunkin joukon muuttujaan jonkin symbolin. Rajoite joillekin muuttujille on lista symboleista, joita rajoite sallii asetettavan muuttujille. Jos väritys asettaa muuttujille vain rajoitteen sallimia symboleja, rajoite on tyytyväinen väritykseen. Optimointi-ongelmat koskevat sellaisten väritysten etsimistä, että mahdollisimman moni rajoite joukosta rajoitteita on tyytyväinen väritykseen. PCP-teoreemalla on yhteys optimointi-ongelmiin, ja tätä yhteyttä hyödyntäen tutkielmassa todistetaan PCP-teoreema. Tutkielma seuraa I. Dinurin vastaavaa todistusta vuoden 2007 artikkelista The PCP Theorem by Gap Amplification. Rajoiteverkko on verkko, jonka kuhunkin kaareen liittyy jokin rajoite. Rajoiteverkkoon liittyy lisäksi aakkosto, joka sisältää ne symbolit, joita voi esiintyä verkon rajoitteissa ja värityksissä. Tutkielman päälauseen avulla kyetään kasvattamaan rajoiteverkossa olevien värityksiin tyytymättömien rajoitteiden suhteellista osuutta. Päälause takaa, että verkon koko säilyy samassa kokoluokassa, ja että verkon aakkoston koko ei muutu. Lisäksi jos verkon kaikki rajoitteet ovat tyytyväisiä johonkin väritykseen, päälauseen tuottaman verkon kaikki rajoitteet ovat edelleen tyytyväisiä johonkin väritykseen. Päälause koostetaan kolmessa vaiheessa, joita kutakin vastaa tutkielmassa yksi osio. Näistä ensimmäisessä, tutkielman osiossa 4, verkon rakenteesta muovataan sovelias seuraavia osioita varten. Toisessa vaiheessa, jota vastaa osio 6, verkon kävelyitä hyödyntäen kasvatetaan tyytymättömien rajoitteiden lukumäärää, mutta samalla verkon aakkosto kasvaa. Kolmannessa vaiheessa, osiossa 5, aakkoston koko saadaan pudotettua kolmeen sopivan algoritmin avulla. Osiossa 7 kootaan päälause ja todistetaan lausetta toistaen PCP-teoreema.

In the thesis ”P-Fredholmness of Band-dominated Operators, and its Equivalence to Invertibility of Limit Operators and the Uniform Boundedness of Their Inverses”, we present the generalization of the classical Fredholm-Riesz theory with respect to a sequence of approximating projections on direct sums of spaces. The thesis is a progessive introduction to understanding and proving the core result in the generalized Fredholm-Riesz theory, which is stated in the title. The stated equivalence has been further improved and it can be generalized further by omitting either the initial condition of richness of the operator or the uniform boundedness criterion. Our focal point is on the elementary form of this result. We lay the groundwork for the classical Fredholm-Riesz theory by introducing compact operators and defining Fredholmness as invertibility on modulo compact operators. Thereafter we introduce the concept of approximating projections in infinite direct sums of Banach spaces, that is we operate continuous operators with a sequence of projections which approach the identity operator in the limit and examine whether we have convergence in the norm sense. This method yields us a way to define P-compactness, P-strong converngence and finally PFredholmness. We introduce the notion of limit operators operators by first shifting, then operating and then shifting back an operator with respect to an element in a sequence and afterwards investigating what happens in the P-strong limit of this sequence. Furthermore we define band-dominated operators as uniform limits of linear combinations of simple multiplication and shift operators. In this subspace of operators we prove that indeed for rich operators the core result holds true.

This thesis is motivated by the following questions: What can we say about the set of primes p for which the equation f(x) = 0 (mod p) is solvable when f is (i) a polynomial or (ii) of the form a^x - b? Part I focuses on polynomial equations modulo primes. Chapter 2 focuses on the simultaneous solvability of such equations. Chapter 3 discusses classical topics in algebraic number theory, including Galois groups, finite fields and the Artin symbol, from this point of view. Part II focuses on exponential equations modulo primes. Artin's famous primitive root conjecture and Hooley's conditional solution is discussed in Chapter 4. Tools on Kummer-type extensions are given in Chapter 5 and a multivariable generalization of a method of Lenstra is presented in Chapter 6. These are put to use in Chapter 7, where solutions to several applications, including the Schinzel-Wójcik problem on the equality of orders of integers modulo primes, are given.

The Ising model is a classic model in statistical physics. Originally intended to model ferromagnetism, it has proven to be of great interest to mathematicians and physicists. In two dimensions it is sufficiently complex to describe interesting phenomena while still remaining analytically solvable. The model is defined upon a graph, with a random variable, called a spin, on each vertex. Other random variables may be defined as functions of spins. A classic problem of interest is the correlation of these random variables. A continuum analogue of the Ising model is possible through considering the scaling limit of the model, as the graph taken to approximate some domain e.g. in the complex plane or a torus. The core of this work is an exposition upon one method of calculating correlations of a random variable called a fermion defined in terms of spins and disorder random variables. The method is called Bosonization and associates correlations of some random variables to correlations of the Gaussian Free Field (GFF). The GFF is a random distribution, which approximately functions as a gaussian random variable whose covariance structure is given by Green's function. A result known as the Pfaffian-Hafnian identity is covered, to provide an example of an identity which may be derived using Bosonization on a continuum planar Ising model. A similar result is also presented on the Torus, using elliptic functions. These results are not original, but we present the only -- to us -- known explicit proofs based on hints from others. In the latter half of the work, Bosonization is approached using Random Current representation. Random currents give weights to each edge of the graph of the Ising model. Two other models are introduced: Alternating flows and the Dimer model. There are equivalence relations between the configuration of the Ising model, the Nesting Field of a random current and the height functions of an alternating flow and a dimer cover. Using these, correlations of random variables of the Ising model are given in terms of the height function of the Dimer model. The height function of the Dimer model is a discrete analogue of the GFF.

In this thesis we prove a short time asymptotic formula for a path integral solution to the Fokker Planck heat equation on a Riemannian manifold. The result is inspired by multiple developments regarding the theory of stochastic differential equations on a Riemannian manifold. Most notably the papers by Itô (1962) which describes the stochastic differential equation, Graham (1985) which describes the probabilistic time development of the stochastic differential equation via a path integral and Anderson and Driver (1999) which proves that Graham's path integral converges to the correct notion of probability. The starting point of the thesis is a paper by R. Graham (1985) where a path integral formula for the solution of the heat equation on a Riemannian manifold is given in terms of a stochastic differential equation in Itô sense. The path integral formula contains an integrand of the exponential of an action function. The action function is defined by the given stochastic differential equation and additional integration variables denoted as the momenta of the paths appearing in the integral. The path integral is defined as the time continuum limit of a product of integrals on a discrete time lattice. The result obtained in this thesis is proven by considering the saddle point approximation of the action appearing in the finite version of Graham's path integral formula. The saddle point approximation gives a power series approximation of the action up to the second order by taking the first and second variations of the action and setting the first variation as zero. We say that the saddle point approximation is evaluated along the critical path of the action which is defined by taking the first variation as zero. The second variation of the action is called the Hessian matrix. With the saddle point approximation of the action, we obtain an asymptotic formula of the path integral which contains the exponential of the action evaluated along the critical path and the determinant of the Hessian. The main part of the proof is the evaluation of the determinant of the Hessian in the continuum limit. To this end we prove a finite dimensional version of a theorem due to R. Forman (1987), called Forman's theorem, which allows us to calculate the ratio of determinants of the Hessian parametrized by two different boundary conditions as a ratio of finite dimensional determinants. We then show that in the continuum limit the ratio of determinants of the Hessian can be written in terms of the Jacobi ow. With the Forman's theorem we then get the short time asymptotic formula by evaluating the determinants on a short time interval.

Sobolev functions generalize the concept of differentiability for functions beyond classical settings. The spaces of Sobolev functions are fundamental in mathematics and physics, particularly in the study of partial differential equations and functional analysis. This thesis provides an overview of construction of an extension operator on the space of Sobolev functions on a locally uniform domain. The primary reference is Luke Rogers' work "A Degree-Independent Sobolev Extension Operator". Locally uniform domains satisfy certain geometric properties, for example there are not too thin cusps. However locally uniform domains can possess highly non-rectifiable boundaries. For instance, the interior of the Koch snowflake represents a locally uniform domain with a non-rectifiable boundary. First we will divide the interior points of the complement of our locally uniform domain into dyadic cubes and use a collection of the cubes having certain geometric properties. The collection is called Whitney decomposition of the locally uniform domain. To extend a Sobolev function to a small cube in the Whitney decomposition one approach is to use polynomial approximations to the function on an nearby piece of the domain. We will use a polynomial reproducing kernel in order to obtain a degree independent extension operator. This involves defining the polynomial reproducing kernel in sets of the domain that we call here twisting cones. These sets are not exactly cones, but have some similarity to cones. Although a significant part of Rogers' work deals extensively with proving the existence of the kernel with the desired properties, our focus will remain in the construction of the extension operator so we will discuss the polynomial reproducing kernel only briefly. The extension operator for small Whitney cubes will be defined as convolution of the function with the kernel. For large Whitney cubes it is enough to set the extension to be 0. Finally the extension operator will be the smooth sum of the operators defined for each cube. Ultimately, since the domain is locally uniform the boundary is of measure zero and no special definition for the extension is required there. However it is necessary to verify that the extension "matches" the function correctly at the boundary, essentially that their k-1-th derivatives are Lipschitz there. This concludes the construction of a degree independent extension operator for Sobolev functions on a locally uniform domain.

A convex function, which Hessian determinant equals to one, defined in a convex and bounded polygon is called a surface tension. Moreover at the boundary of the given polygon it is demanded that the function is piece-wise affine. This setting originates from the theory of dimer models but in this thesis the system is studied as such. The boundary condition gives us points of interest i.e. the corners of the polygon and so called quasi-frozen points, where the boundary function is not differentiable. With a suitable homeomorphism one can map the unit disc to the polygon in question. In this setting an explicit formula for the gradient of the surface tension is derived. Furthermore the values of the gradient in corner and quasi-frozen points are derived as limits from, which as a corollary the directed derivatives of the surface tension are studied.

HMC is a computational method build to efficiently sample from a high dimensional distribution. Sampling from a distribution is typically a statistical problem and hence a lot of works concerning Hamiltonian Monte Carlo are written in the mathematical language of probability theory, which perhaps is not ideally suited for HMC, since HMC is at its core differential geometry. The purpose of this text is to present the differential geometric tool's needed in HMC and then methodically build the algorithm itself. Since there is a great introductory book to smooth manifolds by Lee and not wanting to completely copy Lee's work from his book, some basic knowledge of differential geometry is left for the reader. Similarly, the author being more comfortable with notions of differential geometry, and to cut down the length of this text, most theorems connected to measure and probability theory are omitted from this work. The first chapter is an introductory chapter that goes through the bare minimum of measure theory needed to motivate Hamiltonian Monte Carlo. Bulk of this text is in the second and third chapter. The second chapter presents the concepts of differential geometry needed to understand the abstract build of Hamiltonian Monte Carlo. Those familiar with differential geometry can possibly skip the second chapter, even though it might be worth while to at least flip through it to fill in on the notations used in this text. The third chapter is the core of this text. There the algorithm is methodically built using the groundwork laid in previous chapters. The most important part and the theoretical heart of the algorithm is presented here in the sections discussing the lift of the target measure. The fourth chapter provides brief practical insight to implementing HMC and also discusses quickly how HMC is currently being improved.