An additive divisor problem with a growing number of factors

Let τk(n) be the number of representations ofn as the product ofk positive factors, τ(n)=τ(n). The asymptotics of Σ _n≤x τ _k (n)τ(n+1) for 80k ¹⁰ (lnlnx)³≤lnx is shown to be uniform with respect tok. Translated fromMatematicheskie Zametki, Vol. 61, No. 3, pp. 391–406, March, 1997. Translated by N. K. Kulman     

Embedding ofl ∞ k in finite dimensional Banach spaces

Letx ₁,x ₂, ...,x _n ben unit vectors in a normed spaceX and defineM _n =Ave{‖Σ _i=1 ⁿ ε₁ x _i ‖:ε₁=±1}. We prove that there exists a setA⊂{1, ...,n} of cardinality such that {x _i } _i∈A is 16M _n -isomorphic to the natural basis ofl _∞ ^k . This result implies a significant improvement of the known results concerning embedding ofl _∞ ^k in finite dimensional Banach spaces. We also prove that for every ∈>0 there exists a constantC(∈) such that every normed spaceX _n of dimensionn either contains a (1+∈)-isomorphic copy ofl ₂ ^m for somem satisfying ln lnm≧1/2 ln lnn or contains a (1+∈)-isomorphic copy ofl _∞ ^k for somek satisfying ln lnk>1/2 ln lnn−C(∈). These results follow from some combinatorial properties of vectors with ±1 entries. The contribution of the first author to this paper forms part of his Ph.D. Thesis written under the supervision of Prof. M. A. Perles from the Hebrew University.     

Small fractional parts of additive forms

Letf(x)=θ₁ x ₁ ^k +...+θ _s x _s ^k be an additive form with real coefficients, and ∥α∥ = min {|α-u|:uεℤ} denote the distance fromα to the nearest integer. We show that ifθ ₁,…,θ _s , are algebraic ands = 4k then there are integersx ₁,…,x _s , satisfying l ≤x ₁,≤ N and ∥f(x)∥ ≤ N ^E , withE = − 1 + 2/e. Whens = λk, 1 ≤λ ≤ 2k, the exponentE may be replaced byλE/4, and if we drop the condition thatθ ₁,…,θ _s , be algebraic then the result holds for almost all values of θεℝ ^s . Whenk ≥ 6 is small a better exponent is obtained using Heath-Brown’s version of Weyl’s estimate.     

Trigonometric Approximation of SO(N) Loops

This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a Hölder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order $\mathcal{O}(n^{-\alpha+\epsilon})This paper extends previous work on approximation of loops to the case of special orthogonal groups SO(N), N≥3. We prove that the best approximation of an SO(N) loop Q(t) belonging to a H?lder class Lip _α , α>1, by a polynomial SO(N) loop of degree ≤n is of order O(n^-a+e)\mathcal{O}(n^{-\alpha+\epsilon}) for n≥k, where k=k(Q) is determined by topological properties of the loop and ε>0 is arbitrarily small. The convergence rate is therefore ε-close to the optimal achievable rate of approximation. The construction of polynomial loops involves higher-order splitting methods for the matrix exponential. A novelty in this work is the factorization technique for SO(N) loops which incorporates the loops’ topological aspects.     

Covering arrays of strength 3 and 4 from holey difference matrices

A covering array CA(N; t, k, v) is an N × k array with entries from a set X of v symbols such that every N × t sub-array contains all t-tuples over X at least once, where t is the strength of the array. The minimum size N for which a CA(N; t, k, v) exists is called the covering array number and denoted by CAN(t, k, v). Covering arrays are used in experiments to screen for interactions among t-subsets of k components. One of the main problems on covering arrays is to construct a CA(N; t, k, v) for given parameters (t, k, v) so that N is as small as possible. In this paper, we present some constructions of covering arrays of strengths 3 and 4 via holey difference matrices with prescribed properties. As a consequence, some of known bounds on covering array number are improved. In particular, it is proved that (1) CAN(3, 5, 2v) ≤ 2v ²(4v + 1) for any odd positive integer v with gcd(v, 9) ≠ 3; (2) CAN(3, 6, 6p) ≤ 216p ³ + 42p ² for any prime p > 5; and (3) CAN(4, 6, 2p) ≤ 16p ⁴ + 5p ³ for any prime p ≡ 1 (mod 4) greater than 5.     

