Constructing cubature formulae of degree 5 with few points

This paper is devoted to construct a family of fifth degree cubature formulae for n$n$-cube with symmetric measure and n$n$-dimensional spherically symmetrical region. The formula forn$n$-cube contains at most n²+5n+3$n^2+5n+3$ points and for n$n$-dimensional spherically symmetrical region contains only n²+3n+3$n^2+3n+3$ points. Moreover, the numbers can be reduced to n²+3n+1$n^2+3n+1$ and n²+n+1$n^2+n+1$ if n=7$n=7$ respectively, the latter of which is minimal.     

Estimating the ground state energy of the Schrödinger equation for convex potentials

In 2011, the fundamental gap conjecture for Schrödinger operators was proven. This can be used to estimate the ground state energy of the time-independent Schrödinger equation with a convex potential and relative error ε$\epsilon$. Classical deterministic algorithms solving this problem have cost exponential in the number of its degrees of freedom d$d$. We show a quantum algorithm, that is based on a perturbation method, for estimating the ground state energy with relative error ε$\epsilon$. The cost of the algorithm is polynomial in d$d$ and ε⁻¹${\epsilon }^{-1}$, while the number of qubits is polynomial in d$d$ and logε⁻¹$log{\epsilon }^{-1}$. In addition, we present an algorithm for preparing a quantum state that overlaps within 1−δ,δ∈(0,1)$1-\delta ,\delta \in (0,1)$, with the ground state eigenvector of the discretized Hamiltonian. This algorithm also approximates the ground state with relative error ε$\epsilon$. The cost of the algorithm is polynomial in d$d$, ε⁻¹${\epsilon }^{-1}$ and δ⁻¹${\delta }^{-1}$, while the number of qubits is polynomial in d$d$, logε⁻¹$log{\epsilon }^{-1}$ and logδ⁻¹$log{\delta }^{-1}$.     

Convergence of invariant measures for singular stochastic diffusion equations

It is proved that the solutions to the singular stochastic p$p$-Laplace equation, p∈(1,2)$p\in (1,2)$ and the solutions to the stochastic fast diffusion equation with nonlinearity parameter r∈(0,1)$r\in (0,1)$ on a bounded open domain Λ⊂R^d$\Lambda \subset {\mathbb{R}}^d$ with Dirichlet boundary conditions are continuous in mean, uniformly in time, with respect to the parameters p$p$ and r$r$ respectively (in the Hilbert spaces L²(Λ)$L^2\left(\Lambda \right)$, H⁻¹(Λ)$H^{-1}\left(\Lambda \right)$ respectively). The highly singular limit case p=1$p=1$ is treated with the help of stochastic evolution variational inequalities, where P$\mathbb{P}$-a.s. convergence, uniformly in time, is established.     

Asymptotic average shadowing property on compact metric spaces

We prove that if for a continuous map f$f$ on a compact metric space X$X$, the chain recurrent set, R(f)$R\left(f\right)$ has more than one chain component, then f$f$ does not satisfy the asymptotic average shadowing property. We also show that if a continuous map f$f$ on a compact metric space X$X$ has the asymptotic average shadowing property and if A$A$ is an attractor for f$f$, then A$A$ is the single attractor for f$f$ and we have A=R(f)$A=R\left(f\right)$. We also study diffeomorphisms with asymptotic average shadowing property and prove that if M$M$ is a compact manifold which is not finite with dimM=2$dimM=2$, then the C¹$C^1$ interior of the set of all C¹$C^1$ diffeomorphisms with the asymptotic average shadowing property is characterized by the set of Ω$\Omega$-stable diffeomorphisms.     

Hölder continuity of solutions of supercritical dissipative hydrodynamic transport equations

We examine the regularity of weak solutions of quasi-geostrophic (QG) type equations with supercritical (α<1/2$\alpha <1/2$) dissipation α(−Δ)${(-\mathrm{\Delta })}^{\alpha }$. This study is motivated by a recent work of Caffarelli and Vasseur, in which they study the global regularity issue for the critical (α=1/2$\alpha =1/2$) QG equation [L. Caffarelli, A. Vasseur, Drift diffusion equations with fractional diffusion and the quasi-geostrophic equation, arXiv: math.AP/0608447, 2006]. Their approach successively increases the regularity levels of Leray–Hopf weak solutions: from L²$L^2$ to L^∞$L^{\infty }$, from L^∞$L^{\infty }$ to Hölder (Cδ$C^{\delta }$, δ>0$\delta >0$), and from Hölder to classical solutions. In the supercritical case, Leray–Hopf weak solutions can still be shown to be L^∞$L^{\infty }$, but it does not appear that their approach can be easily extended to establish the Hölder continuity of L^∞$L^{\infty }$ solutions. In order for their approach to work, we require the velocity to be in the Hölder space C1−2α$C^{1-2\alpha }$. Higher regularity starting from Cδ$C^{\delta }$ with δ>1−2α$\delta >1-2\alpha$ can be established through Besov space techniques and will be presented elsewhere [P. Constantin, J. Wu, Regularity of Hölder continuous solutions of the supercritical quasi-geostrophic equation, Ann. Inst. H. Poincaré Anal. Non Linéaire, in press].     

