Maintaining the minimal distance of a point set in polylogarithmic time

A dynamic data structure is given that maintains the minimal distance in a set ofn points ink-dimensional space inO((logn) ^k log logn) amortized time per update. The size of the data structure is bounded byO(n(logn) ^k ). Distances are measured in the MinkowskiL _t -metric, where 1 t . This is the first dynamic data structure that maintains the minimal distance in polylogarithmic time for fully on-line updates.This work was supported by the ESPRIT II Basic Research Actions Program, under Contract No. 3075 (project ALCOM).     

Integral Operators in Sobolev Spaces on Domains with Boundary

Properties of integral operators with weak singularities arc investigated. It is assumed that G ? ?ⁿ is a bounded domain. The boundary δG should be smooth concerning the Sobolev trace theorem. It will be proved that the integral operators $\int {_G \frac{{f\left(\Theta \right)}}{{x - y|^{n - 1} }}u\left(\nu \right)d\partial G_\nu }$ and $ \int {_{\partial G} \frac{{f\left(\Theta \right)}}{{|x - y|^{n - 1} }}u\left(y \right)d\partial G_y }$ maps W_p^k(G) into W_p^k+1(G) and W_p^k?1(G) into W_p^k/p(G), respectively, and are bounded. Here θ ∈ S ? ?ⁿ, where S is the unit sphere. Furthermore, f possesses bounded first order derivatives and is bounded on S. Then applications to first order systems are discussed.     

Hermite-Fejér插值的收敛准则

本文给出Hermite-Fejér插值的若干收敛准则.其中之一是:Hermite-Fejer插值算子对每一个连续函数一致收敛当且仅当该算子范数一致有界且该算子对两个单项式x及x²一致收敛.     

Cocycle d'Euler etK2

In this paper we construct a canonical 2-cocycle on the groupP SL(2,k) with values in the Witt groupW(k) of the fieldk. This allows us to produce anatural homomorphism :H ₂(SL(2,k); Z)I ²(k), whereI ²(k) is the square of the fundamental ideal. We prove that this homomorphism is in fact a lift of Milnor's symbol.

     

Random k-dimensional orders: Width and number of linear extensions

We consider the width W _k (n) and number L _k (n) of linear extensions of a random k-dimensional order P _k (n). We show that, for each fixed k, almost surely W _k (n) lies between (k/2–C)n _1–1/k and 4kn ^1-1/k , for some constant C, and L _k (n) lies between (e ^-2 n ^1-1/k ) ⁿ and (2kn ^1-1/k ) ⁿ . The bounds given also apply to the expectations of the corresponding random variables. We also show that W _k (n) and log L _k (n) are sharply concentrated about their means.     

An extreme value theory for long head runs

Summary For an infinite sequence of independent coin tosses withP(Heads)=p(0,1), the longest run of consecutive heads in the firstn tosses is a natural object of study. We show that the probabilistic behavior of the length of the longest pure head run is closely approximated by that of the greatest integer function of the maximum ofn(1-p) i.i.d. exponential random variables. These results are extended to the case of the longest head run interrupted byk tails. The mean length of this run is shown to be log(n)+klog(n)+(k+1)log(1–p)–log(k!)+k+/–1/2+ r₁(n)+ o(1) where log=log_1/p , =0.577 ... is the Euler-Mascheroni constant, =ln(1/p), andr ₁(n) is small. The variance is ₂/6²+1/12 +r ₂(n)+ o(1), wherer ₂(n) is again small. Upper and lower class results for these run lengths are also obtained and extensions discussed.This work was supported by a grant from the System Development Foundation     

Finite and p-adic Polylogarithms

The finite nth polylogarithm li _n (z) /p(z) is defined as _k=1 ^p–1 z ^k /k ⁿ . We state and prove the following theorem. Let Li _k : _{p p} be the p-adic polylogarithms defined by Coleman. Then a certain linear combination F _n of products of polylogarithms and logarithms, with coefficients which are independent of p, has the property that p ^1–n DF _n (z) reduces modulo p>n+1 to li _n–1((z)), where D is the Cathelineau operator z(1–z)d/dz and is the inverse of the p-power map. A slightly modified version of this theorem was conjectured by Kontsevich. This theorem is used by Elbaz-Vincent and Gangl to deduce functional equations of finite polylogarithms from those of complex polylogarithms.     

Projection-iteration methods for solving constrained minimization problems

The problem of minimization of the functionalf(x) on the set in a Hilbert space H is solved by methods that approximatef(x) by a sequence of functionalsf _n(x_n) defined on the sets _n= H _n (H _n H) and then minimize eachf _n(x_n) on _n by gradient projection methods. Several approximations x_n ⁽ⁱ⁾(i=1,2,...,k_n) are constructed for each functional, and the last approximation is accepted as the starting approximation for the next functional. Convergence theorems are proved and error bounds are obtained.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 64, pp. 3–8, 1988.     

k-Weakly almost convex groups and π 1 ∞ \tilde M^3

