The jump operation for structure degrees

One of the main problems in effective model theory is to find an appropriate information complexity measure of the algebraic structures in the sense of computability. Unlike the commonly used degrees of structures, the structure degree measure is total. We introduce and study the jump operation for structure degrees. We prove that it has all natural jump properties (including jump inversion theorem, theorem of Ash), which show that our definition is relevant. We study the relation between the structure degree jump (in the sense of Soskov) and the jump degrees of a structure (in the sense of Jockusch) and give necessary and sufficient conditions for their existence in the terms of structure degrees. We show some properties, distinguishing the structure degrees from the enumeration degrees.     

c-Quasiminimal Enumeration Degrees

The notion of a C-quasiminimal set, with C an arbitrary subset of the naturals, was introduced by Sasso and presents a relativization of the well-known notion of quasiminimal set which was first constructed by Medvedev for proving the existence of nontotal enumeration degrees. In this article we study the local properties of the partially ordered set of the enumeration degrees containing C-quasiminimal sets. In particular, we prove for arbitrary enumeration degrees c and a that if c<a and a is a total e-degree then each at most countable partial order embeds isomorphically into the partially ordered set of c-quasiminimal e-degrees lying below a.     

Badness and jump inversion in the enumeration degrees

This paper continues the investigation into the relationship between good approximations and jump inversion initiated by Griffith. Firstly it is shown that there is a ${\Pi^{0}_{2}}$ set A whose enumeration degree a is bad—i.e. such that no set ${X \in a}$ is good approximable—and whose complement ${\overline{A}}$ has lowest possible jump, in other words is low₂. This also ensures that the degrees y ≤ a only contain ${\Delta^{0}_{3}}$ sets and thus yields a tight lower bound for the complexity of both a set of bad enumeration degree, and of its complement, in terms of the high/low jump hierarchy. Extending the author’s previous characterisation of the double jump of good approximable sets, the triple jump of a ${\Sigma^{0}_{2}}$ set A is characterised in terms of the index set of coinfinite sets enumeration reducible to A. The paper concludes by using Griffith’s jump interpolation technique to show that there exists a high quasiminimal ${\Delta^{0}_{2}}$ enumeration degree.     

Limit lemmas and jump inversion in the enumeration degrees

We show that there is a limit lemma for enumeration reducibility to 0_e', analogous to the Shoenfield Limit Lemma in the Turing degrees, which relativises for total enumeration degrees. Using this and `good approximations' we prove a jump inversion result: for any set W with a good approximation and any set X<_eW such that W_eX' there is a set A such that X_eA<_eW and A'=W'. (All jumps are enumeration degree jumps.) The degrees of sets with good approximations include the ⁰₂ degrees and the n-CEA degrees. The results in this paper form part of the author's doctoral dissertation written under the supervision of Prof. Steffen Lempp at the University of Wisconsin Madison. The author is grateful to an anonymous referee for helpful comments and suggestions.     

A non-inversion theorem for the jump operator

R.W. Robinson's [15] interpolation theorem shows that the Sacks [16] jump inversion theorem can be extended to invert the jump and preserve order on any finite linearly ordered set of degrees r.e. in and above (REA in) 0′. We show that although the Friedberg inversion theorem can be extended to partial orders, the Sacks theorem cannot be extended to even the simplest ones even if we allow the inversion to carry us into rather than just the r.e. degrees. This strong non-inversion theorem also decides the problem that Lerman [12] has called the main obstacle to deciding the theory of the degrees with jump. It is a corollary to our main result:

Theorem 1.1. There are a₀ and a₁ REA in 0′ such that a₀ a₁<0” and if u<0′, then not both a₀ and a₁ are r.e. in u.

Other corollaries include a solution to a problem suggested by Jockusch and Soare: not every a REA in 0′ is the jump of a degree which is half of an r.e. minimal pair. The proof introduces a new type of 0 priority argument in which the tree of strategies is ω+1 branching and so simply determining the true path requires a 0 oracle.     

The viability property of controlled jump diffusion processes

