On the cost of approximating all roots of a complex polynomial

This work examines the computational complexity of a homotopy algorithm in approximating all roots of a complex polynomialf. It is shown that, probabilistically, monotonic convergence to each of the roots occurs after a determined number of steps. Moreover, in all subsequent steps, each rootz is approximated by a complex numberx, where ifx ₀ =x, x _j =x _j–1 –f(x _j–1)/f(x _j–1),j = 1, 2,, then |x _j –z| < (1/|x ₀ –z|)|x _j–1–z|².     

On a characterization of polynomials by divided differences

Summary We consider the functional equationf[x ₁,x ₂,, x _n ] =h(x ₁ + +x _n ) (x ₁,,x _n K, x _j x _k forj k), (D) wheref[x ₁,x ₂,,x _n ] denotes the (n – 1)-st divided difference off and prove Theorem. Let n be an integer, n 2, let K be a field, char(K) 2, with # K 8(n – 2) + 2. Let, furthermore, f, h: K K be functions. Then we have that f, h fulfil (D) if, and only if, there are constants a_j K, 0 j n (a := a_n, b := a_{n – 1}) such thatf = ax ⁿ +bx ^{n – 1} + +a ₀ and h = ax + b.     

An Inequality on the Size of a Set in a Cartesian Product

Let Ω be a finite subset of the Cartesian productW₁  ×   × W_nof n sets. ForA    {1, 2, , n }, denote by Ω_Athe projection ofΩ onto the Cartesian product of W_i, i   A. Generalizing an inequality given in an article by Shen, we prove that | Ω |² ≤  |Ω_A1 || Ω_Ak| provided that { A₁, , A_k} is a double cover of {1, 2, , n }. This inequality is applied to give some bounds on the numbers of special subgraphs of a graph.     

Approximate computation of the positive eigenvalue of a positive operator with a nonlinear occurrence of a parameter

A method is indicated for the approximate determination of the positive eigenvalue of the problem x–Qx=0, >0, xK, x0, whereK is a cone in Banach space and Q is an operator-valued function positive relative toK.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 58, pp. 37–39, 1976.     

On the order of approximation of a continuous 2π-periodic function by Fejer and Poisson means of its Fourier series

Let _n (f) and P_r (f) be, respectively, the Fejer and Poisson means of the Fourier series of the functionf. The present work considers problems associated with the rapidity of approximation of a continuous 2-periodic function by means of Fejer and Poisson processes, and gives, in particular, an upper bound to the deviation of the Fejer and Poisson processes from the function in terms of moduli of continuity, and a lower bound to _n (f)–f in terms of functionals composed of best approximations to the functionf; in addition, some relationships among the quantities P_r (f)–f and _n (f)–f are established.Translated from Matematicheskie Zametki, Vol. 4, No. 1, pp. 21–32, July, 1968.     

Extensions of an inequality of Bonnesen toD-dimensional space and curvature conditions for convex bodies

For convex bodies inE ^d (d 3) with diameter 2 we consider inequalitiesW _i – W _d–1 +( - 1) W _d 0 (i = 0, , d – 2) whereW _j are the quermassintegrals. In addition, for a ball, equality is attained for a body of revolution for which the elementary symmetric functions _d–1–i of main curvature radii is constant. The inequality is actually proved fori = d – 2 by means of Weierstrass's fundamental theorem of the calculus of variations.Dedicated to Professor Otto Haupt with best wishes on his 100th birthday     

Law of the iterated logarithm for the quadratic variation of a wiener process

LetP _a be the class of those partitions of intervals [,T], such that |t _i –t _i–1 |>a, wherea is a constant, . It is proved that for anya lim V(T,P _a )/2Tln ₂T=1 a. s., whereln _i x=ln ln x, ifln x e,ln ₂ x=1, ifln x <e.Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 158, pp. 72–80, 1987.     

Number of no nisomorphic subgraphs in an n-point graph

LetG(n) be the set of all nonoriented graphs with n enumerated points without loops or multiple lines, and let v_k(G) be the number of mutually nonisomorphic k-point subgraphs of G G(n). It is proved that at least |G(n)| (1–1/n) graphs G G(n) possess the following properties: a) for any k [6log₂n], where c=–c log₂c–(1–c)×log₂(1–c) and c>1/2, we havev _k(G) > C _n ^k (1–1/n²); b) for any k [cn + 5 log₂n] we havev _k(G) = C _n ^k . Hence almost all graphs G G(n) containv(G) 2ⁿ pairwise nonisomorphic subgraphs.Translated from Matematicheskie Zametki, Vol. 9, No. 3, pp. 263–273, March, 1971.     

