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.     

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.     

Partial rigidity of degenerate CR embeddings into spheres

In this paper, we study degenerate CR embeddings f$f$ of a strictly pseudoconvex hypersurface M⊂Cⁿ⁺¹$M\subset {\mathbb{C}}^{n+1}$ into a sphere S$\mathbb{S}$ in a higher dimensional complex space C^N+1${\mathbb{C}}^{N+1}$. The degeneracy of the mapping f$f$ will be characterized in terms of the ranks of the CR second fundamental form and its covariant derivatives. In 2004, the author, together with X. Huang and D. Zaitsev, established a rigidity result for CR embeddings f$f$ into spheres in low codimensions. A key step in the proof of this result was to show that degenerate mappings are necessarily contained in a complex plane section of the target sphere (partial rigidity). In the 2004 paper, it was shown that if the total rank d$d$ of the second fundamental form and all of its covariant derivatives is <n$<n$ (here, n$n$ is the CR dimension of M$M$), then f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$. The converse of this statement is also true, as is easy to see. When the total rank d$d$ exceeds n$n$, it is no longer true, in general, that f(M)$f\left(M\right)$ is contained in a complex plane of dimension n+d+1$n+d+1$, as can be seen by examples. In this paper, we carry out a systematic study of degenerate CR mappings into spheres. We show that when the ranks of the second fundamental form and its covariant derivatives exceed the CR dimension n$n$, then partial rigidity may still persist, but there is a “defect” k$k$ that arises from the ranks exceeding n$n$ such that f(M)$f\left(M\right)$ is only contained in a complex plane of dimension n+d+k+1$n+d+k+1$. Moreover, this defect occurs in general, as is illustrated by examples.     

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.     

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.     

Large deviations of infinite intersections of events in Gaussian processes

Consider events of the form {_Zs≥ζ(s),s∈S}$\{Z_s\ge \zeta \left(s\right),s\in S\}$, where Z$Z$ is a continuous Gaussian process with stationary increments, ζ$\zeta$ is a function that belongs to the reproducing kernel Hilbert space R$R$ of process Z$Z$, and S⊂R$S\subset \mathbb{R}$ is compact. The main problem considered in this paper is identifying the function β^∗∈R${\beta }^{\ast }\in R$ satisfying β^∗(s)≥ζ(s)${\beta }^{\ast }\left(s\right)\ge \zeta \left(s\right)$ on S$S$ and having minimal R$R$-norm. The smoothness (mean square differentiability) of Z$Z$ turns out to have a crucial impact on the structure of the solution. As examples, we obtain the explicit solutions when ζ(s)=s$\zeta \left(s\right)=s$ for s∈[0,1]$s\in [0,1]$ and Z$Z$ is either a fractional Brownian motion or an integrated Ornstein–Uhlenbeck process.     

Ordinary and symbolic powers are Golod

Let S$S$ be a positively graded polynomial ring over a field of characteristic 0$0$, and I⊂S$I\subset S$ a proper graded ideal. In this note it is shown that S/I$S/I$ is Golod if ∂(I)²⊂I$\partial {\left(I\right)}^2\subset I$. Here ∂(I)$\partial \left(I\right)$ denotes the ideal generated by all the partial derivatives of elements of I$I$. We apply this result to find large classes of Golod ideals, including powers, symbolic powers, and saturations of ideals.     

Applications of equivariant degree for gradient maps to symmetric Newtonian systems

We consider G=Γ×S¹$G=\Gamma \times S^1$ with Γ$\Gamma$ being a finite group, for which the complete Euler ring structure in U(G)$U\left(G\right)$ is described. The multiplication tables for Γ=_D6$\Gamma =D_6$, _S4$S_4$ and _A5$A_5$ are provided in the Appendix. The equivariant degree for G$G$-orthogonal maps is constructed using the primary equivariant degree with one free parameter. We show that the G$G$-orthogonal degree extends the degree for G$G$-gradient maps (in the case of G=Γ×S¹$G=\Gamma \times S^1$) introduced by G?ba in [K. G?ba, W. Krawcewicz, J. Wu, An equivariant degree with applications to symmetric bifurcation problems I: Construction of the degree, Bull. London. Math. Soc. 69 (1994) 377–398]. The computational results obtained are applied to a Γ$\Gamma$-symmetric autonomous Newtonian system for which we study the existence of 2π$2\pi$-periodic solutions. For some concrete cases, we present the symmetric classification of the solution set for the systems considered.     

Stable extendibility of vector bundles over real projective spaces

