Sign changes in rational L w 1 -approximation

Let f ∈ L _w ¹ [−1, 1], let r _n,m(f) be the best rational L _w ¹ -approximation for f with respect to real rational functions of degree at most n in the numerator and of degree at most m in the denominator, let m = m(n), and let lim _{n → ∞} (n-m(n)) = ∞. In this case, we show that the counting measures of certain subsets of sign changes of f-r _n,m (f) converge weakly to the equilibrium measure on [−1, 1] as n → ∞. Moreover, we prove estimates for discrepancy between these counting measures and the equilibrium measure. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 2, pp. 283–287, February, 2006.     

Approximation in Learning Theory

This paper addresses some problems of supervised learning in the setting formulated by Cucker and Smale. Supervised learning, or learning-from-examples, refers to a process that builds on the base of available data of inputs x_i and outputs y_i, i = 1,...,m, a function that best represents the relation between the inputs x ∈ X and the corresponding outputs y ∈ Y. The goal is to find an estimator f_z on the base of given data z := ((x₁,y₁),...,(x_m,y_m)) that approximates well the regression function f_ρ (or its projection) of an unknown Borel probability measure ρ defined on Z = X × Y. We assume that (x_i,y_i), i = 1,...,m, are independent and distributed according to ρ. We discuss the following two problems: I. the projection learning problem (improper function learning problem); II. universal (adaptive) estimators in the proper function learning problem. In the first problem we do not impose any restrictions on a Borel measure ρ except our standard assumption that |y|≤ M a.e. with respect to ρ. In this case we use the data z to estimate (approximate) the L₂(ρ_X) projection (f_ρ)_W of f_ρ onto a function class W of our choice. Here, ρ_X is the marginal probability measure. In [KT1,2] this problem has been studied for W satisfying the decay condition ε_n(W,B) ≤ Dn^-r of the entropy numbers ε_n(W,B) of W in a Banach space B in the case B = C(X) or B = L₂(\rho_X). In this paper we obtain the upper estimates in the case ε_n(W,L₁(ρ_X)) ≤ Dn^-r with an extra assumption that W is convex. In the second problem we assume that an unknown measure ρ satisfies some conditions. Following the standard way from nonparametric statistics we formulate these conditions of the form f_ρ ∈ Θ. Next, we assume that the only a priori information available is that f_ρ belongs to a class Θ (unknown) from a known collection {Θ} of classes. We want to build an estimator that provides approximation of f_ρ close to the optimal for the class Θ. Along with standard penalized least squares estimators we consider a new method of construction of universal estimators. This method is based on a combination of two powerful ideas in building universal estimators. The first one is the use of penalized least squares estimators. This idea works well in the case of general setting with rather abstract methods of approximation. The second one is the idea of thresholding that works very well when we use wavelets expansions as an approximation tool. A new estimator that we call the big jump estimator uses the least squares estimators and chooses a right model by a thresholding criteria instead of the penalization. In this paper we illustrate how ideas and methods of approximation theory can be used in learning theory both in formulating a problem and in solving it.     

On the description of overgroups of E(m,R)?E(n,R)

The subgroups E(m,R) ⊗ E(n,R) ≤ H ≤ G = GL(mn,R) are studied under the assumption that the ring R is commutative and m, n ≥ 3. The group GL _m ⊗GL _n is defined by equations, the normalizer of the group E(m,R) ⊗ E(n,R) is calculated, and with each intermediate subgroup H it is associated a uniquely determined lower level (A,B,C), where A,B,C are ideals in R such that mA,A ² ≤ B ≤ A and nA,A ² ≤ C ≤ A. The lower level specifies the largest elementary subgroup satisfying the condition E(m, n,R, A,B,C) ≤ H. The standard answer to this problem asserts that H is contained in the normalizer N _G (E(m,n,R, A,B,C)). Bibliography: 46 titles.     

On best rational approximation of analytic functions

This paper contains some theorems related to the best approximation ρ_n(f;E) to a function f in the uniform metric on a compact set by rational functions of degree at most n. We obtain results characterizing the relationship between ρ_n(f;K) and ρ_n(f;E) in the case when complements of compact sets K and E are connected, K is a subset of the interior Ω of E, and f is analytic in Ω and continuous on E.     

Affinely equivalent complete flat manifolds