Regularity and explicit representation of (0,1,...,m−2,m) interpolation on the zeros of (1−x 2)P n −2/(α,β) (x)

Necessary and sufficient conditions for the regularity andq-regularity of (0,1,...,m–2,m) interpolation on the zeros of (1–x ²)P _n ^–2/(,) (x) (,>–1) in a manageable form are established, whereP _n ^–2/(,) (x) stands for the (n–2)th Jacobi polynomial. Meanwhile, the explicit representation of the fundamental polynomials, when they exist, is given. Moreover, we show that under a mild assumption if the problem of (0,1,...,m–2,m) interpolation has an infinity of solutions then the general form of the solutions isf ₀(x)+C f(x) with an arbitrary constantC.This work is supported by the National Natural Science Foundation of China.     

The average a posteriori error of numerical methods

Summary The definition of the average error of numerical methods (by example of a quadrature formula to approximateS(f)= f d on a function classF) is difficult, because on many important setsF there is no natural probability measure in the sense of an equidistribution. We define the average a posteriori error of an approximation by an averaging process over the set of possible information, which is used by (in the example of a quadrature formula,N(F)={(f(a ₁), ...,f/fF} is the set of posible information). This approach has the practical advantage that the averaging process is related only to finite dimensional sets and uses only the usual Lebesgue measure. As an application of the theory I consider the numerical integration of functions of the classF={f:[0,1]/f(x)–f(y)||x–y|}. For arbitrary (fixed) knotsa _i we determine the optimal coefficientsc _i for the approximation and compute the resulting average error. The latter is minimal for the knots . (It is well known that the maximal error is minimal for the knotsa _i .) Then the adaptive methods for the same problem and methods for seeking the maximum of a Lipschitz function are considered. While adaptive methods are not better when considering the maximal error (this is valid for our examples as well as for many others) this is in general not the case with the average error.     

A Szemerédi-type regularity lemma in abelian groups, with applications

Szemerédi’s regularity lemma is an important tool in graph theory which has applications throughout combinatorics. In this paper we prove an analogue of Szemerédi’s regularity lemma in the context of abelian groups and use it to derive some results in additive number theory. One is a structure theorem for sets which are almost sum-free. If has δ N² triples (a₁, a₂, a₃) for which a₁ + a₂ = a₃ then A = B ∪ C, where B is sum-free and |C| = δ′N, and as Another answers a question of Bergelson, Host and Kra. If 0,$$" align="middle" border="0"> if \,N_{0}(\alpha, \epsilon)$$" align="middle" border="0"> and if has size α N, then there is some d ≠ 0 such that A contains at least three-term arithmetic progressions with common difference d.Received: November 2003 Revision: October 2004 Accepted: December 2004     

On the extreme spectral properties of Toeplitz matrices generated byL 1 functions with several minima/maxima

In this paper we are concerned with the asymptotic behavior of the smallest eigenvalue ₁ ⁽ⁿ⁾ of symmetric (Hermitian)n ×n Toeplitz matricesT _n (f) generated by an integrable functionf defined in [–, ]. In [7, 8, 11] it is shown that ₁ ⁽ⁿ⁾ tends to essinff =m _f in the following way: ₁ ⁽ⁿ⁾ –m _f 1/n ^2k . These authors use three assumptions:A1)f –m _f has a zero inx =x ₀ of order 2k.A2)f is continuous and at leastC ^2k in a neighborhood ofx ₀.A3)x =x ₀ is the unique global minimum off in [–, ]. In [10] we have proved that the hypothesis of smoothnessA2 is not necessary and that the same result holds under the weaker assumption thatf L ¹[–, ]. In this paper we further extend this theory to the case of a functionf L ¹[–, ] having several global minima by suppressing the hypothesisA3 and by showing that the maximal order 2k of the zeros off –m _f is the only parameter which characterizes the rate of convergence of ₁ ⁽ⁿ⁾ tom _f .     

An asymptotically complete class of tests

Summary This paper investigates sequences of asymptotically similar critical regions {S _n >0},n, under the assumption that the test-statisticS _n admits a certain stochastic expansion. It is shown that for such test-sequences, first order efficiency implies second order efficiency (i.e. efficiency up to an error termo(n ^–1/2)). Moreover, the asymptotic power functions of first order efficient test-sequences are determined up to an error termo(n ^–1), and a class of critical regions is specified which is minimal essentially complete up too(n ^–1).The results of this paper rest upon the technique of Edgeworth-expansions and are, therefore, restricted to continuous probability distributions.     

