The Ramsey property for collections of sequences not containing all arithmetic progressions

A family of sequences has the Ramsey property if for every positive integerk, there exists a least positive integerf (k) such that for every 2-coloring of {1,2, ...,f (k)} there is a monochromatick-term member of . For fixed integersm > 1 and 0 q < m, let _q(m) be the collection of those increasing sequences of positive integers {x ₁,..., x_k} such thatx _i+1 – x_i q(modm) for 1 i k – 1. Fort a fixed positive integer, denote byA _t the collection of those arithmetic progressions having constant differencet. Landman and Long showed that for allm 2 and 1 q < m, _q(m) does not have the Ramsey property, while _q(m) A _m does. We extend these results to various finite unions of _q(m) 's andA _t 's. We show that for allm 2, _q=1 ^m–1 _q(m) does not have the Ramsey property. We give necessary and sufficient conditions for collections of the form _q(m) ( _{t T} A _t) to have the Ramsey property. We determine when collections of the form _a(m₁) _b(m₂) have the Ramsey property. We extend this to the study of arbitrary finite unions of _q(m)'s. In all cases considered for which has the Ramsey property, upper bounds are given forf .     

The Logarithmic Frequency of Values of Additive Functions

We consider the weak convergence of distribution functions (_mx 1/ m)^-1 _{m x},f_x(m)x is a set (x 2) of strongly additive functions such that f_x(p){0,1} for each prime number p.     

Symmetrische Permutationsmengen

A permutation set (M, I) consisting of a setM and a set of permutations ofM, is calledsymmetric, if for any two permutations, the existence of anx M with (x) (x) and ^–1 (x) = ^–1 (x) implies ^–1 = ^–1 , andsharply 3-transitive, if for any two triples (x ₁,x ₂,x ₃), (y ₁,y ₂,y ₃) M ³ with|{x ₁,x ₂,x ₃ }| = |{y ₁,y ₂,y ₃ }| = 3 there is exactly one permutation with(x ₁) =y ₁,(x ₂) =y ₂,(x ₃) =y ₃. The following theorem will be proved.THEOREM.Let (M, ) be a sharply 3-transitive symmetric permutation set with |M|3, such that contains the identity. Then is a group and there is a commutative field K such that and the projective linear group PGL(2, K) are isomorphic.     

Sur les équations fonctionnelles auxq-différences

Summary In this paper, we study the convergence of formal power series solutions of functional equations of the formP _k(x)(^[k](x))=(x), where ^[k] (x) denotes thek-th iterate of the function.We obtain results similar to the results of Malgrange and Ramis for formal solutions of differential equations: if(0) = 0, and(0) =q is a nonzero complex number with absolute value less than one then, if(x)=a(n)x ⁿ is a divergent solution, there exists a positive real numbers such that the power seriesa(n)q ^sn(n+1)2 x ⁿ has a finite and nonzero radius of convergence.

     

A generalization of the inversion formulas of systems of power series in systems of implicit functions

Using a multidimensional analog of the logarithmic residue, equations are derived expressing the coefficients of the power series of implicit functionsx _j =_j(w)=_j(w₁,...,w_m), j=1,...,n, defined by the system of equations f_j(w, x)=F_j (w₁,...,w_m:z₁,...,x _n )=0, j=1,...,n,f _j , (0, 0)=0, F_j(0, 0)/z_k=_jk in a neighborhood of the point (0, 0)C _(w,x) ^m+n , in terms of the coefficients of the power series of the functions F_j(w, z), j=1, ..., n. As a corollary, well-known formulas are obtained for the inversion of multiple power series.Translated from Matematicheskie Zametki, Vol. 23, No. 1, pp. 47–54, January, 1978.     

Efficiency of Proximal Bundle Methods

We give efficiency estimates for proximal bundle methods for finding f_*min_Xf, where f and X are convex. We show that, for any accuracy <0, these methods find a point x^kX such that f(x^k)–f^* after at most k=O(1/³) objective and subgradient evaluations.     

Affine modifications and affine hypersurfaces with a very transitive automorphism group

