Post's Problem for Reducibilities of Bounded Complexity

In this paper we consider the we known method by E. Post of solving the problem of construction of recursively enumerable sets that have a degree intermediate between the degrees of recursive and complete sets with respect to a given reducibility. Post considered reducibilities ≤_m, ≤_btt, ≤_tt and ≤_T and solved the problem for al of them except ≤_T. Here we extend Post's original method of construction of incomplete sets onto two wide classes of sub‐Turing reducibilities what were studying in [1, 2].     

Separations by Random Oracles and “Almost” Classes for Generalized Reducibilities

Let ≤_r and ≤_sbe two binary relations on 2^ℕ which are meant as reducibilities. Let both relations be closed under finite variation (of their set arguments) and consider the uniform distribution on 2^ℕ, which is obtained by choosing elements of 2^ℕ by independent tosses of a fair coin.Then we might ask for the probability that the lower ≤_r‐cone of a randomly chosen set X, that is, the class of all sets A with A ≤_r X, differs from the lower ≤_s‐cone of X. By c osure under finite variation, the Kolmogorov 0‐1 aw yields immediately that this probability is either 0 or 1; in case it is 1, the relations are said to be separable by random oracles.Again by closure under finite variation, for every given set A, the probability that a randomly chosen set X is in the upper ≤_r‐cone of A is either 0 or 1; let Almost_r be the class of sets for which the upper ≤_r‐cone has measure 1. In the following, results about separations by random oracles and about Almost classes are obtained in the context of generalized reducibilities, that is, for binary relations on 2^ℕ which can be defined by a countable set of total continuous functionals on 2^ℕ in the same way as the usual resource‐bounded reducibilities are defined by an enumeration of appropriate oracle Turing machines. The concept of generalized reducibility comprises a natura resource‐bounded reducibilities, but is more general; in particular, it does not involve any kind of specific machine model or even effectivity. The results on generalized reducibilities yield corollaries about specific resource‐bounded reducibilities, including several results which have been shown previously in the setting of time or space bounded Turing machine computations.     

Discontinuity of Cappings in the Recursively Enumerable Degrees and Strongly Nonbranching Degrees

We construct an r. e. degree a which possesses a greatest a-minimal pair b₀, b₁, i.e., r. e. degrees b₀ and b₁ such that b₀, b₁ < a, b₀ ∩ b₁ = a, and, for any other pair c₀, c₁ with these properties, c₀ ≤ b_i and c₁ ≤ b_1-i for some i ≤ 1. By extending this result, we show that there are strongly nonbranching degrees which are not strongly noncappable. Finally, by introducing a new genericity concept for r. e. sets, we prove a jump theorem for the strongly nonbranching and strongly noncappable r. e. degrees. Mathematics Subject Classification : 03D25.     

Exact Pairs for Abstract Bounded Reducibilities

In an attempt to give a unified account of common properties of various resource bounded reducibilities, we introduce conditions on a binary relation ≤_r between subsets of the natural numbers, where ≤_r is meant as a resource bounded reducibility. The conditions are a formalization of basic features shared by most resource bounded reducibilities which can be found in the literature. As our main technical result, we show that these conditions imply a result about exact pairs which has been previously shown by Ambos-Spies [2] in a setting of polynomial time bounds: given some recursively presentable ≤_r-ideal I and some recursive ≤_r-hard set B for I which is not contained in I, there is some recursive set C, where B and C are an exact pair for I, that is, I is equal to the intersection of the lower ≤_r-cones of B and C, where C is not in I. In particular, if the relation ≤_r is in addition transitive and there are least sets, then every recursive set which is not in the least degree is half of a minimal pair of recursive sets.     

Δ2 degrees without Σ1 induction

In this paper, we study the structure of Turing degrees below 0′ in the theory that is a fragment of Peano arithmetic without Σ₁ induction, with special focus on proper d-r.e. degrees and non-r.e. degrees. We prove:

1. P ^? + BΣ₁ + Exp ? There is a proper d-r.e. degree.
2. P ^? +BΣ₁+ Exp ? IΣ₁ ? There is a proper d-r.e. degree below 0′.
3. P ^? + BΣ₁ + Exp ? There is a non-r.e. degree below 0′.

     

Norms on L of Periodic Interpolation Splines with Equidistant Nodes

We consider the set S _r,n of periodic (with period 1) splines of degree r with deficiency 1 whose nodes are at n equidistant points x_i=i / n. For n-tuples y = (y₀, ... , y_n-1), we take splines s _r,n (y, x) from S _r,n solving the interpolation problem

$$s_{r,n} (y,t_i ) = y_i,$$

where t _i = x _i if r is odd and t _i is the middle of the closed interval [x _i , x _i+1 ] if r is even. For the norms L _r,n ^* of the operator y → s _r,n (y, x) treated as an operator from l¹ to L¹ [0, 1] we establish the estimate

$$L_{r,n}^ * = \frac{4}{{\pi ^2 n}}log min(r,n) + O\left( {\frac{1}{n}} \right)$$

