Additive problems for integers with a given number of prime divisors

The asymptotics of sums of the form Στ(|bn−a|) (summation overn<N, ω(n)=k) is studied, whereω(n) is the number of distinct prime divisors ofn, andτ(n) is the number of all divisors. Translated fromMatematicheskie Zametki, Vol. 63, No. 5, pp. 749–762, May, 1998. In conclusion, the author wishes to express his gratitude to Professor N. M. Timofeev for valuable advice. This research was supported by the Russian Foundation for Basic Research under grant No. 96-01-00502.     

The number of periodic solutions of polynomial differential equations

We estimate the number of periodic solutions for special classes ofnth-order ordinary differential equations with variable coefficients. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 720–727, November, 1998. The author thanks Yu. S. Il'yashenko for setting the problems, permanent advice, and overall support. The author is also thankful to D. A. Panov for numerous discussions. This research was supported by the CRDF Foundation under grant MR1-220, by the INTAS Foundation under grant No. 93-05-07, and by the Russian Foundation for Basic Research under grant No. 95-01-01258.     

Branched two-sheeted covers

In this paper we explore the connection between Weierstrass points of subspaces of the holomorphic differentials and the geometry of the canonical curve inPC ^g−1. In particular, we consider non-hyperelliptic Riemann surfaces with involution and the Weierstrass points of the −1 eigenspace of the holomorphic differentials. The case of coverings of a torus is considered in detail. Research of the first author supported in part by the Paul and Gabriella Rosenbaum Foundation, the Landau Center for Research in Mathematical Analysis (supported by Minerva Foundation-Germany) and a US-Israel BSF grant. Research by the second author supported in part by NSF Grant DMS 9003361 and a Lady Davis Visiting Professorship at the Hebrew University.     

The class of groups all of whose subgroups with lesser number of generators are free is generic

It is shown that, in a certain statistical sense, in almost every group withm generators andn relations (withm andn chosen), any subgroup generated by less thanm elements (which need not belong to the system of generators of the whole group) is free. In particular, this solves Problem 11.75 from the Kourov Notebook. In the proof we introduce a new assumption on the defining relations stated in terms of finite marked groups. Translated fromMatematicheskie Zametki, Vol. 59, No. 4, pp. 489–496, April, 1996. The research of the second author was partially supported by the Russian Foundation for Basic Research under grant No. 94-0101541 and by the International Science Foundation under grant No. MID000.     

Castles in the air revisited

We show that the total number of faces bounding any one cell in an arrangement ofn (d−1)-simplices in ℝ ^d isO(n ^d−1 logn), thus almost settling a conjecture of Pach and Sharir. We present several applications of this result, mainly to translational motion planning in polyhedral environments. We than extend our analysis to derive other results on complexity in arrangements of simplices. For example, we show that in such an arrangement the total number of vertices incident to the same cell on more than one “side” isO(n ^d−1 logn). We, also show that the number of repetitions of a “k-flap,” formed by intersectingd−k given simplices, along the boundary of the same cell, summed over all cells and allk-flaps, isO(n ^d−1 log² n). We use this quantity, which we call theexcess of the arrangement, to derive bounds on the complexity ofm distinct cells of such an arrangement. Work on this paper by the first author has been partially supported by National Science Foundation Grant CCR-92-11541. Work on this paper by the second author has been supported by Office of Naval Research Grant N00014-90-J-1284, by National Science Foundation Grants CCR-89-01484 and CCR-91-22103, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F.—the German-Israeli Foundation for Scientific Reseach and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences.     

Weight of faces in plane maps

Precise upper bounds are obtained for the minimum weight of minor faces in normal plane maps and 3-polytopes with specified maximum vertex degree. Translated fromMatematicheskie Zametki, Vol. 64, No. 5, pp. 648–657, November, 1998. The research of the first named author was supported in part by the Visiting Fellowship Research Grant GR/K00561 from the Engineering and Physical Sciences Research Council and by the Russian Foundation for Basic Research under grant No. 96-01-01614 and No. 97-01-01075.     

On polynomiality of the method of analytic centers for fractional problems

We establish polynomial time convergence of the method of analytic centers for the fractional programming problemt→min |x∈G, tB(x)−A(x)∈K, whereG ⊂ ℝ ⁿ is a closed and bounded convex domain,K ⊂ ℝ ^m is a closed convex cone andA(x):G → ℝ ⁿ ,B(x):G→K are regular enough (say, affine) mappings. This research was partly supported by grant #93-012-499 of the Fundamental Studies Foundation of Russian Academy of Sciences     