We extend Cannon's notion ofk-almost convex groups which requires that for two pointsx, y on then-sphere in the Cayley graph which can be joined by a pathl ₁ of length k, there is a second pathl ₂ in then-ball, joiningx andy, of bounded length N(k). Ourk-weakly almost convexity relaxes this condition by requiring only thatl ₁ l ₂ bounds a disk of area C ₁(k)n ^{1 - (k)} +C ₂(k). IfM ³ is a closed 3-manifold with 3-weakly almost convex fundamental group, then ₁ .     

Random Lazy Random Walks on Arbitrary Finite Groups

This paper considers lazy random walks supported on a random subset of k elements of a finite group G with order n. If k=a log₂ n where a>1 is constant, then most such walks take no more than a multiple of log₂ n steps to get close to uniformly distributed on G. If k=log₂ n+f(n) where f(n) and f(n)/log₂ n0 as n, then most such walks take no more than a multiple of (log₂ n) ln(log₂ n) steps to get close to uniformly distributed. To get these results, this paper extends techniques of Erdös and Rényi and of Pak.     

Many triangulated spheres

Lets(d, n) be the number of triangulations withn labeled vertices ofS ^d–1, the (d–1)-dimensional sphere. We extend a construction of Billera and Lee to obtain a large family of triangulated spheres. Our construction shows that logs(d, n)C ₁(d)n ^[(d–1)/2], while the known upper bound is logs(d, n)C ₂(d)n ^[d/2] logn.Letc(d, n) be the number of combinatorial types of simpliciald-polytopes withn labeled vertices. (Clearly,c(d, n)s(d, n).) Goodman and Pollack have recently proved the upper bound: logc(d, n)d(d+1)n logn. Combining this upper bound forc(d, n) with our lower bounds fors(d, n), we obtain, for everyd5, that lim _n(c(d, n)/s(d, n))=0. The cased=4 is left open. (Steinitz's fundamental theorem asserts thats(3,n)=c(3,n), for everyn.) We also prove that, for everyb4, lim _d(c(d, d+b)/s(d, d+b))=0. (Mani proved thats(d, d+3)=c(d, d+3), for everyd.)Lets(n) be the number of triangulated spheres withn labeled vertices. We prove that logs(n)=2^{0.69424n(1+o(1))}. The same asymptotic formula describes the number of triangulated manifolds withn labeled vertices.Research done, in part, while the author visited the mathematics research center at AT&T Bell Laboratories.     

An asymptotic approximation of Wallis’ sequence

An asymptotic approximation of Wallis’ sequence W(n) = Π _k=1 ⁿ 4k ²/(4k ² − 1) obtained on the base of Stirling’s factorial formula is presented. As a consequence, several accurate new estimates of Wallis’ ratios w(n) = Π _k=1 ⁿ (2k−1)/(2k) are given. Also, an asymptotic approximation of π in terms of Wallis’ sequence W(n) is obtained, together with several double inequalities such as, for example,

Weighted mean convergence of Hakopian interpolation on the disk

In this paper, we study weighted mean integral convergence of Hakopian interpolation on the unit disk D. We show that the inner product between Hakopian interpolation polynomial Hn(f;x,y) and a smooth function g(x,y) on D converges to that of f(x,y) and g(x,y) on D when n →∞, provided f(x,y) belongs to C(D) and all first partial derivatives of g(x,y) belong to the space LipαM(0 ＜α≤ 1). We further show that provided all second partial derivatives of g(x,y) also belong to the space LipαM and f(x,y) belongs to C1 (D), the inner product between the partial derivative of Hakopian interpolation polynomial (6)/(6)xHn(f;x,y) and g(x,y) on D converges to that between (6)/(6)xf(x,y) and g(x,y) on D when n →∞.     

On the Elementary Retarded,Ultrahyperbolic Solution of the Klein-Gordon Operator,Iterated k Times

Let t = (t₁,…,t_n) be a point of ?ⁿ. We shall write . We put, by the definition, W_α(u, m) = (m^?2u)^{(α ? n)/4}[π^{(n ? 2)/2}2^{(α + n ? 2)/2}Г(α/2)]J_{(α ? n)/2}(m²u)^1/2; here α is a complex parameter, m a real nonnegative number, and n the dimension of the space. W_α(u, m), which is an ordinary function if Re α ≥ n, is an entire distributional function of α. First we evaluate {□ + m²}W_{α + 2}(u, m) = W_α(u, m), where {□ + m²} is the ultrahyperbolic operator. Then we express W_α(u, m) as a linear combination of R_α(u) of differntial orders; R_α(u) is Marcel Riesz's ultrahyperbolic kernel. We also obtain the following results: W_?2k(u, m) = {□ + m²}^kδ, k = 0, 1,…; W₀(u, m) = δ; and {□ + m²}^kW_2k(u, m) = δ. Finally we prove that W_α(u, m = 0) = R_α(u). Several of these results, in the particular case µ = 1, were proved earlier by a completely different method.     

A new continuation method for complementarity problems with uniformP-functions

The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR ₊ ⁿ ofR ⁿ intoR ⁿ can be written as the system of equationsF(x, y) = 0 and(x, y) R ₊ ²ⁿ , whereF denotes the mapping from the nonnegative orthantR ₊ ²ⁿ ofR ²ⁿ intoR ₊ ⁿ × Rⁿ defined byF(x, y) = (x ₁y₁,,x_ny_n, f₁(x) – y₁,, f_n(x) – y_n) for every(x, y) R ₊ ²ⁿ . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR ₊ ²ⁿ ontoR ₊ ⁿ × Rⁿ. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x ⁰, y⁰) and(x, y) R ₊ ²ⁿ from an arbitrary initial point(x ⁰, y⁰) R ₊ ²ⁿ witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.     