Let F$\mathbb{F}$ be either the real number field R$\mathbb{R}$ or the complex number field C$\mathbb{C}$ and RPⁿ${\mathbb{RP}}^n$ the real projective space of dimension n. Theorems A and C in Hemmi and Kobayashi (2008) [2] give necessary and sufficient conditions for a given F$\mathbb{F}$-vector bundle over RPⁿ${\mathbb{RP}}^n$ to be stably extendible to RP^m${\mathbb{RP}}^m$ for every m?n$m?n$. In this paper, we simplify the theorems and apply them to the tangent bundle of RPⁿ${\mathbb{RP}}^n$, its complexification, the normal bundle associated to an immersion of RPⁿ${\mathbb{RP}}^n$ in R^n+r${\mathbb{R}}^{n+r}$(r>0)$(r>0)$, and its complexification. Our result for the normal bundle is a generalization of Theorem A in Kobayashi et al. (2000) [8] and that for its complexification is a generalization of Theorem 1 in Kobayashi and Yoshida (2003) [5].     

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.     

Critical edges for the assignment problem: Complexity and exact resolution

This paper investigates two problems related to the determination of critical edges for the minimum cost assignment problem. Given a complete bipartite balanced graph with n$n$ vertices on each part and with costs on its edges, k$k$Most Vital Edges Assignment consists of determining a set of k$k$ edges whose removal results in the largest increase in the cost of a minimum cost assignment. A dual problem, Min Edge Blocker Assignment, consists of removing a subset of edges of minimum cardinality such that the cost of a minimum cost assignment in the remaining graph is larger than or equal to a specified threshold. We show that k$k$Most Vital Edges Assignment is NP$NP$-hard to approximate within a factor c<2$c<2$ and Min Edge Blocker Assignment is NP$NP$-hard to approximate within a factor 1.36$1.36$. We also provide an exact algorithm for k$k$Most Vital Edges Assignment that runs in O(n^k+2)$O\left(n^{k+2}\right)$. This algorithm can also be used to solve exactly Min Edge Blocker Assignment.     

Estimation for stochastic differential equations with a small diffusion coefficient

We consider a multidimensional diffusion X$X$ with drift coefficient b(_Xt,α)$b(X_t,\alpha )$ and diffusion coefficient εa(_Xt,β)$\epsilon a(X_t,\beta )$ where α$\alpha$ and β$\beta$ are two unknown parameters, while ε$\epsilon$ is known. For a high frequency sample of observations of the diffusion at the time points k/n$k/n$, k=1,…,n$k=1,\dots ,n$, we propose a class of contrast functions and thus obtain estimators of (α,β)$(\alpha ,\beta )$. The estimators are shown to be consistent and asymptotically normal when n→∞$n\to \infty$ and ε→0$\epsilon \to 0$ in such a way that ε⁻¹n^−ρ${\epsilon }^{-1}{n}^{-\rho }$ remains bounded for some ρ>0$\rho >0$. The main focus is on the construction of explicit contrast functions, but it is noted that the theory covers quadratic martingale estimating functions as a special case. In a simulation study we consider the finite sample behaviour and the applicability to a financial model of an estimator obtained from a simple explicit contrast function.     

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.     

Phase transition in equilibrium fluctuations of symmetric slowed exclusion

We analyze the equilibrium fluctuations of density, current and tagged particle in symmetric exclusion with a slow bond. The system evolves in the one-dimensional lattice and the jump rate is everywhere equal to one except at the slow bond where it is αn^−β$\alpha n^{-\beta }$, with α>0$\alpha >0$, β∈[0,+∞]$\beta \in [0,+\infty ]$ and n$n$ is the scaling parameter. Depending on the regime of β$\beta$, we find three different behaviors for the limiting fluctuations whose covariances are explicitly computed. In particular, for the critical value β=1$\beta =1$, starting a tagged particle near the slow bond, we obtain a family of Gaussian processes indexed in α$\alpha$, interpolating a fractional Brownian motion of Hurst exponent 1/4$1/4$ and the degenerate process equal to zero.     

Growth order for the size of smallest hamiltonian chain saturated uniform hypergraphs

We say that a hypergraph H$H$ is hamiltonian chain saturated if H$H$ does not contain a hamiltonian chain but by adding any new edge we create a hamiltonian chain in H$H$. In this paper, for each k≥3$k\ge 3$, we establish the right order of magnitude n^k−1$n^{k-1}$ for the size of the smallest k$k$-uniform hamiltonian chain saturated hypergraph. This solves an open problem of G.Y. Katona.     

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}$.