On the concentration of eigenvalues of random symmetric matrices

It is shown that for every 1≤s≤n, the probability that thes-th largest eigenvalue of a random symmetricn-by-n matrix with independent random entries of absolute value at most 1 deviates from its median by more thant is at most 4e ⁻ t ²32 ^s2. The main ingredient in the proof is Talagrand’s Inequality for concentration of measure in product spaces. Research supported in part by a USA — Israel BSF grant, by a grant from the Israel Science Foundation and by the Hermann Minkowski Minerva Center for Geometry at Tel Aviv University. Research supported in part by a USA — Israel BSF grant and by a Bergmann Memorial Grant.     

Vertical decomposition of arrangements of hyperplanes in four dimensions

We show that, for any collection ℋ ofn hyperplanes in ℜ⁴, the combinatorial complexity of thevertical decomposition of the arrangementA(ℋ) of ℋ isO(n ⁴ logn). The proof relies on properties of superimposed convex subdivisions of 3-space, and we also derive some other results concerning them. Work on this paper by Leonidas Guibas and Micha Sharir has been supported by a grant from the U.S.-Israeli Binational Science Foundation. Work by Leonidas Guibas was also supported by National Science Foundation Grant CCR-9215219. Work by Micha Sharir was also supported by National Science Foundation Grant CCR-91-22103, and by grants from the G.I.F.—the German Isreali Foundation for Scientific Research and Development, and the Fund for Basic Research administered by the Israeli Academy of Sciences. Work by Jiří Matouŝek was done while he was visiting Tel Aviv University, and its was partially supported by a Humboldt Research Fellowship. Work on this paper by Dan Halperin was carried out while he was at Tel Aviv University.     

Self-similar sets of zero Hausdorff measure and positive packing measure

We prove that there exist self-similar sets of zero Hausdorff measure, but positive and finite packing measure, in their dimension; for instance, for almost everyu ∈ [3, 6], the set of all sums ∑ ₀ ⁸ a _n 4⁻ⁿ a _n 4⁻ⁿ with digits witha _n ∈ {0, 1,u} has this property. Perhaps surprisingly, this behavior is typical in various families of self-similar sets, e.g., for projections of certain planar self-similar sets to lines. We establish the Hausdorff measure result using special properties of self-similar sets, but the result on packing measure is obtained from a general complement to Marstrand’s projection theorem, that relates the Hausdorff measure of an arbitrary Borel set to the packing measure of its projections. Research of Y. Peres was partially supported by NSF grant #DMS-9803597. Research of K. Simon was supported in part by the OTKA foundation grant F019099. Research of B. Solomyak was supported in part by NSF grant #DMS 9800786, the Fulbright Foundation, and the Institute of Mathematics at The Hebrew University of Jerusalem.     

Almost tight upper bounds for the single cell and zone problems in three dimensions

We consider the problem of bounding the combinatorial complexity of a single cell in an arrangement ofn low-degree algebraic surface patches in 3-space. We show that this complexity isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. This extends several previous results, almost settles a 9-year-old open problem, and has applications to motion planning of general robot systems with three degrees of freedom. As a corollary of the above result, we show that the overall complexity of all the three-dimensional cells of an arrangement ofn low-degree algebraic surface patches, intersected by an additional low-degree algebraic surface patch σ (the so-calledzone of σ in the arrangement) isO(n ^2+ε), for any ε>0, where the constant of proportionality depends on ε and on the maximum degree of the given surfaces and of their boundaries. Work on this paper by the first author has been supported by a Rothschild Postdoctoral Fellowship, by a grant from the Stanford Integrated Manufacturing Association (SIMA), by NSF/ARPA Grant IRI-9306544, and by NSF Grant CCR-9215219. Work on this paper by the second author has been supported by NSF Grants CCR-91-22103 and CCR-93-111327, and by grants from the U.S.-Israeli Binational Science Foundation, the G.I.F., the German-Israeli Foundation for Scientific Research and Development, and the Israel Science Fund administered by the Israeli Academy of Sciences.     

Functional equations for Hecke-Maaass series

The Dirichlet (Hecke-Maass) series associated with the eigenfuctionsf andg of the invariant differential operator Δ_k=−y²(∂²/∂x²)+iky∂/∂x of weightk are investigated. It is proved that any relation of the form (f/kM)=g for thek-action of the groupSL ₂ SL ₂(ℝ) is equivalent to a pair of functional equations relating the Hecke-Maass series forf andg and involving only traditional gamma factors. This work was supported by the Russian Foundation for Basic Research (grant No. 96-01-10439). Institute of Applied Mathematics, Far East Division of Russian Academy of Sciences. Translated from Funktional'nyi Analiz i Ego Prilozheniya, Vol. 34, No. 2, pp. 23–32, April–June, 2000. Translated by V. M. Volosov     