We study the modificationAA of an affine domainA which produces another affine domainA=A[I/f] whereI is a nontrivial ideal ofA andf is a nonzero element ofI. First appeared in passing in the basic paper of O. Zariski [Zar], it was further considered by E. D. Davis [Da]. In [Ka1] its geometric counterpart was applied to construct contractible smooth affine varieties non-isomorphic to Euclidean spaces. Here we provide certain conditions (more general than those in [Ka1]) which guarantee preservation of the topology under a modification.As an application, we show that the group of biregular automorphisms of the affine hypersurfaceXC ^k+2, given by the equationuv=(p(x ₁,...,x_k) wherepC[x ₁,...,x _k ],k2, actsm-transitively on the smooth part regX ofX for anymN. We present examples of such hypersurfaces diffeomorphic to Euclidean spaces.Partially supported by the NSA grant MDA904-96-01-0012.     

Solving systems of polynomial inequalities over a real closed field in subexponential time

Let _m= (₁,..., _m) denote an ordered field, where _i+1>0 is infinitesimal relative to the elements of _i, 0 < –i < m (by definition, ₀= ). Given a system of inequalities f₁ > 0, ..., f_s > 0, f_s+1 0, ..., f_k 0, where f_{j m} [X₁,..., X_n] are polynomials such that, and the absolute value of any integer occurring in the coefficients of the f_js is at most 2^M. An algorithm is constructed which tests the above system of inequalities for solvability over the real closure of _m in polynomial time with respect to M, ((d)ⁿd₀)^n+m. In the case _m=, the algorithm explicitly constructs a family of real solutions of the system (provided the latter is consistent). Previously known algorithms for this problem had complexity of the order ofM(d d ₀ ^{m 2U(n)} .Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Maternaticheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 3–36, 1988.     

Two-sided polynomial approximation of functions

Conditions are established when the collocation polynomials P_m(x) and P_M(x), m M, constructed respectively using the system of nodes x_j of multiplicities a_j 1, j = O,, n, and the system of nodes x_-r,,x_o,,x_n,,x_n+r1, r O, r₁ O, of multiplicities a_-r,,(a_o + y_o),,(a_n + y_n),,a_n+r1, a_j + y_j 1, are two sided-approximations of the function f on the intervals , x_j[, j = O,...,n + 1, and on unions of any number of these intervals. In this case, the polynomials P_m (x), P_M ^(l) (x) with l a_j are two-sided approximations of the function f⁽¹⁾ in the neighborhood of the node x_j and the integrals of the polynomials P_m(x), P_M(x) over D_j are two-sided approximations of the integral of the function f (over D_j). If the multiplicities a_j a_j + y_j of the nodes x_j are even, then this is also true for integrals over the set _j= _µ ^k D_j µ 1, k n. It is shown that noncollocation polynomials (Fourier polynomials, etc.) do not have these properties.Kiev University. Translated from Vychislitel'naya i Prikladnaya Matematika, No. 67, pp. 31–37, 1989.     

Bestimmung der Eigenwerte und Eigenvektoren einer Matrix mit Hilfe des Quotienten-Differenzen-Algorithmus

Summary Two previous papers (in Vol. V) describe theory and some applications of the quotient-difference (=QD-) algorithm. Here we give an extension which allows the determination of the eigenvectors of a matrix. Letx ₍₀₎ ¹ , ...,x ₍₀₎ ⁿ be a coordinate system in whichA has Jacobi form (such a system may be constructed with methods ofC. Lanczos orW. Givens). Then the QD-algorithm allows the construction of a sequence of coordinate systemsx ₍₂₎ ¹ , ...,x ₍₂₎ ⁿ , (=0, 1, 2, ...) which converge for to the system of the eigenvectors ofA.     

A functional inequality for real-analytic functions

Summary Forf ( C ⁿ() and 0 t x letJ _n (f, t, x) = (–1)ⁿ f(–x)f ⁽ⁿ⁾(t) +f(x)f ⁽ⁿ⁾ (–t). We prove that the only real-analytic functions satisfyingJ _n (f, t, x) 0 for alln = 0, 1, 2, are the exponential functionsf(x) = c e ^x,c, . Further we present a nontrivial class of real-analytic functions satisfying the inequalitiesJ ₀ (f, x, x) 0 and ₀ ^x (x – t)^{n – 1}J_n(f, t, x)dt 0 (n 1).     

Kolmogorov and linear widths of weighted Sobolev-type classes on a finite interval

Let I be a finite interval, r N and p(t)=dist{t,I}, tI. Denote by W ^r _{p ,}, 0<<, the class of functions x on I with the seminorm x ^(r) p _Lp1. We obtain two-sided estimates of the Kolmogorov widths d _n(W^r _p, )_Lq and of the linear widths d _n(W^r _p,)_Lq ^lin     

A quadrature formula for the Hankel transform

We present in this paper a quadrature formula for a certain Fourier-Bessel transform and, closely related to this, for the Hankel transform of order >–1. Such formulas originate in the context of a Galerkin-type projection of the weightedL ₂(–, ; ) space ( is the weight function mentioned below) used to get a discrete representation of a certain physical problem in Quantum Mechanics. The generalized Hermitee polynomialsH ₀ (x),H ₁ (x),..., with weight function (x), are used as the basis on which such a projection takes place. It is shown that theN-dimensional vectors representing certain projected functions as well as the entries of theN×N matrix representing the kernel of that Fourier-Bessel transform, approach the exact functional values at the zeros of theNth generalized Hermitee polynomial whenN.These properties lead to propose this matrix as a finite representation of the kernel of the Fourier-Bessel transform involved in this problem and theN zeros of the generalized Hermitee polynomialH _N (x) as abscissas to yield certain quadrature formulae for this integral and for the related Hankel transform. The error function produced by this algorithm is estimated at theN nodes and its is shown to be of a smaller order than 1/N. This error estimate is valid for piecewise continuous functions satisfying certain integral conditions involving their absolute values. The algorithm is presented with some numerical examples.     

An Inequality for Tail Probabilities of Martingales with Bounded Differences

Let M _n =X₁+...+X_n be a martingale with bounded differences X_m=M_m-M_m-1 such that {|X_m| _m}=1 with some nonnegative _m. Write ²= ₁ ² + ... + _n ² . We prove the inequalities {M _nx}c(1-(x/)), {M _n x} 1- c(1- (-x/)) with a constant . The result yields sharp inequalities in some models related to the measure concentration phenomena.     

On a hypothesis on Poincaré series

Let F(x₁,..., x_m) (m1) be a polynomial with integral p-adic coefficients, and let N, be the number of solutions of the congruence F(x₁,..., X_m)=0 mod A proof is given that the Poincaré series (t) = ₀ N t is rational for a class of isometrically-equivalent polynomials of m variables (m2) containing a form of degree n2 of two variables.Translated from Matematicheskie Zametki, Vol. 14, No. 3, pp. 453–463, September, 1973.The author wishes to thank N. G. Chudakov for discussing this paper and for his helpful advice.     

Asymptotics of Solutions of the Sturm–Liouville Equation with Respect to a Parameter

On a finite segment [0, l], we consider the differential equation

Approximation of the viability kernel

We study recursive inclusionsx ⁿ⁺¹ G(x ⁿ ). For instance, such systems appear for discrete finite-difference inclusionsx ⁿ⁺¹ G (x ⁿ) whereG :=1+F. The discrete viability kernel ofG , i.e., the largest discrete viability domain, can be an internal approximation of the viability kernel ofK underF. We study discrete and finite dynamical systems. In the Lipschitz case we get a generalization to differential inclusions of the Euler and Runge-Kutta methods. We prove first that the viability kernel ofK underF can be approached by a sequence of discrete viability kernels associated withx ⁿ⁺¹ (xⁿ) where (x) =x + F(x) + (ML/2) ². Secondly, we show that it can be approached by finite viability kernels associated withx _h ⁿ⁺¹ ( (x _h ⁿ⁺¹ ) +(h) X _h .     

An implicit function theorem

Suppose thatF:DR ⁿ×R^mRⁿ, withF(x ⁰,y ⁰)=0. The classical implicit function theorem requires thatF is differentiable with respect tox and moreover that ₁ F(x ⁰,y ⁰) is nonsingular. We strengthen this theorem by removing the nonsingularity and differentiability requirements and by replacing them with a one-to-one condition onF as a function ofx.     

An automatic integration procedure for infinite range integrals involving oscillatory kernels

Let the real functionsK(x) andL(x) be such thatM(x)=K(x)+iL(x)=e^ix g(x), whereg(x) is infinitely differentiable for all largex and is non-oscillatory at infinity. We develop an efficient automatic quadrature procedure for numerically computing the integrals _a K(t)f(t) and _a L(t)f(t)dt, where the functionf(t) is smooth and nonoscillatory at infinity. One such example for which we also provide numerical results is that for whichK(x)=J (x) andL(x)=Y (x), whereJ (x) andY (x) are the Bessel functions of order . The procedure involves the use of an automatic scheme for Fourier integrals and the modified W-transformation which is used for computing oscillatory infinite integrals.     

Properties of solutions of linear functional-differential equations depending on a parameter

On the segment 0 t1 we study the equation A(d/dt, )x(t) + [F()x](t)=f(t), whereA (d/dt, ) x=x( ⁿ )+A ₁ x(^n–1 +...+ ⁿ A _n x, the matrices A₁,...,A_n are of size m × m, x is an unknown and f a given function with values in the m-dimensional space ^m , F() is a linear operator acting from a Hölder space to a Lebesgue space of vectorfunctions with values in ^m and depending on a complex parameter . We find the set of those at which a one-to-one correspondence is established between the solutions of the given equation and the solutions of the equation A(d/dt, )x(t)=0.Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 43, No. 9, pp. 1213–1231, September, 1991.