Σ-Bounded algebraic systems and universal functions. I

We introduce the concept of a Σ-bounded algebraic system and prove that if a system is Σ- bounded with respect to a subset A then in a hereditarily finite admissible set over this system there exists a universal Σ-function for the family of functions definable by Σ-formulas with parameters in A. We obtain a necessary and sufficient condition for the existence of a universal Σ-function in a hereditarily finite admissible set over a Σ-bounded algebraic system. We prove that every linear order is a Σ-bounded system and in a hereditarily finite admissible set over it there exists a universal Σ-function.     

Consistency statements and iterations of computable functions in IΣ1 and PRA

In this paper we will state and prove some comparative theorems concerning PRA and IΣ₁. We shall provide a characterization of IΣ₁ in terms of PRA and iterations of a class of functions. In particular, we prove that for this class of functions the difference between IΣ₁ and PRA is exactly that, where PRA is closed under iterations of these functions, IΣ₁ is moreover provably closed under iteration. We will formulate a sufficient condition for a model of PRA to be a model of IΣ₁. This condition is used to give a model-theoretic proof of Parsons’ theorem, that is, IΣ₁ is Π₂-conservative over PRA. We shall also give a purely syntactical proof of Parsons’ theorem. Finally, we show that IΣ₁ proves the consistency of PRA on a definable IΣ₁-cut. This implies that proofs in IΣ₁ can have non-elementary speed up over proofs in PRA.     

An analysis of approximations for maximizing submodular set functions—I

LetN be a finite set andz be a real-valued function defined on the set of subsets ofN that satisfies z(S)+z(T)z(ST)+z(ST) for allS, T inN. Such a function is called submodular. We consider the problem max_SN{a(S):|S|K,z(S) submodular}.Several hard combinatorial optimization problems can be posed in this framework. For example, the problem of finding a maximum weight independent set in a matroid, when the elements of the matroid are colored and the elements of the independent set can have no more thanK colors, is in this class. The uncapacitated location problem is a special case of this matroid optimization problem.We analyze greedy and local improvement heuristics and a linear programming relaxation for this problem. Our results are worst case bounds on the quality of the approximations. For example, whenz(S) is nondecreasing andz(0) = 0, we show that a greedy heuristic always produces a solution whose value is at least 1 –[(K – 1)/K] ^K times the optimal value. This bound can be achieved for eachK and has a limiting value of (e – 1)/e, where e is the base of the natural logarithm.On leave of absence from Cornell University and supported, in part, by NSF Grant ENG 75-00568.Supported, in part, by NSF Grant ENG 76-20274.     

Solvable complete lie algebras. I ∗

In this paper, we will discuss the properties of solvable complete Lie algebra, describe the structures of the root spaces of solvable complete Lie algebra, prove that solvable Lie algebras of maximal rank are com-plete, and construct some new complete Lie algebras from Kac-Moody algebras.     

Vector—valued fractal interpolation functions and their box dimension

Summary We introduce continuous functions f: 1 $$ " align="middle" border="0"> , whose graphs are the attractors of certain iterated function systems, and which interpolate a given set of data or interpolation points ={(t _j ,x _j ):j = 0, 1, , M; M >1} according tof(t _j ) =x _j . The box dimension of the graph of these functions is in general non-integral. We present a formula for this dimension. Applications to the approximation of complicated self-affine functions are indicated.     

A numerical method based on hybrid orthonormal Bernstein and improved block-pulse functions for solving Volterra–Fredholm integral equations

This paper deals with the numerical solution of the integral equations of linear second kind Volterra–Fredholm. These integral equations are commonly used in engineering and mathematical physics to solve many of the problems. A hybrid of Bernstein and improved block-pulse functions method is introduced and used where the key point is to transform linear second-type Volterra–Fredholm integral equations into an algebraic equation structure that can be solved using classical methods. Numeric examples are given which demonstrate the related features of the process.     

Measures of inset information on the open domain — I: Inset entropies and information functions of all degrees