Halfspace range search: An algorithmic application ofk-sets

Given a fixed setS ofn points inE ³ and a query plane, the halfspace range search problem asks for the retrieval of all points ofS on a chosen side of. We prove that withO(n(logn)⁸ (loglogn)⁴) storage it is possible to solve this problem inO(k+logn) time, wherek is the number of points to be reported. This result rests crucially on a new combinatorial derivation. We show that the total number ofj-sets (j=1, ...,k) realized by a set ofn points inE ³ isO(nk ⁵); ak-set is any subset ofS of sizek which can be separated from the rest ofS by a plane.Supported in part by NSF grants MCS 83-03925 and the Office of Naval Research and the Defense Advanced Research Projects Agency under contract N00014-83-K-0146 and ARPA Order No. 4786.Supported in part by Joint Services Electronics Program under Contract N00014-79-C-0424.     

A Sharp Threshold for k‐Colorability

Let k be a fixed integer and f_k(n, p) denote the probability that the random graph G(n, p) is k‐colorable. We show that for k≥3, there exists d_k(n) such that for any ϵ>0, (1) As a result we conclude that for sufficiently large n the chromatic number of G(n, d/n) is concentrated in one value for all but a small fraction of d>1. ©1999 John Wiley & Sons, Inc. Random Struct. Alg., 14, 63–70, 1999     

Largest planar matching in random bipartite graphs

For a distribution ?? over labeled bipartite (multi) graphs G = (W, M, E), |W| = |M| = n, let L(n) denote the size of the largest planar matching of G (here W and M are posets drawn on the plane as two ordered rows of nodes and edges are drawn as straight lines). We study the asymptotic (in n) behavior of L(n) for different distributions ??. Two interesting instances of this problem are Ulam's longest increasing subsequence problem and the longest common subsequence problem. We focus on the case where ?? is the uniform distribution over the k‐regular bipartite graphs on W and M. For k = o(n^1/4), we establish that $L(n) \slash \sqrt{kn}$ tends to 2 in probability when n → ∞. Convergence in mean is also studied. Furthermore, we show that if each of the n² possible edges between W and M are chosen independently with probability 0 < p < 1, then L(n)/n tends to a constant γ_p in probability and in mean when n → ∞. © 2002 Wiley Periodicals, Inc. Random Struct. Alg., 21: 162–181, 2002     

The real spectrum of an ideal and KO-theory exact sequences

A construction in abstract real algebra is used to define invariants S _n(A) of commutative rings, with or without identity. If A=C(X) is the ring of continuous real functions on a compact space, then S _n(A) = k0^–n(X), and, for any A, S _n(A) Z[1/2]-W _n(A) Z[1/2], where the W _n(A) are the Witt groups of A. In addition, a short exact sequence of rings yields a long exact sequence of the groups S _n. The functors S _n(A) thus provide a solution of a problem proposed by Karoubi. This paper primarily deals with the exact sequences involving a ring A and an ideal I A. Work supported in part by NSF Grant DMS85-06816.     

Ratewise-optimal non-sequential search strategies under constraints on the tests

Already in his Lectures on Search [A. Rényi, Lectures on the theory of search, University of North Carolina, Chapel Hill, Institute of Statistics, Mimeo Series No. 6007, 1969. [11]] Renyi suggested to consider a search problem, where an unknown is to be found by asking for containment in a minimal number m(n,k) of subsets A₁,…,A_m with the restrictions |A_i|k<n/2 for i=1,2,…,m.Katona gave in 1966 the lower bound m(n,k)logn/h(k/n) in terms of binary entropy and the upper bound m(n,k)(logn+1)/logn/k·n/k, which was improved by Wegener in 1979 to m(n,k)logn/logn/k(n/k-1).We prove here for k=pn that m(n,k)=logn+o(logn)/h(p), that is, ratewise optimality of the entropy bound: .Actually this work was motivated by a more recent study of Karpovsky, Chakrabarty, Levitin and Avresky of a problem on fault diagnosis in hypercubes, which amounts to finding the minimal number M(n,r) of Hamming balls of radius r=ρn with in the Hamming space , which separate the vertices. Their bounds on M(n,r) are far from being optimal. We establish bounds implying

However, it must be emphasized that the methods of prove for our two upper bounds are quite different.