Integrability of certain solutions of differential equations

Let L=P_o(d/d_t)ⁿ+P₁(d/d_t)^n–1+...+P_n denote a formally self-adjoint differential expression on an open intervalI=(a, b) (–a. Here the P_k are complex valued with (n — k) continuous derivatives onI, and P₀(t) 0 onI. We discuss integrability of functions which are adjoint to certain fundamental solutions ofLy=y, and a related consequence.     

Convergence of a Halpern-type iteration algorithm for a class of pseudo-contractive mappings

Let E be a real reflexive Banach space with uniformly Gâteaux differentiable norm. Let K be a nonempty bounded closed and convex subset of E. Let T:K→K be a strictly pseudo-contractive map and let L>0 denote its Lipschitz constant. Assume F(T){xK:Tx=x}≠0/ and let zF(T). Fix δ(0,1) and let δ^* be such that δ^*δL(0,1). Define , where δ_n(0,1) and limδ_n=0. Let {α_n} be a real sequence in (0,1) which satisfies the following conditions: . For arbitrary x₀,uK, define a sequence {x_n}K by x_n+1=α_nu+(1−α_n)S_nx_n. Then, {x_n} converges strongly to a fixed point of T.     

Codes of Steiner triple and quadruple systems

The code over a finite fieldF _q of orderq of a design is the subspace spanned by the incidence vectors of the blocks. It is shown here that if the design is a Steiner triple system on points, and if the integerd is such that 2 ^d –1<2 ^d+1–1, then the binary code of the design contains a subcode that can be shortened to the binary Hamming codeH _d of length 2 ^d –1. Similarly the binary code of any Steiner quadruple system on +1 points contains a subcode that can be shortened to the Reed-Muller code (d–2,d) of orderd–2 and length 2 ^d , whered is as above.     

Complete stability of large order statistics

Fix an integerr1. For eachnr, letM _nr be the rth largest ofX ₁,...,X _n, where {X _n,n1} is a sequence of i.i.d. random variables. Necessary and sufficient conditions are given for the convergence of _n=r n P[|M _nr /a _n –1|<] for every >0, where {a _n} is a real sequence and –1. Moreover, it is shown that if this series converges for somer1 and some >–1, then it converges for everyr1 and every >–1.     

The self-adjointness conditions for a higher order differential operator with an operator coefficient

Certain sufficient conditions are found for self-adjointness of the differential operator generated by the expressionl (y)=(–1) ⁿ y ²ⁿ +Q (x)y, – <x <, where Q(x) is for each fixed value of x a bounded self-adjoint operator acting from the Hilbert space H into H, and y(x) is a vector function of H₁ for which .Translated from Matematicheskie Zametki, Vol. 5, No. 6, pp. 697–707, June, 1969.     

Finite extinction time for some perturbed Hamilton-Jacobi equations

In this paper we study initial value problems likeu _t–R¦u¦^m+u^q=0 in ⁿ× ₊, u(·,0⁺)=u_o(·) in ^N, whereR > 0, 0 <q < 1,m 1, andu _o is a positive uniformly continuous function verifying –R¦u _o¦^m+u ₀ ^q 0 in ^N . We show the existence of the minimum nonnegative continuous viscosity solutionu, as well as the existence of the function t(·) defined byu(x, t) > 0 if 0<t<t (x) andu(x, t)=0 ift t (x). Regularity, extinction rate, and asymptotic behavior of t(x) are also studied. Moreover, form=1 we obtain the representation formulau(x, t)=max{([(u _o(x – t))^1–q –(1–q)t]₊)^1/(1–q): ¦¦R}, (x, t) ₊ ^N+1 .Partially supported by the DGICYT No. 86/0405 project.     

Group Pairs with Property (T), from Arithmetic Lattices

Let Γ be an arithmetic lattice in an absolutely simple Lie group G with trivial centre. We prove that there exists an integer N ≥ 2, a subgroup Λ of finite index in Γ, and an action of Λ on such that the pair ( ) has property (T). If G has property (T), then so does . If G is the adjoint group of Sp(n, 1), then is a property (T) group satisfying the Baum–Connes conjecture. If Γ is an arithmetic lattice in SO(n, 1), then the associated von Neumann algebra is a II₁-factor in Popa’s class . Elaborating on this result of Popa, we construct a countable family of pairwise nonstably isomorphic group II₁-factors in the class , all with trivial fundamental groups and with all L²-Betti numbers being zero.Mathematics Subject Classiffications (2000). 22E40, 22E47, 46L80, 37A20