Upward closure and cohesive degrees

It is shown that the degrees of unsolvability of sets having almost any sort of immunity or cohesiveness property studied in recursion theory are closed upwards. From this it follows that every degreea witha′≧0″ contains a cohesive set. This research was supported by National Science Foundation Grant GP 29223.     

The weak density of properly d-r.e. branching degree in the d-r.e. degrees

It is proved that for any r.e. degreesv <u, there exists a properly d-r.e. degreec such thatc is a branching degree andv <c <u. Project supported by the National Natural Science Foundation of China (Grant No. 19771045) and National 863 Hi-Tech R&D Programme.     

There is no plus-capping degree

Summary Answering a question of Per Lindström, we show that there is no plus-capping degree, i.e. that for any incomplete r.e. degreew, there is an incomplete r.e. degreea>w such that there is no r.e. degreev>w withav=w.Mathematics subject classification: 03D30The authors would like to thank Per Lindström for raising the question and Carl Jockusch for communicating it to them. The first author was partially supported by a U.S./New Zealand binational grant. The second author was partially supported by NSF grant DMS-9100114 and the U.S./New Zealand binational NSF grant INT-9020558     

Continuity of Julia sets

A sufficient and necessary condition is given for the continuity of Julia sets in the space of all rational maps with degreek>1. Project supported by the National Natural Science Foundation of China (Grant No. 19871002).     

On the dimension of bivariate spline spaces of smoothnessr and degreed=3r+1

Summary We consider the well-known spaces of bivariate piecewise polynomials of degreed defined over arbitrary triangulations of a polygonal domain and possessingr continuous derivatives globally. To date, dimension formulae for such spaces have been established only whend3r+2, (except for the special case wherer=1 andd=4). In this paper we establish dimension formulae for allr1 andd=3r+1 for almost all triangulations.Dedicated to R. S. Varga on the occasion of his sixtieth birthdaySupported in part by National Science Foundation Grant DMS-8701121Supported in part by National Science Foundation Grant DMS-8602337     

Quadrature formulae with multiple nodes and a maximal trigonometric degree of exactness