In this paper, we first give a comparison theorem of viscosity solution to some nonlinear second order integrodifferential equation. And then using the comparison theorem, we obtain a necessary and sufficient condition for the viability property of some controlled jump diffusion processes which can keep the solution within a constraint K.     

Determination of Dirac operator with eigenvalue-dependent boundary and jump conditions

Dirac operator with eigenvalue-dependent boundary and jump conditions is studied. Uniqueness theorems of the inverse problems from either Weyl function or the spectral data (the sets of eigenvalues and norming constants except for one eigenvalue and corresponding norming constant; two sets of different eigenvalues except for two eigenvalues) are proved. Finally, we investigate two applications of these theorems and obtain analogues of a theorem of Hochstadt-Lieberman and a theorem of Mochizuki-Trooshin.     

The jump operator on the -enumeration degrees

The jump operator on the ω-enumeration degrees was introduced in [I.N. Soskov, The ω-enumeration degrees, J. Logic Computat. 17 (2007) 1193–1214]. In the present paper we prove a jump inversion theorem which allows us to show that the enumeration degrees are first order definable in the structure of the ω-enumeration degrees augmented by the jump operator. Further on we show that the groups of the automorphisms of and of the enumeration degrees are isomorphic.In the second part of the paper we study the jumps of the ω-enumeration degrees below . We define the ideal of the almost zero degrees and obtain a natural characterization of the class H of the ω-enumeration degrees below which are high n for some n and of the class L of the ω-enumeration degrees below which are low n for some n.     

The generalised jump of a function and Gibbs phenomenon

Summary By studying certain transforms and applying his theorem on ? the generalised jump of a function ? author proves certain theorems concerning jump of a function and Gibbs phenomenon.     

A jump inversion theorem for the semilattices of sigma-degrees

We prove an analogue of the jump inversion theorem for the semilattices of Σ-degrees of structures. As a corollary, we get a similar result for the semilattices of degrees of presentability of countable structures.     

Synchronized stationary distribution for stochastic multi-links systems with Markov jump

This paper is concerned with the existence of a synchronized stationary distribution for stochastic multi-links systems with Markov jump (SMMJs). By employing Lyapunov method, Kirchhoff’s Matrix Tree Theorem in graph theory as well as M-matrix method, several criteria are given to guarantee the existence of a synchronized stationary distribution of SMMJs, including the Lyapunov-type theorem and a coefficients-type theorem. As a subsequent, the theoretical results are applied to a class of stochastic Markov jump oscillators with multi-links and stochastic multi-links Chua’s circuits with Markov jump, which indicates the results present widely applied prospect in various physical systems. Eventually, two examples together with numerical simulations are provided to validate the effectiveness of the theoretical results.     

Hypergraphs do not jump

The number α, 0≦α≦1, is a jump forr if for any positive ε and any integerm,m≧r, anyr-uniform hypergraph withn>n _o (ε,m) vertices and at least (α+ε) \(\left( {\begin{array}{*{20}c} n \\ r \\ \end{array} } \right)\) edges contains a subgraph withm vertices and at least (α+c) \(\left( {\begin{array}{*{20}c} m \\ r \\ \end{array} } \right)\) edges, wherec=c(α) does not depend on ε andm. It follows from a theorem of Erdös, Stone and Simonovits that forr=2 every α is a jump. Erdös asked whether the same is true forr≧3. He offered $ 1000 for answering this question. In this paper we give a negative answer by showing that \(1 - \frac{1}{{l^{r - 1} }}\) is not a jump ifr≧3,l>2r.     

Perfect Matchings and Perfect Powers