Uniform bound of Sobolev norms of solutions to 3D nonlinear wave equations with null condition

This article concerns the time growth of Sobolev norms of classical solutions to the 3D quasi-linear wave equations with the null condition. Given initial data in H^s×H^s−1$H^s\times H^{s-1}$ with compact supports, the global well-posedness theory has been established independently by Klainerman [13] and Christodoulou [3], respectively, for a relatively large integer s  . However, the highest order Sobolev energy, namely, the H^s$H^s$ energy of solutions may have a logarithmic growth in time. In this paper, we show that the H^s$H^s$ energy of solutions is also uniformly bounded for s?5$s?5$. The proof employs the generalized energy method of Klainerman, enhanced by weighted L²$L^2$ estimates and the ghost weight introduced by Alinhac.     

Harness processes and harmonic crystals

In the Hammersley harness processes the R$\mathbb{R}$-valued height at each site i∈Z^d$i\in {\mathbb{Z}}^d$ is updated at rate 1 to an average of the neighboring heights plus a centered random variable (the noise). We construct the process “a la Harris” simultaneously for all times and boxes contained in Z^d${\mathbb{Z}}^d$. With this representation we compute covariances and show L²$L^2$ and almost sure time and space convergence of the process. In particular, the process started from the flat configuration and viewed from the height at the origin converges to an invariant measure. In dimension three and higher, the process itself converges to an invariant measure in L²$L^2$ at speed t^1−d/2$t^{1-d/2}$ (this extends the convergence established by Hsiao). When the noise is Gaussian the limiting measures are Gaussian fields (harmonic crystals) and are also reversible for the process.     

Quadrature rule for Abel’s equations: Uniformly approximating fractional derivatives

An automatic quadrature method is presented for approximating fractional derivative D^qf(x)$D^{q}f\left(x\right)$ of a given function f(x)$f\left(x\right)$, which is defined by an indefinite integral involving f(x)$f\left(x\right)$. The present method interpolates f(x)$f\left(x\right)$ in terms of the Chebyshev polynomials in the range [0, 1] to approximate the fractional derivative D^qf(x)$D^{q}f\left(x\right)$ uniformly for 0≤x≤1$0\le x\le 1$, namely the error is bounded independently of x$x$. Some numerical examples demonstrate the performance of the present automatic method.     

The Ornstein–Uhlenbeck bridge and applications to Markov semigroups

For an arbitrary Hilbert space-valued Ornstein–Uhlenbeck process we construct the Ornstein–Uhlenbeck bridge connecting a given starting point x$x$ and an endpoint y$y$ provided y$y$ belongs to a certain linear subspace of full measure. We derive also a stochastic evolution equation satisfied by the OU bridge and study its basic properties. The OU bridge is then used to investigate the Markov transition semigroup defined by a stochastic evolution equation with additive noise. We provide an explicit formula for the transition density and study its regularity. These results are applied to show some basic properties of the transition semigroup. Given the strong Feller property and the existence of invariant measure we show that all L^p$L^p$ functions are transformed into continuous functions, thus generalising the strong Feller property. We also show that transition operators are q$q$-summing for some q>p>1$q>p>1$, in particular of Hilbert–Schmidt type.     

On testing Hamiltonicity of graphs

Let us fix a function f(n)=o(nlnn)$f\left(n\right)=o(nlnn)$ and real numbers 0≤α<β≤1$0\le \alpha <\beta \le 1$. We present a polynomial time algorithm which, given a directed graph G$G$ with n$n$ vertices, decides either that one can add at most βn$\beta n$ new edges to G$G$ so that G$G$ acquires a Hamiltonian circuit or that one cannot add αn$\alpha n$ or fewer new edges to G$G$ so that G$G$ acquires at least e^−f(n)n!$e^{-f\left(n\right)}n!$ Hamiltonian circuits, or both.     

On the length of an external branch in the Beta-coalescent

In this paper, we consider Beta(2−α,α)$(2-\alpha ,\alpha )$ (with 1<α<2$1<\alpha <2$) and related Λ$\Lambda$-coalescents. If T⁽ⁿ⁾$T^{\left(n\right)}$ denotes the length of a randomly chosen external branch of the n$n$-coalescent, we prove the convergence of n^α−1T⁽ⁿ⁾$n^{\alpha -1}{T}^{\left(n\right)}$ when n$n$ tends to ∞$\infty$, and give the limit. To this aim, we give asymptotics for the number σ⁽ⁿ⁾${\sigma }^{\left(n\right)}$ of collisions which occur in the n$n$-coalescent until the end of the chosen external branch, and for the block counting process associated with the n$n$-coalescent.     