In this paper we consider interpolatory quadrature formulae with multiple nodes, which have the maximal trigonometric degree of exactness. Our approach is based on a procedure given by Ghizzeti and Ossicini (Quadrature formulae, Academie-Verlag, Berlin, 1970). We introduce and consider the so-called σ-orthogonal trigonometric polynomials of semi-integer degree and give a numerical method for their construction. Also, some numerical examples are included. The authors were supported in part by the Serbian Ministry of Science and Technological Development (Project: Orthogonal Systems and Applications, grant number #144004) and the Swiss National Science Foundation (SCOPES Joint Research Project No. IB7320-111079 “New Methods for Quadrature”).     

On the value distribution of <Emphasis Type="Italic">ƒ</Emphasis> + <Emphasis Type="Italic">a</Emphasis>(<Emphasis Type="Italic">ƒ</Emphasis>′)<Superscript><Emphasis Type="Italic">n</Emphasis></Superscript>

Let ƒ be a transcendental meromorphic function, a a nonzero finite complex number, and n ⩾ 2 a positive integer. Then ƒ + a(ƒ′) ⁿ assumes every complex value infinitely often. This answers a question of Ye for n = 2. A related normality criterion is also given. This work was supported by the National Natural Science Foundation of China (Grant No. 10771076), the Natural Science Foundation of Guangdong Province, China (Grant No. 07006700) and by the German-Israeli Foundation for Scientific Research and Development (Grant No. G-809-234.6/2003)     

On Lachlan’s major sub-degree problem

The Major Sub-degree Problem of A. H. Lachlan (first posed in 1967) has become a long-standing open question concerning the structure of the computably enumerable (c.e.) degrees. Its solution has important implications for Turing definability and for the ongoing programme of fully characterising the theory of the c.e. Turing degrees. A c.e. degree a is a major subdegree of a c.e. degree b > a if for any c.e. degree x, if and only if . In this paper, we show that every c.e. degree b ≠ 0 or 0′ has a major sub-degree, answering Lachlan’s question affirmatively. Both authors were funded by EPSRC Research Grant no. GR/M 91419, “Turing Definability”, by INTAS-RFBR Research Grant no. 97-0139, “Computability and Models”, and by an NSFC Grand International Joint Project Grant no. 60310213, “New Directions in Theory and Applications of Models of Computation”. Both authors are grateful to Andrew Lewis for helpful suggestions regarding presentation, technical aspects of the proof, and verification. A. Li is partially supported by National Distinguished Young Investigator Award no. 60325206 (People’s Republic of China).     

Solving combinatorial optimization problems using Karmarkar's algorithm

We describe a cutting plane algorithm for solving combinatorial optimization problems. The primal projective standard-form variant of Karmarkar's algorithm for linear programming is applied to the duals of a sequence of linear programming relaxations of the combinatorial optimization problem.Computational facilities provided by the Cornell Computational Optimization Project supported by NSF Grant DMS-8706133 and by the Cornell National Supercomputer Facility. The Cornell National Supercomputer Facility is a resource of the Center for Theory and Simulation in Science and Engineering at Cornell Unversity, which is funded in part by the National Science Foundation, New York State, and the IBM Corporation. The research of both authors was partially supported by the U.S. Army Research Office through the Mathematical Sciences Institute of Cornell University.Research partially supported by ONR Grant N00014-90-J-1714.Research partially supported by NSF Grant ECS-8602534 and by ONR Contract N00014-87-K-0212.     

Rosenthal type inequalities forB-valued strong mixing random fields and their applications

Some inequalities for moments of partial sums of aB -valued strong mixing field are established and their applications to the weak and strong laws of large numbers and the complete convergences are discussed. Project supported by the National Natural Science Foundation of China (Grant No. 19701011) and China Postdoctoral Science Foundation.     

Computing the link center of a simple polygon

The link center of a simple polygonP is the set of pointsx insideP at which the maximal link-distance fromx to any other point inP is minimized. Here the link distance between two pointsx, y insideP is defined to be the smallest number of straight edges in a polygonal path insideP connectingx toy. We prove several geometric properties of the link center and present an algorithm that calculates this set in timeO(n ²), wheren is the number of sides ofP. We also give anO(n logn) algorithm for finding an approximate link center, that is, a pointx such that the maximal link distance fromx to any point inP is at most one more than the value attained from the true link center.Work on this paper by the second author has been supported by National Science Foundation Grant DMS-8501947. Work by the third author has been supported by the Canadian National Science and Engineering Research Council, Grant A0332. Work by the fifth author has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation. Work by the seventh author has been supported by a Killam Senior Research Fellowship from the Canada Council, and work by the ninth author has been supported by the National Science Foundation Grants DCR-84-01898 and DCR-84-01633. Part of the work on this paper has been carried out at the Workshop on Movable Separability of Sets at the Bellairs Research Institute of McGill University, Barbados, February 1986. Further acknowledgments can be obtained from the tenth author upon request.     

Uniform embeddings of metric spaces and of banach spaces into hilbert spaces

It is proved using positive definite functions that a normed spaceX is unifomly homeomorphic to a subset of a Hilbert space, if and only ifX is (linearly) isomorphic to a subspace of aL ₀(μ) space (=the space of the measurable functions on a probability space with convergence in probability). As a result we get thatl _p (respectivelyL _p (0, 1)), 2<p<∞, is not uniformly embedded in a bounded subset of itself. This answers negatively the question whether every infinite dimensional Banach space is uniformly homeomorphic to a bounded subset of itself. Positive definite functions are also used to characterize geometrical properties of Banach spaces. Partially supported by the National Science Foundation, Grant MCS-79-03322. Partially supported by the National Science Foundation, Grant MCS-80-06073.     

Two Kinds of Numbers and Their Applications

C. Radoux （J. Comput. Appl. Math., 115 （2000） 471-477） obtained a computational formula of Hankel determinants on some classical combinatorial sequences such as Catalan numbers and polynomials, Bell polynomials, Hermite polynomials, Derangement polynomials etc. From a pair of matrices this paper introduces two kinds of numbers. Using the first kind of numbers we give a unified treatment of Hankel determinants on those sequences, i.e., to consider a general representation of Hankel matrices on the first kind of numbers. It is interesting that the Hankel determinant of the first kind of numbers has a close relation that of the second kind of numbers.     

Normal approximation for finite-populationU-statistics

In this article, the general central limit theorem and Berry-Esseen bounds for finite-populationU-statistics with degreem are established under the very weak conditions. These results substantially improve those of Zhao and Ohen's (1987).This work was done when the authors were at the Center for Multivariate Analysis, University of Pittsburgh. The research is sponsored by the Air Force Office of Scientific Research under Contract F49620-85-C-0008.This work is also supported in part by the National Natural Science Foundation of China.     

Hypersurface variations are maximal,I

Summary The variation of Hodge structure defined by the natural family of hypersurfaces of degreed and dimensionn is maximal if the cohomology has Hodge level >1. There is a small list of hypersurfaces of level one which give non-maximal variations: plane curves of degreed5, cubics of dimension 3 and 5, and quartic threefolds.Research partially supported by the National Science Foundation     

Analysis of search-extension method for finding multiple solutions of nonlinear problem

For numerical computations of multiple solutions of the nonlinear elliptic problemΔu f(u)=0 inΩ, u=0 onΓ, a search-extension method (SEM) was proposed and systematically studied by the authors. This paper shall complete its theoretical analysis. It is assumed that the nonlinearity is non-convex and its solution is isolated, under some conditions the corresponding linearized problem has a unique solution. By use of the compactness of the solution family and the contradiction argument, in general conditions, the high order regularity of the solution u∈H~(1 α),α>0 is proved. Assume that some initial value searched by suitably many eigenbases is already fallen into the neighborhood of the isolated solution, then the optimal error estimates of its nonlinear finite element approximation are shown by the duality argument and continuation method.     

On complex eigenvalues ofM andP matrices

Summary Inequalities are obtained for the complex eigenvalues of anM matrix or aP matrix which depend only on the order of the matrix.This research was supported in part by the National Science Foundation under Grant GP-20555.     

Moderate deviations for the quenched mean of the super-Brownian motion with random immigration

Moderate deviations for the quenched mean of the super-Brownian motion with random immigration are proved for 3≤d≤6, which fills in the gap between central limit theorem(CLT)and large deviation principle(LDP).     

Uniqueness in the dirichlet problem for some elliptic operators with discontinuous coefficients

Uniqueness is proved for the Dirichlet problem for second order nondivergence form elliptic operators with coefficients continuous except at a countable set of points having at most one accumulation point. Moreover, gradient estimates are proved.The authors are partially supported by the National Science Foundation Grant no. NSF/DMS 8421377-04.     

Converse and saturation results on Tikhonov regularization together witha posteriori parameter choice

Some converse and saturation results on Tikhonov regularization of nonlinear ill-posed problems are proved and the aposteriori parameter choice yielding optimal rates of convergence is discussed Project supported by the National Natural Science Foundation of China (Grant No. 9801018).