This is one in a series of papers studying measures of information in the so-called mixed theory of information (i.e. considering the events as well as their probabilities) on the open domain (i.e. without empty sets and zero probabilities). In this paper we find all-recursive, 3-semisymmetric inset entropies on the open domain. We do this by solving the fundamental equation of inset information of degree () on the open domain.Dedicated to Professor János Aczél on his 60th birthday.     

Gleason’s problem,rational functions and spaces of left-regular functions: The split-quaternion setting

We study Gleason’s problem, rational functions and spaces of regular functions in the setting of split-quaternions. There are two natural symmetries in the algebra of split-quaternions. The first symmetry allows to define positive matrices with split-quaternionic entries, and also reproducing Hilbert spaces of regular functions. The second leads to reproducing kernel Krein spaces.     

Best trigonometric and bilinear approximations of functions of several variables from the classes Bp,θr· I

Approximations are studied of the classes B_p,^r of periodic functions of several variables with the help of trigonometric polynomials with a given number of harmonics. The results obtained are used to establish order estimates of the approximation of functions of the form f(x–y), f(x) B_p,^r, by combinations of products of functions of a fewer number of variables.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 44, No. 11, pp. 1535–1547, November, 1992.     

Increasing functions and inverse Santaló inequality for unconditional functions

Let be a convex function and be its Legendre tranform. It is proved that if is invariant by changes of signs, then . This is a functional version of the inverse Santaló inequality for unconditional convex bodies due to J. Saint Raymond. The proof involves a general result on increasing functions on together with a functional form of Lozanovskii’s lemma. In the last section, we prove that for some c > 0, one has always . This generalizes a result of B. Klartag and V. Milman.      

A sandwich theorem and Hyers—Ulam stability of affine functions

It is shown that two real functionsf andg, defined on a real intervalI, satisfy the inequalitiesf(x + (1 – )y) g(x) + (1 – )g(y) andg(x + (1 – )y) f(x) + (1 – )f(y) for allx, y I and [0, 1], iff there exists an affine functionh: I such thatf h g. As a consequence we obtain a stability result of Hyers—Ulam type for affine functions.     

On α-times integrated C-cosine functions and abstract Cauchy problem I

In this paper we first investigate some basic properties concerning nondegenerate α-times integrated C-cosine functions on a Banach space X, and then characterize their generator A in terms of the unique existence of strong solutions of the following abstract Cauchy problem: for t>0, u(0)=x, u^′(0)=y.     

Zonal spherical functions on CROSS’s and special functions

We find formulas for the eigenvalues of the Laplacian and the zonal spherical functions on all simply-connected CROSS??s by a simple method, using the trigonometric formulas of spherical geometry, Hopf fiber bundles, and the results on the spectra of the Laplacian on the total space and on the base of a Riemannian submersion with totally geodesic fibers. We find direct relations of the so-obtained zonal spherical functions to the special functions: hypergeometric finite Gauss series, Jacobi polynomials, and orthogonal polynomials including the ultraspherical Gegenbauer polynomials whose particular cases are given by the Legendre polynomials and the Chebyshev polynomials of the first and second kinds. We point out the relations to the corresponding results by Helgason and Berger with coauthors and give brief information about the method of calculating the spectra of the Laplacian on compact simply-connected irreducible Riemannian spaces and the spectra of the Laplacian on the CROSS??s obtained therefrom.     

On random walks arising in queueing systems: ergodicity and transience via quadratic forms as lyapounov functions — Part I

A simple and quite general approach is proposed to derive criteria for transience and ergodicity of a certain class of irreducibleN-dimensional Markov chains in ₊ ^N assuming a boundedness condition on the second moment of the jumps. The method consists in constructing convenient smooth supermartingales outside some compact set. The Lyapounov functions introduced belong to the set of quadratic forms in ₊ ^N and do not always have a definite sign. Existence and construction of these forms is shown to be basically equivalent to finding vectors satisfying a system of linear inequalities.Part I is restricted toN=2, in which case a complete characterization is obtained for the type of random walks analyzed by Malyshev and Mensikov, thus relaxing their condition of boundedness of the jumps. The motivation for this work is partly from a large class of queueing systems that give rise to random walks in ₊ ^N