Let E _Aff(Γ,G, m) be the set of affine equivalence classes of m-dimensional complete flat manifolds with a fixed fundamental group Γ and a fixed holonomy group G. Let n be the dimension of a closed flat manifold whose fundamental group is isomorphic to Γ. We describe E _Aff(Γ,G, m) in terms of equivalence classes of pairs (ε, ρ), consisting of epimorphisms of Γ onto G and representations of G in ℝ ^m-n . As an application we give some estimates of card E _Aff(Γ,G, m).     

On the Riesz means of coefficients of <Emphasis Type="Italic">m</Emphasis>th symmetric power <Emphasis Type="Italic">L</Emphasis>-functions

Let c _n be the Fourier coefficients of L(sym ^m   f, s), and Δρ(x; sym ^m   f) be the error term in the asymptotic formula for ∑ _n≪x c _n . In this paper, we study the Riesz means of Δρ(x; sym ^m   f) and obtain a truncated Voronoi-type formula under the hypothesis Nice(m, f).     

On the order of growth of solutions of algebraic differential equations

Assume thatf is an integer transcendental solution of the differential equationP _n (z, f, f′)=P _n−1(z, f, f′, ... f ^(p)), whereP _n andP _n−1 are polynomials in all variables, the degree ofP _n with respect tof andf′ is equal ton, and the degree ofP _n−1 with respect tof, f′, ... f ^(p) is at mostn−1. We prove that the order ρ of growth off satisfies the relation 1/2≤ρ<∞. We also prove that if ρ=1/2, then, for a certain real ν, in the domain {z: ν<argz<ν+2π}/E _*, whereE _* is a certain set of disks with finite sum of radii, the estimate lnf(z)=z ^1/2 (β+o(1)), β∈C, holds forz=re ^iϕ,r≥r(ϕ)≥0. Furthermore, on the ray {z: argz=ν}, the following relation is true: ln‖f(re ^iν)‖=o(r ^1/2),r→+∞,r>0, , where Δ is a certain set on the semiaxisr>0 with mes Δ<∞. “L'vivs'ka Politekhnika” University, Lvov. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 51, No. 1, pp. 69–77, January, 1999.     

On embedding trees into uniformly convex Banach spaces

We investigate the minimum value ofD =D(n) such that anyn-point tree metric space (T, ρ) can beD-embedded into a given Banach space (X, ∥·∥); that is, there exists a mappingf :T →X with 1/D ρ(x,y) ≤ ∥f(x) −f(y)∥ ≤ρ(x,y) for anyx,y εT. Bourgain showed thatD(n) grows to infinity for any superreflexiveX (and this characterized super-reflexivity), and forX =ℓ _p, 1 <p < ∞, he proved a quantitative lower bound of const·(log logn)^min(1/2,1/p). We give another, completely elementary proof of this lower bound, and we prove that it is tight (up to the value of the constant). In particular, we show that anyn-point tree metric space can beD-embedded into a Euclidean space, with no restriction on the dimension, withD =O(√log logn). This paper contains results from my thesis [Mat89] from 1989. Since the subject of bi-Lipschitz embeddings is becoming increasingly popular, in 1997 I finally decided to publish this English version. Supported by Czech Republic Grant GAČR 0194 and by Charles University grants No. 193, 194.     

Uniformity over primes of tamely ramified splittings

We fix a prime p and let f(X) vary over all monic integer polynomials of fixed degree n. Given any possible shape of a tamely ramified splitting of p in an extension of degree n, we prove that there exists a rational function φ(X)∈ℚ(X) such that the density of the monic integer polynomials f(X) for which the splitting of p has the given shape in ℚ[X]/f(X) is φ(p) (here reducible polynomials can be neglected). As a corollary, we prove that, for p≥n, the density of irreducible monic polynomials of degree n in ℤ _p [X] is the value at p of a rational function φ _n (X)∈ℚ(X). All rational functions involved are effectively computable. Received: 15 September 1998 / Revised version: 21 October 1999     

A counterexample in copositive approximation