Solvability of nonlocal elliptic problems in weight spaces

In this paper we consider elliptic equations of order 2m in a bounded domainQ є R ⁿ with boundaryδQ and nonlocal conditions relating the traces of the solution and its derivatives on (n − 1)-dimensional smooth manifolds Γ _i (∪ _i =∂δQ) to their values on some compact setF ⊂Q, whereF ∩δQ ≠ Φ. The Fredholm solvability of these problems in the weight spacesV _{p, a} ^/l+2m (Q) is proved for arbitrary 1<p <∞. Translated fromMatematicheskie Zametki, Vol. 67, No. 6, pp. 882–898, June, 2000. This research was supported by the Russian Foundation for Basic Research under grant No. 99-01-00028.     

Morita equivalence of smooth noncommutative tori

We show that in the generic case the smooth noncommutative tori associated with two n × n real skew-symmetric matrices are Morita equivalent if and only if the matrices are in the same orbit of the natural SO(n, n∣Z) action. This research was supported by a grant from the Natural Sciences and Engineering Research Council of Canada, held by the first named author.     

On continuous extension of locally homeomorphic simplicial maps of ℝ2 into itself byσ-processes

It is shown that the Klein bottle with two points removed can be embedded in the compactification of ℝ² by a finite tree. Translated fromMatematicheskie Zametki, Vol. 59, No. 6, pp. 821–831, June, 1996. I wish to express sincere gratitude to A. G. Vitushkin for posing the problem and guidance. This research was supported by the Russian Foundation for Basic Research under grant No. 93-01-00225 and by the Ministry of Scientific and Technological Research in the Mathematical Sciences of Italy.     

Fast decreasing rational functions

Necessary and sufficient conditions are obtained for the existence of sequences of rational functions of the formr _n(x) =p _n(x)/p_n(−x), withp _n a polynomial of degreen, that decrease geometrically on (0, 1] in accordance with a specified rate function. The technique of proof involves minimum energy problems for Green potentials in the presence of an external field. Applications are given for the construction of rational approximations of |x| and sgn(x) on [−1, 1] having geometric rates of convergence forx ≠ 0. The research of this author was supported, in part, by National Science Foundation grant DMS-9501130.     

Uniformn-analytic polynomial approximations of functions on rectifiable contours in ℂ

We study approximations of functions byn-analytic polynomials in the uniform norm on closed rectifiable Jordan curves in the complex plane. It is shown that, in contrast to the case of uniform approximations by complex polynomials, there are no topological criteria for the existence of such approximations. We obtain a criterion for the existence ofn-analytic polynomial approximations in terms of analytic properties of these curves. Translated fromMatematicheskie Zametki, Vol. 59, No. 4, pp. 603–609, April, 1996. The author is extremely grateful to A. G. Vitushkin and P. V. Paramonov for the statement of the problem and their attention to the work. The work was partially supported by the Russian Foundation for Basic Research under grant No. 93-01-00225.     

Canonical Representations on Lobachevsky Spaces: An Interaction with an Overalgebra

We define canonical representations R _λ , , for the Lobachevsky space ℒ=G/K of dimension n−1 where G=SO₀(n−1,1), K=SO(n−1), as the restriction to G of maximal degenerate series representations of the overgroup . We determine explicitly the interaction of Lie operators of with operators intertwining canonical representations and representations of G associated with a cone. Supported by the Russian Foundation for Basic Research: grants No. 05-01-00074a and No. 05-01-00001a, the Netherlands Organization for Scientific Research (NWO): grant 047-017-015, the Scientific Program “Devel. Sci. Potent. High. School”: project RNP.2.1.1.351 and Templan No. 1.2.02.     

Strongly meager and strong measure zero sets

 In this paper we present two consistency results concerning the existence of large strong measure zero and strongly meager sets. RID="ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID="ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658 Received: 6 January 1999 / Revised version: 20 July 1999 / Published online: 25 February 2002 RID=" ID=" <E5>Mathematics Subject Classification (2000):</E5>&ensp;03E35 RID=" ID=" The first author was supported by Alexander von Humboldt Foundation and NSF grant DMS 95-05375. The second author was partially supported by Basic Research Fund, Israel Academy of Sciences, publication 658