The interrelation between stochastic differential inclusions and set-valued stochastic differential equations

In this paper we connect the well established theory of stochastic differential inclusions with a new theory of set-valued stochastic differential equations. Solutions to the latter equations are understood as continuous mappings taking on their values in the hyperspace of nonempty, bounded, convex and closed subsets of the space L²$L^2$ consisting of square integrable random vectors. We show that for the solution X$X$ to a set-valued stochastic differential equation corresponding to a stochastic differential inclusion, there exists a solution x$x$ for this inclusion that is a _‖⋅‖L2${\Vert \cdot \Vert }_{L^2}$-continuous selection of X$X$. This result enables us to draw inferences about the reachable sets of solutions for stochastic differential inclusions, as well as to consider the viability problem for stochastic differential inclusions.     

Transformation formulas for fractional Brownian motion

We derive a Molchan–Golosov-type integral transform which changes fractional Brownian motion of arbitrary Hurst index K$K$ into fractional Brownian motion of index H$H$. Integration is carried out over [0,t]$[0,t]$, t>0$t>0$. The formula is derived in the time domain. Based on this transform, we construct a prelimit which converges in L²(P)$L^2\left(\mathbb{P}\right)$-sense to an analogous, already known Mandelbrot–Van Ness-type integral transform, where integration is over (−∞,t]$(-\infty ,t]$, t>0$t>0$.     

On truncated variation,upward truncated variation and downward truncated variation for diffusions

The truncated variation, TV^c${\text{TV}}^c$, is a fairly new concept introduced in ?ochowski (2008) [5]. Roughly speaking, given a càdlàg function f$f$, its truncated variation is “the total variation which does not pay attention to small changes of f$f$, below some threshold c>0$c>0$”. The very basic consequence of such approach is that contrary to the total variation, TV^c${\text{TV}}^c$ is always finite. This is appealing to the stochastic analysis where so-far large classes of processes, like semimartingales or diffusions, could not be studied with the total variation. Recently in ?ochowski (2011) [6], another characterization of TV^c${\text{TV}}^c$ has been found. Namely TV^c${\text{TV}}^c$ is the smallest possible total variation of a function which approximates f$f$ uniformly with accuracy c/2$c/2$. Due to these properties we envisage that TV^c${\text{TV}}^c$ might be a useful concept both in the theory and applications of stochastic processes.     

Feedback vertex set on graphs of low clique-width

The Feedback Vertex Set problem asks whether a graph contains q$q$ vertices meeting all its cycles. This is not a local property, in the sense that we cannot check if q$q$ vertices meet all cycles by looking only at their neighbors. Dynamic programming algorithms for problems based on non-local properties are usually more complicated. In this paper, given a graph G$G$ of clique-width cw$cw$ and a cw$cw$-expression of G$G$, we solve the Minimum Feedback Vertex Set problem in time O(n²2^O(cwlogcw))$O\left(n^2{2}^{O(cwlogcw)}\right)$. Our algorithm applies dynamic programming on a so-called k$k$-module decomposition of a graph, as defined by Rao (2008) [29], which is easily derivable from ak$k$-expression of the graph. The related notion of module-width of a graph is tightly linked to both clique-width and NLC-width, and in this paper we give an alternative equivalent characterization of module-width.     

On the effectiveness of a generalization of Miller’s primality theorem

Berrizbeitia and Olivieri showed in a recent paper that, for any integer r$r$, the notion of ω$\omega$-prime to base a$a$ leads to a primality test for numbers n≡1$n\equiv 1$ mod r$r$, that under the Extended Riemann Hypothesis (ERH) runs in polynomial time. They showed that the complexity of their test is at most the complexity of the Miller primality test (MPT), which is O((logn)^4+o(1))$O\left({(logn)}^{4+o\left(1\right)}\right)$. They conjectured that their test is more effective than the MPT if r$r$ is large.     

Multidimensional extension of the Morse–Hedlund theorem

A celebrated result of Morse and Hedlund, stated in 1938, asserts that a sequence x$x$ over a finite alphabet is ultimately periodic if and only if, for some n$n$, the number of different factors of length n$n$ appearing in x$x$ is less than n+1$n+1$. Attempts to extend this fundamental result, for example, to higher dimensions, have been considered during the last fifteen years. Let d≥2$d\ge 2$. A legitimate extension to a multidimensional setting of the notion of periodicity is to consider sets of Z^d${\mathbb{Z}}^d$ definable by a first order formula in the Presburger arithmetic 〈Z;<,+〉$〈\mathbb{Z};<,+〉$. With this latter notion and using a powerful criterion due to Muchnik, we exhibit a complete extension of the Morse–Hedlund theorem to an arbitrary dimension d$d$ and characterize sets of Z^d${\mathbb{Z}}^d$ definable in 〈Z;<,+〉$〈\mathbb{Z};<,+〉$ in terms of some functions counting recurrent blocks, that is, blocks occurring infinitely often.