with an absolute constant in the remainder. We study the relationship between the norms L _r,n ^* and the norms of similar operators for nonperiodic splines.

     

Piecewise Monotone Pointwise Approximation

Let r, k, s be three integers such that , or We prove the following: Proposition. Let Y:={y _i } _i=1 ^s be a fixed collection of distinct points y _i ∈ (-1,1) and Π (x):= (x-y ₁ ). ... .(x-y _s ). Let I:=[-1,1]. If f ∈ C ^(r) (I) and f'(x)Π(x) ≥ 0, x ∈ I, then for each integer n ≥ k+r-1 there is an algebraic polynomial P _n =P _n (x) of degree ≤ n such that P _n '(x) Π (x) ≥ 0 and $$ \vert f(x)-P_n(x) \vert \le B\left(\frac{1}{n^2}+\frac{1}{n}\sqrt{1-x^2}\right)^r \omega_k \left(f^{(r)};\frac{1}{n^2}+\frac{1}{n}\sqrt{1-x^2}\right) \legno{(1)}$$ for all x∈ I, where ω _k (f ^(r) ;t) is the modulus of smoothness of the k -th order of the function f ^(r) and B is a constant depending only on r , k , and Y. If s=1, the constant B does not depend on Y except in the case (r=1, k=3). In addition it is shown that (1) does not hold for r=1, k>3. March 20, 1995. Dates revised: March 11, 1996; December 20, 1996; and August 7, 1997.     

Existence of triple solutions of discrete (n,p) boundary value problems

We consider the following boundary value problem: −Δⁿy = F(k,y, Δy,…,Δⁿ⁻¹y), k ϵ Z[n − 1, N], Δⁱy(0) = 0, 0 ≤ i ≤ n − 2, Δ^py(N + n - p) = 0, where n ≥ 2 and p is a fixed integer satisfying 0 ≤ p ≤ n − 1. Using a fixed-point theorem for operators on a cone, we shall yield the existence of at least three positive solutions.     

A maximum a posteriori estimator for trajectories of diffusion processes

Let x _t be a diffusion process observed via a noisy sensor, whose output is y_t We consider the problem of evaluating the maximum a posteriori trajectory {x_s0≤ s ≤ t Based on results of Stratonovich [1] and Ikeda-Watanabe [2], we show that this estimator is given by the solution of an appropriate variational problem which is a slight modification of the "minimum energy" estimator. We compare our results to the non-linear filtering theory and show that for problems which possess a finite dimensional solution, our approach yields also explicit filters. For linear diffusions observed via linear sensors, these filters are identical to the Kalman-filter     

Exact bounds for simultaneous approximation of functions of two variables and their derivatives by bilinear splines

We find the exact value of the expression $$\varepsilon ^{(l,q)} {\mathbf{ }}(W^{(r,s)} ){\mathbf{ }}H^{w_1 ,w_2 } (G)) = \sup \{ ||f^{(l,q)} ( \cdot {\mathbf{ }}, \cdot ) - S_{1,1}^{(l,q)} (f;{\mathbf{ }} \cdot {\mathbf{ }}, \cdot )||_{C(G)} :f \in W^{(r,{\mathbf{ }}s)} H^{w_1 ,w_2 } (G)\} ,$$ , where? ^(l,q) (x,y)=? ^1+q ?/?x ^l ?y ^q (l, q=0, 1, 1≤l+q≤2) andS _1,1(f; x, y) is a bilinear spline interpolatingf(x, y) in the nodes of the grid Δ _mn =Δ _m ^x ×Δ _n ^y with Δ _m ^x :x _i =i/m (i=0, ..., m) and Δ _n ^y :y _j =j/n (j=0, ..., n). Here $(W^{(r,s)} ){\mathbf{ }}H^{w_1 ,w_2 } (G)$ is the class of functionsf(x, y) with continuous derivativesf ^(r,s)(x, y) (r, s=0, 1, 1≤r+s≤2) on the squareG=[0, 1]×[0, 1] and with the modulus of continuity satisfying the inequalityω(f ^(r,s);t, τ)≤ω ₁ (t)+ω ₂ (τ), whereω ₁ (τ) andω ₂ (τ) are the given moduli of continuity.     

On the rates of the other law of the logarithm

Let X, X1 , X2 , . . . be i.i.d. random variables, and set Sn = X1 +···+Xn , Mn = maxk≤n |Sk|, n ≥1. Let an = o( (n)(1/2)/logn). By using the strong approximation, we prove that, if EX = 0, VarX = σ2 0 and E|X| 2+ε ∞ for some ε 0, then for any r 1, lim ε1/(r-1)(1/2) [ε-2-(r-1)]∞∑n=1 nr-2 P{Mn ≤εσ (π2n/(8log n))(1/2) + an } = 4/π . We also show that the widest a n is o( n(1/2)/logn).     

Bounds on Ramsey Numbers of Certain Complete Bipartite Graphs