In the last decade there have been many results about special families of graphs whose number of perfect matchings is given by perfect or near perfect powers (N. Elkies et al., J. Algebraic Combin. 1 (1992), 111–132; B.-Y. Yang, Ph.D. thesis, Department of Mathematics, MIT, Cambridge, MA, 1991; J. Propp, New Perspectives in Geometric Combinatorics, Cambridge University Press, 1999). In this paper we present an approach that allows proving them in a unified way. We use this approach to prove a conjecture of James Propp stating that the number of tilings of the so-called Aztec dungeon regions is a power (or twice a power) of 13. We also prove a conjecture of Matt Blum stating that the number of perfect matchings of a certain family of subgraphs of the square lattice is a power of 3 or twice a power of 3. In addition we obtain multi-parameter generalizations of previously known results, and new multi-parameter exact enumeration results. We obtain in particular a simple combinatorial proof of Bo-Yin Yang's multivariate generalization of fortresses, a result whose previously known proof was quite complicated, amounting to evaluation of the Kasteleyn matrix by explicit row reduction. We also include a new multivariate exact enumeration of Aztec diamonds, in the spirit of Stanley's multivariate version.     

On some functionals of the first passage times in jump models of stochastic volatility

Abstract

We compute some functionals related to the generalized joint Laplace transforms of the first times at which two-dimensional jump processes exit half strips. It is assumed that the state space components are driven by Cox processes with both independent and common (positive) exponential jump components. The method of proof is based on the solutions of the equivalent partial integro-differential boundary-value problems for the associated value functions. The results are illustrated on several two-dimensional jump models of stochastic volatility which are based on non-affine analogs of certain mean-reverting or diverting diffusion processes representing closed-form solutions of the appropriate stochastic differential equations.     

Anticipated BSDEs driven by a single jump process

In this paper, we discuss a class of anticipated backward stochastic differential equations related to a finite continuous time single jump process. We prove the existence and uniqueness of the adapted solution. Moreover, a comparison theorem for the solutions is also established.     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

A representation theory for the impulse control of jump processes

A state space representation theory for the impulse control of a quite general class of non-Markov jump processes is developed. Control decisions are based upon observations of past histories of an input jump process and observations of the current state of the corresponding controlled output. A verification theorem establishes that a solution of a system of quasi variational inequalities gives rise naturally to an optimal impulse policy. The proof of optimality relies upon an extended version of the well-known Dynkin formula for Markov processes.     

Three sphere inequality for second order elliptic equations with coefficients with jump discontinuity

This is a short note to complete the paper appeared in Francini et al. (2016) [4], where a rough version of the classical well known Hadamard three-circle theorem for solution of an elliptic PDE in divergence form has been proved. Precisely, instead of circles, the authors obtain a similar inequality in a more complicated geometry. In this paper we clean the geometry and obtain a generalized version of the three-circle inequality for elliptic equation with coefficients with discontinuity of jump type.     

A thinning result for pure jump processes

A standard thinning procedure for point processes is extended to processes of pure jump type in which each jump is retained with probability p or deleted with probability 1 ? p, independently of everything else.Two theorems are proved, the first gives a sufficient condition for the existence of thinned pure jump processes, the second concerns the convergence of such processes to pure jump processes whose increments are generated by a Cox process. Some generalizations are discussed.     

Problem of optimal endogenous growth with exhaustible resources and possibility of a technological jump

In 2013, S. Aseev, K. Besov, and S. Kaniovski (“The problem of optimal endogenous growth with exhaustible resources revisited,” Dyn. Model. Econometr. Econ. Finance 14, 3–30) considered the problem of optimal dynamic allocation of economic resources in an endogenous growth model in which both production and research sectors require an exhaustible resource as an input. The problem is formulated as an infinite-horizon optimal control problem with an integral constraint imposed on the control. A full mathematical study of the problem was carried out, and it was shown that the optimal growth is not sustainable under the most natural assumptions about the parameters of the model. In the present paper we extend the model by introducing an additional possibility of “random” transition (jump) to a qualitatively new technological trajectory (to an essentially unlimited backstop resource). As an objective functional to be maximized, we consider the expected value of the sum of the objective functional in the original problem on the time interval before the jump and an evaluation of the state of the model at the moment of the jump. The resulting problem also reduces to an infinite-horizon optimal control problem, and we prove an existence theorem for it and write down an appropriate version of the Pontryagin maximum principle. Then we characterize the optimal transitional dynamics and compare the results with those for the original problem (without a jump).