On the Hausdorff dimensions of certain attractors

For any a,b∈R let ϕ_a,b(x)=ax+b(x∈R). Suppose 0<a<1. Let C_a,b be the generalized a-Cantor set with generating iterated function systme {ϕ_a,0, ϕ_a,b; ϕ_a,l}. Then we prove the Hausdorff dimension of C_a,c² C_{a,c^2 } is \fracln(3 - ?5 - ln2lna\frac{{ln(3 - \sqrt 5 - ln2}}{{lna}} when 0<a≤2 cos 80°.     

On the general additive divisor problem

We obtain a new upper bound for the sum Σ _h≤H Δ _k (N, h) when 1 ≤ H ≤ N, k ∈ ℕ, k ≥ 3, where Δ _k (N, h) is the (expected) error term in the asymptotic formula for Σ _N<n≤2N d _k (n)d _k (n + h), and d _k (n) is the divisor function generated by ζ(s) ^k . When k = 3, the result improves, for H ≥ N ^1/2, the bound given in a recent work of Baier, Browning, Marasingha and Zhao, who dealt with the case k = 3.     

Digital Expansions with Respect to Different Bases

We consider the g-ary expansion N=∑ _k b _k (N, g)g ^k of non-negative integers N and prove various results on the distribution and the mean value of the k-th digit b _k (N, g) if g varies in an interval of the form 2≤g≤N ^η. As an application we also consider the average value of the sum-of-digits function s(N, g)=∑ _k b _k (N, g).     

Acyclick-strong coloring of maps on surfaces

A coloring of graph vertices is called acyclic if the ends of each edge are colored in distinct colors and there are no two-colored cycles. Suppose each face of rank not greater thank, k ≥ 4, on a surfaceS ^N is replaced by the clique on the same set of vertices. Then the pseudograph obtained in this way can be colored acyclically in a set of colors whose cardinality depends linearly onN and onk. Results of this kind were known before only for 1 ≤N ≤ 2 and 3 ≤k ≤ 4. Translated fromMatematicheskie Zametki, vol. 67, No. 1, pp. 36–45, January, 2000.     

Computing commutator length in free groups

We study commutator length in free groups. (By a commutator lengthcl(g) of an element g in a derived subgroup G′ of a group G we mean the least natural number k such that g is a product of k commutators.) A purely algebraic algorithm is constructed for computing commutator length in a free group F₂ (Thm. 1). Moreover, for every element z ε F′₂ and for any natural m, the following estimate derives:cl(z^m) ≥ (ms(z) + 6)/12, where s(z) is a nonnegative number defined by an element z (Thm. 2). This estimate is used to compute commutator length of some particular elements. By analogy with the concept of width of a derived subgroup known in group theory, we define the concept of width of a derived subalgebra. The width of a derived subalgebra is computed for an algebra P of pairs, and also for its corresponding Lie algebra P_L. The algebra of pairs arises naturally in proving Theorem 2 and enjoys a number of interesting properties. We state that in a free group F_2k with free generators a₁, b₁, ..., a_k, b_k, k εN, every natural m satisfiescl(([a₁, b₁] ... [a_k, b_k])^m)=[(2 − m)/2] + mk. For k=1, this entails a known result of Culler. The notion of a growth function as applied to a finitely generated group G is well known. Associated with a derived subgroup of F₂ is some series depending on two variables which bears information not only on the number of elements of prescribed length but also on the number of elements of prescribed commutator length. A number of open questions are formulated. Supported by RFFR grant No. 98-01-00699. Translated fromAlgebra i Logika, Vol. 39, No. 4, pp. 395–440, July–August, 2000.     

Digital Expansions with Respect to Different Bases

We consider the g-ary expansion N=∑ _k b _k (N, g)g ^k of non-negative integers N and prove various results on the distribution and the mean value of the k-th digit b _k (N, g) if g varies in an interval of the form 2≤g≤N ^η. As an application we also consider the average value of the sum-of-digits function s(N, g)=∑ _k b _k (N, g). Received 5 November 2001 RID="a" ID="a" Dedicated to Professor Edmund Hlawka on the occasion of his 85th birthday     

Precise asymptotics of error variance estimator in partially linear models

In this paper, we focus our attention on the precise asymptotics of error variance estimator in partially linear regression models, y _i = x _i ^τ β + g(t _i ) + ε _i , 1 ≤ i ≤ n, {ε _i , i = 1, ⋯ n} are i.i.d random errors with mean 0 and positive finite variance σ ². Following the ideas of Allan Gut and Aurel Spătaru^[7,8] and Zhang^[21], on precise asymptotics in the Baum-Katz and Davis laws of large numbers and precise rate in laws of the iterated logarithm, respectively, and subject to some regular conditions, we obtain the corresponding results in partially linear regression models.      

A sparse graph almost as good as the complete graph on points inK dimensions

A setV ofn points ink-dimensional space induces a complete weighted undirected graph as follows. The points are the vertices of this graph and the weight of an edge between any two points is the distance between the points under someL _p metric. Let ε≤1 be an error parameter and letk be fixed. We show how to extract inO(n logn+ε ^−k log(1/ε)n) time a sparse subgraphG=(V, E) of the complete graph onV such that: (a) for any two pointsx, y inV, the length of the shortest path inG betweenx andy is at most (1+∈) times the distance betweenx andy, and (b)|E|=O(ε^−k n).     

Ideal einstein,conformally flat and semi-symmetric immersions

Recently, B. Y. Chen introduced a new intrinsic invariant of a manifold, and proved that everyn-dimensional submanifold of real space formsR ^m (ε) of constant sectional curvature ε satisfies a basic inequality δ(n ₁,…,n _k )≤c(n ₁,…,n _k )H ²+b(n ₁,…,n _k )ε, whereH is the mean curvature of the immersion, andc(n ₁,…,n _k ) andb(n ₁,…,n _k ) are constants depending only onn ₁,…,n _k ,n andk. The immersion is calledideal if it satisfies the equality case of the above inequality identically for somek-tuple (n ₁,…,n _k ). In this paper, we first prove that every ideal Einstein immersion satisfyingn≥n ₁+…+n _k +1 is totally geodesic, and that every ideal conformally flat immersion satisfyingn≥n ₁+…+n _k +2 andk≥2 is also totally geodesic. Secondly we completely classify all ideal semi-symmetric hypersurfaces in real space forms. The author was supported by the NSFC and RFDP.     

Asymptotic behavior of eigenvalues and eigenfunctions of the Fourier problem in a thick multilevel junction

A spectral boundary-value problem is considered in a plane thick two-level junction Ω_ε formed as the union of a domain Ω₀ and a large number 2N of thin rods with thickness of order ε = O(N ⁻¹). The thin rods are split into two levels depending on their length. In addition, the thin rods from the indicated levels are ε-periodically alternating. The Fourier conditions are given on the lateral boundaries of the thin rods. The asymptotic behavior of the eigenvalues and eigenfunctions is investigated as ε → 0, i.e., when the number of thin rods infinitely increases and their thickness approaches zero. The Hausdorff convergence of the spectrum is proved as ε → 0, the leading terms of asymptotics are constructed, and the corresponding asymptotic estimates are justified for the eigenvalues and eigenfunctions. Published in Ukrains’kyi Matematychnyi Zhurnal, Vol. 58, No. 2, pp. 195–216, February, 2006.     

The <Emphasis Type="Italic">k</Emphasis>-point exponent set of primitive digraphs with girth 2

Let D = （V, E） be a primitive digraph. The vertex exponent of D at a vertex v∈ V, denoted by expD（v）, is the least integer p such that there is a v →u walk of length p for each u ∈ V. Following Brualdi and Liu, we order the vertices of D so that exPD（V1） ≤ exPD（V2） …≤ exPD（Vn）. Then exPD（Vk） is called the k- point exponent of D and is denoted by exPD （k）, 1≤ k ≤ n. In this paper we define e（n, k） ：= max{expD （k） ｜ D ∈ PD（n, 2）} and E（n, k） ：= {exPD（k）｜ D ∈ PD（n, 2）}, where PD（n, 2） is the set of all primitive digraphs of order n with girth 2. We completely determine e（n, k） and E（n, k） for all n, k with n ≥ 3 and 1 ≤ k ≤ n.     

Approximation and asymptotics of eigenvalues of unbounded self-adjoint Jacobi matrices acting in <Emphasis Type="Italic">l</Emphasis><Superscript>2</Superscript> by the use of finite submatrices

We consider the problem of approximation of eigenvalues of a self-adjoint operator J defined by a Jacobi matrix in the Hilbert space l ²(ℕ) by eigenvalues of principal finite submatrices of an infinite Jacobi matrix that defines this operator. We assume the operator J is bounded from below with compact resolvent. In our research we estimate the asymptotics (with n → ∞) of the joint error of approximation for the eigenvalues, numbered from 1 to N; of J by the eigenvalues of the finite submatrix J _n of order n × n; where N = max{k ∈ ℕ: k ≤ rn} and r ∈ (0; 1) is arbitrary chosen. We apply this result to obtain an asymptotics for the eigenvalues of J. The method applied in this research is based on Volkmer’s results included in [23].     

Robust Shape Fitting via Peeling and Grating Coresets

Let P be a set of n points in ℝ ^d . A subset of P is called a (k,ε)-kernel if for every direction, the directional width of ε-approximates that of P, when k “outliers” can be ignored in that direction. We show that a (k,ε)-kernel of P of size O(k/ε ^(d−1)/2) can be computed in time O(n+k ²/ε ^d−1). The new algorithm works by repeatedly “peeling” away (0,ε)-kernels from the point set. We also present a simple ε-approximation algorithm for fitting various shapes through a set of points with at most k outliers. The algorithm is incremental and works by repeatedly “grating” critical points into a working set, till the working set provides the required approximation. We prove that the size of the working set is independent of n, and thus results in a simple and practical, near-linear ε-approximation algorithm for shape fitting with outliers in low dimensions. We demonstrate the practicality of our algorithms by showing their empirical performance on various inputs and problems. A preliminary version of this paper appeared in Proceedings of the 17th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 182–191. P.A. and H.Y. are supported by NSF under grants CCR-00-86013, EIA-01-31905, CCR-02-04118, and DEB-04-25465, by ARO grants W911NF-04-1-0278 and DAAD19-03-1-0352, and by a grant from the U.S.–Israel Binational Science Foundation. S.H.-P. is supported by a NSF CAREER award CCR-0132901.     

Scattering theory for perturbed stratified media

We study the operatorH = -c ² x,y)Μx,y)∇ · Μ ^-1 (x,y)∇, wherec andΜ are perturbations of functionsc ₀(y) andΜ ₀(y) which depend only on the one-dimensional variabley. In particular, we study the spatial asymptotics of lim_ε↺0(H - (λ +iε)²)^-1 applied to functions which have compact support or are otherwise well-behaved at infinity and relate the scattering matrix to the asymptotics of the generalized eigenfunctions. We then prove a trace formula for the operatorH in terms of the scattering phase, and, in a very special situation, use the trace formula to find spectral asymptotics forH. Partially supported by an NSF Postdoctoral Fellowship and the University of Missouri Research Board.