Bounds on the Ramsey number r(K_l,m,K_l,n), where we may assume l ≤ m ≤ n, are determined for 3 ≤ l ≤ 5 and m ≈ n. Particularly, for m = n the general upper bound on r(K_l,n, K_l,n) due to Chung and Graham is improved for those l. Moreover, the behavior of r(K_3,m, K_3,n) is studied for m fixed and n sufficiently large.     

On global relations for hypergeometric series

Let [K:Q]=k, f_i εK[[z]], ξ εK, Q εK[y₁,...,y_m]. A relation Q(f₁(ξ),..., f_m(ξ))=0 is called global if it holds in any local field where all f_i(ξ) exist. The paper establishes that for series of the form $$\sum\limits_{n = 0}^\infty {\frac{{(\mu _1 )_n \ldots (\mu _p )_n }}{{(\lambda _1 )_n \ldots (\lambda _{q - 1} )_n n!}}\left( {\frac{{z^{p - q} }}{{q - p}}} \right)^n , p > q,} $$ with some natural hypotheses on parameters global relations do not exist. Bibliography: 9 titles.     

For most large underdetermined systems of equations,the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution

We consider inexact linear equations y ≈ Φx where y is a given vector in ?ⁿ, Φ is a given n × m matrix, and we wish to find x_0,? as sparse as possible while obeying ‖y ? Φx_0,?‖₂ ≤ ?. In general, this requires combinatorial optimization and so is considered intractable. On the other hand, the ??₁‐minimization problem is convex and is considered tractable. We show that for most Φ, if the optimally sparse approximation x_0,? is sufficiently sparse, then the solution x_1,? of the ??₁‐minimization problem is a good approximation to x_0,?. We suppose that the columns of Φ are normalized to the unit ??₂‐norm, and we place uniform measure on such Φ. We study the underdetermined case where m ～ τn and τ > 1, and prove the existence of ρ = ρ(τ) > 0 and C = C(ρ, τ) so that for large n and for all Φ's except a negligible fraction, the following approximate sparse solution property of Φ holds: for every y having an approximation ‖y ? Φx₀‖₂ ≤ ? by a coefficient vector x₀ ∈ ?^m with fewer than ρ · n nonzeros, This has two implications. First, for most Φ, whenever the combinatorial optimization result x_0,? would be very sparse, x_1,? is a good approximation to x_0,?. Second, suppose we are given noisy data obeying y = Φx₀ + z where the unknown x₀ is known to be sparse and the noise ‖z‖₂ ≤ ?. For most Φ, noise‐tolerant ??₁‐minimization will stably recover x₀ from y in the presence of noise z. We also study the barely determined case m = n and reach parallel conclusions by slightly different arguments. Proof techniques include the use of almost‐spherical sections in Banach space theory and concentration of measure for eigenvalues of random matrices. © 2006 Wiley Periodicals, Inc.     

连续统与Turing度

令Ｄ为所有Ｔｕｒｉｎｇ度的集合，≤为Ｄ上的图林化归关系．一函数ｆ：Ｄ→Ｄ称为前进函数如果对任何ａ∈Ｄ，ａ≤ｆ（ａ）。对于一个前进函数ｆ，我们说Ｄ中的两个度ａ，ｂ是ｆ－不可比较的，如果ａ≮ｆ（ｂ）且ｂ ≮ｆ（ａ），否则是ｆ－可比较的．本文的一个主要结果是：在ＺＦＣ中连续统假设成立当且仅当存在一个前进函数ｆ：Ｄ→Ｄ使得Ｄ中任何两个度都是ｆ－可比较的.     

偶数阶Sturm-Liouville边值问题的多个正解

该文讨论了偶数阶边值问题 (-1)^m y^(2m)₌f(t,y), 0≤t≤1,a_i+1y⁽²ⁱ⁾ (0)-β_i+1y ⁽²ⁱ⁺¹⁾ (0)=0, γ_i+1y⁽²ⁱ⁾ (1)+δ_i+1y⁽²ⁱ⁺¹⁾ (1)=0,0≤i ≤m-1正解的存在性.借助于Leggett-Williams 不动点定理,建立了该问题存在三个及任意奇数个正解的充分条件.     

Partitions of bi-partite numbers into at mostj parts

The number of partitions of a bi-partite number into at mostj parts is studied. We consider this function,p _j (x, y), on the linex+y=2n. Forj4, we show that this function is maximized whenx=y. Forj>4 we provide an explicit formula forn _j so that, for allnn _j ,x=y yields a maximum forp _j (x,y).     

Upper bound for the product of nonhomogeneous linear forms

It is proved that for any unimodular lattice Λ with homogeneous minimum L>0 and any set of real numbers α₁, α₂,..., α_n there exists a point (y₁, y₂,..., y_n) of Λ such that $$\Pi _{1 \leqslant i \leqslant n} |y_i + \alpha _i | \leqslant 2^{ - n/2_\gamma n} (1 + 3L^{8/(3n)/(\gamma ^{2/3} - 2L^{8/(3n)} )} )^{ - n/2} ,$$ where γⁿ= n^n/(n?1).