The present paper gives a converse result by showing that there exists a functionf ∈C _[−1,1], which satisfies that sgn(x)f(x) ≥ 0 forx ∈ [−1, 1], such that {fx75-1} whereE _n ⁽⁰⁾ (f, 1) is the best approximation of degreen tof by polynomials which are copositive with it, that is, polynomialsP withP(x(f(x) ≥ 0 for allx ∈ [−1, 1],E _n(f) is the ordinary best polynomial approximation off of degreen.     

On the generalized critical values of a polynomial mapping

 Let be a polynomial dominant mapping and let deg f _i ≤d. We prove that the set K(f) of generalized critical values of f is contained in the algebraic hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ , where . This implies in particular that the set B(f) of bifurcations points of f is contained in the hypersurface of degree at most D=(d+s(m−1)(d−1)) ⁿ . We give also an algorithm to compute the set K(f) effectively. Received: 11 June 2001 / Revised version: 1 July 2002 Published online: 24 January 2003 The author is partially supported by the KBN grant 2 PO3A 017 22. Mathematics Subject Classification (2000): 14D06, 14Q20, 51N10, 51N20, 15A04     

The number of K m,m -free graphs

A graph is called H-free if it contains no copy of H. Denote by f _n (H) the number of (labeled) H-free graphs on n vertices. Erdős conjectured that f _n (H) ≤ 2^{(1+o(1))ex(n,H)}. This was first shown to be true for cliques; then, Erdős, Frankl, and R?dl proved it for all graphs H with χ(H)≥3. For most bipartite H, the question is still wide open, and even the correct order of magnitude of log₂ f _n (H) is not known. We prove that f _n (K _m,m ) ≤ 2 ^O (n ^2−1/m ) for every m, extending the result of Kleitman and Winston and answering a question of Erdős. This bound is asymptotically sharp for m∈{2,3}, and possibly for all other values of m, for which the order of ex(n,K _m,m ) is conjectured to be Θ(n ^2−1/m ). Our method also yields a bound on the number of K _m,m -free graphs with fixed order and size, extending the result of Füredi. Using this bound, we prove a relaxed version of a conjecture due to Haxell, Kohayakawa, and Łuczak and show that almost all K _3,3-free graphs of order n have more than 1/20·ex(n,K _3,3) edges.     

Exact laws for sums of ratios of order statistics from the Pareto distribution

Consider independent and identically distributed random variables {X _nk, 1 ≤ k ≤ m, n ≤ 1} from the Pareto distribution. We select two order statistics from each row, X _n(i) ≤ X _n(j), for 1 ≤ i < j ≤ = m. Then we test to see whether or not Laws of Large Numbers with nonzero limits exist for weighted sums of the random variables R _ij = X _n(j)/X _n(i).     

High-Dimensional Centrally Symmetric Polytopes with Neighborliness Proportional to Dimension

Let A be a d by n matrix, d < n. Let C be the regular cross polytope (octahedron) in Rⁿ. It has recently been shown that properties of the centrosymmetric polytope P = AC are of interest for finding sparse solutions to the underdetermined system of equations y = Ax [9]. In particular, it is valuable to know that P is centrally k-neighborly. We study the face numbers of randomly projected cross polytopes in the proportional-dimensional case where d ∼ δn, where the projector A is chosen uniformly at random from the Grassmann manifold of d-dimensional orthoprojectors of Rⁿ. We derive ρ_N(δ) > 0 with the property that, for any ρ < ρ_N(δ), with overwhelming probability for large d, the number of k-dimensional faces of P = AC is the same as for C, for 0 ≤ k ≤ ρd. This implies that P is centrally ⌊ ρ d ⌋-neighborly, and its skeleton Skel_{⌊ ρ d ⌋}(P) is combinatorially equivalent to Skel_{⌊ ρ d⌋}(C). We display graphs of ρ_N. Two weaker notions of neighborliness are also important for understanding sparse solutions of linear equations: weak neighborliness and sectional neighborliness [9]; we study both. Weak (k,ε)-neighborliness asks if the k-faces are all simplicial and if the number of k-dimensional faces f_k(P) ≥ f_k(C)(1 – ε). We characterize and compute the critical proportion ρ_W(δ) > 0 such that weak (k,ε) neighborliness holds at k significantly smaller than ρ_W · d and fails for k significantly larger than ρ_W · d. Sectional (k,ε)-neighborliness asks whether all, except for a small fraction ε, of the k-dimensional intrinsic sections of P are k-dimensional cross polytopes. (Intrinsic sections intersect P with k-dimensional subspaces spanned by vertices of P.) We characterize and compute a proportion ρ_S(δ) > 0 guaranteeing this property for k/d ∼ ρ < ρ_S(δ). We display graphs of ρ_S and ρ_W.     

Test elements for endomorphisms of free groups and algebras

LetE be a bounded Borel subset of ℝⁿ,n≥2, of positive Lebesgue measure andP _E the corresponding ‘Pompeiu transform”. We prove thatP _E is injective onL ^p(ℝⁿ) if 1≤p≤2n/(n-1). We explore the connection between this problem and a Wiener-Tauberian type theorem for theM(n) action onL ^q(ℝⁿ) for various values ofq. We also take up the question of whenP _E is injective in caseE is of finite, positive measure, but is not necessarily a bounded set. Finally, we briefly look at these questions in the contexts of symmetric spaces of compact and non-compact type.     

On samples of independent random vectors in spaces of infinitely increasing dimension

We study the asymptotic behavior of a set of random vectors ξ_i, i = 1,..., m, whose coordinates are independent and identically distributed in a space of infinitely increasing dimension. We investigate the asymptotics of the distribution of the random vectors, the consistency of the sets M _m⁽ⁿ⁾ = ξ₁,..., ξ_m and X _n^λ = x ∈ X _n: ρ(x) ≤ λn, and the mutual location of pairs of vectors. Translated from Ukrainskii Matematicheskii Zhurnal, Vol. 50, No. 12, pp. 1706–1711, December, 1998.     

Approximation of holomorphic functions by Taylor-Abel-Poisson means

We investigate the problem of approximation of functions ƒ holomorphic in the unit disk by means A _{ρ, r} (f) as ρ → 1−. In terms of the error of approximation by these means, a constructive characteristic of classes of holomorphic functions H _p ^r Lipα is given. The problem of the saturation of A _{ρ, r} (f) in the Hardy space H _p is solved. __________ Translated from Ukrains’kyi Matematychnyi Zhurnal, Vol. 59, No. 9, pp. 1253–1260, September, 2007.     

Low distortion euclidean embeddings of trees

We consider the problem of embedding a certain finite metric space to the Euclidean space, trying to keep the bi-Lipschitz constant as small as possible. We introduce the notationc ₂(X, d) for the least distortion with which the metric space (X, d) may be embedded in a Euclidean space. It is known that if (X, d) is a metric space withn points, thenc ₂(X, d)≤0(logn) and the bound is tight. LetT be a tree withn vertices, andd be the metric induced by it. We show thatc ₂(T, d)≤0(log logn), that is we provide an embeddingf of its vertices to the Euclidean space, such thatd(x, y)≤‖f(x)−f(y) ‖≤c log lognd(x, y) for some constantc. Supported in part by grants from the Israeli Academy of Sciences and the US-Israel Binational Science Foundation. Supported in part by NSF under grants CCR-9215293 and by DIMACS, which is supported by NSF grant STC-91-19999 and by the New Jersey Commission on Science and Technology.     

On the Erlang Loss Model with Time Dependent Input

We consider the M(t)/M(t)/m/m queue, where the arrival rate λ(t) and service rate μ(t) are arbitrary (smooth) functions of time. Letting p_n(t) be the probability that n servers are occupied at time t (0≤ n≤ m, t > 0), we study this distribution asymptotically, for m→∞ with a comparably large arrival rate λ(t) = O(m) (with μ(t) = O(1)). We use singular perturbation techniques to solve the forward equation for p_n(t) asymptotically. Particular attention is paid to computing the mean number of occupied servers and the blocking probability p_m(t). The analysis involves several different space-time ranges, as well as different initial conditions (we assume that at t = 0 exactly n₀ servers are occupied, 0≤ n₀≤ m). Numerical studies back up the asymptotic analysis. AMS subject classification: 60K25,34E10 Supported in part by NSF grants DMS-99-71656 and DMS-02-02815     

Relations between some constants associated with finite dimensional Banach spaces

We define the asymmetry constants(E) of a Banach spaceE, and show examples of finite-dimensional spaces with “large” asymmetry constants. IfE isn-dimensional,λ(E)17its projection constant and π ₁(I _E ) the absolutely summing norm of the identity operatorI _E , thenn≦λ(E)π₁(I _E )≤n(s(E))². Similar equations linking thep-absolutely summing and the nuclear norms ofI _E are established. We also obtain estimates on these norms, for example π₂(I _E )=√n. The contribution of this author is a part of a Ph.D. Thesis prepared at the Hebrew University of Jerusalem under the supervision of Professor J. Lindenstrauss whose guidance and valuable suggestions are gratefully acknowledged.