Voronoi Diagrams of Lines in 3-Space Under Polyhedral Convex Distance Functions

The combinatorial complexity of the Voronoi diagram ofnlines in three dimensions under a convex distance function induced by a polytope with a constant number of edges is shown to beO(n²α(n)log n), where α(n) is a slowly growing inverse of the Ackermann function. There are arrangements ofnlines where this complexity can be as large as Ω(n²α(n)).     

Values of the Euler Function in Various Sequences

Let ϕ(n) and λ(n) denote the Euler and Carmichael functions, respectively. In this paper, we investigate the equation ϕ(n)^r = λ(n)^s, where r ≥ s ≥ 1 are fixed positive integers. We also study those positive integers n, not equal to a prime or twice a prime, such that ϕ(n) = p − 1 holds with some prime p, as well as those positive integers n such that the equation ϕ(n) = f(m) holds with some integer m, where f is a fixed polynomial with integer coefficients and degree degf > 1.     

On weighted positivity and the Wiener regularity of a boundary point for the fractional Laplacian

A sufficient condition for the Wiener regularity of a boundary point with respect to the operator (− Δ)^μ inR ⁿ ,n≥1, is obtained, for μ∈(0,1/2n)/(1,1/2n−1). This extends some results for the polyharmonic operator obtained by Maz'ya and Maz'ya-Donchev. As in the polyharmonic case, the proof is based on a weighted positivity property of (− Δ)^μ, where the weight is a fundamental solution of this operator. It is shown that this property holds for μ as above while there is an interval [A _n , 1/2n−A _n ], whereA _n →1, asn→∞, with μ-values for which the property does not hold. This interval is non-empty forn≥8.     

The Maximum of a Critical Branching Wiener Process

Consider a critical branching Wiener process on ¹. Let M(n) be the location of the most right particle at time n. A limit distribution theorem is proved for n ^–1/2 M(n).     

Routing through a generalized switchbox

We present an algorithm for the routing problem for two-terminal nets in generalized switchboxes. A generalized switchbox is any subset R of the planar rectangular grid with no nontrivial holes, i.e., every finite face has exactly four incident vertices. A net is a pair of nodes of nonmaximal degree on the boundary of R. A solution is a set of edge-disjoint paths, one for each net. Our algorithm solves standard generalized switchbox routing problems in time O(n(log n)²) where n is the number of vertices of R, i.e., it either finds a solution or indicates that there is none. A problem is standard if deg(ν) + ter(ν) is even for all vertices ν where deg(ν) is the degree of ν and ter(ν) is the number of nets which have ν as a terminal. For nonstandard problems we can find a solution in time O(n(log n)² + |U|²) where U is the set of vertices ν with deg(ν) + ter(ν) is odd.     

On the Uniform Convergence of Walsh-Fourier Series

We study the uniform convergence of Walsh-Fourier series of functions on the generalized Wiener class BV (p(n)↑∞) This revised version was published online in June 2006 with corrections to the Cover Date.     

On the first pontrjagin class of homotopy complex projective spaces

Let M ²ⁿ be a closed smooth manifold homotopy equivalent to the complex projective space ℂP(n). It is known that the first Pontrjagin class p ₁(M) of M ²ⁿ has the form (n+1+24α(M))u ² for some integer α(M) where u is a generator of H ²(M; ℤ). We prove that α(M) is even when n is even but not divisible by 64.     

Equidistribution of Heegner points and the partition function

Let p(n) denote the number of partitions of a positive integer n. In this paper we study the asymptotic growth of p(n) using the equidistribution of Galois orbits of Heegner points on the modular curve X ₀(6). We obtain a new asymptotic formula for p(n) with an effective error term which is O(n^-(\frac12+d)){O(n^{-(\frac{1}{2}+\delta)})} for some δ > 0. We then use this asymptotic formula to sharpen the classical bounds of Hardy and Ramanujan, Rademacher, and Lehmer on the error term in Rademacher’s exact formula for p(n).     

Singularity of orbital measures in SU(n)

We show that the minimalk such that μ^κ ∈L ¹(SU(n)) for all central, continuous measures μ on SU(n) isk=n. We do this by exhibiting an elementg∈SU(n) for which the (n−1)-fold product of its conjugacy class has zero Haar measure. This ensures that if μ _g is the corresponding orbital measure supported on the conjugacy class, then μ _g ^n-1 is singular toL ¹. This research is supported in part by NSERC. The hospitality of the University of Waterloo is gratefully acknowledged.     

Growth of transcendental entire functions on algebraic varieties

LetX be a complete intersection algebraic variety of codimensionm>1 in ℂ ^m+n . We define the notion of (p,q)-order and (p,q)-K-type for transcendental entire functionsfεO(ℂ ^m+n ) whereK is a non-pluripolar compact subset of ℂ ^m+n . Further, we consider the analogues of (p,q)-order and (p,q)-K-type inO(X). We discuss the series expansions of the functions inO(X) in terms of an orthogonal basis in a Hilbert spaceL ²(X, μ), where μ is a capacitary extremal measure onK. Author is grateful to the NSA for partial support during the period of this research.     

Quadratic Hermite–Padé polynomials associated with the exponential function

The asymptotic behavior of quadratic Hermite–Padé polynomials associated with the exponential function is studied for n→∞. These polynomials are defined by the relation

(*)

p_n(z)+q_n(z)e^z+r_n(z)e^2z=O(z³ⁿ⁺²) as z→0,

where O(·) denotes Landau's symbol. In the investigation analytic expressions are proved for the asymptotics of the polynomials, for the asymptotics of the remainder term in (*), and also for the arcs on which the zeros of the polynomials and of the remainder term cluster if the independent variable z is rescaled in an appropriate way. The asymptotic expressions are defined with the help of an algebraic function of third degree and its associated Riemann surface. Among other possible applications, the results form the basis for the investigation of the convergence of quadratic Hermite–Padé approximants, which will be done in a follow-up paper.     

Approximation Algorithms for Min–Max Tree Partition

We consider the problem of partitioning the node set of a graph intopequal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded error ratio can be given for the problem unless P = NP. We present anO(n²) time algorithm for the problem, wherenis the number of nodes in the graph. Assuming that the edge lengths satisfy the triangle inequality, its error ratio is at most 2p − 1. We also present an improved algorithm that obtains as an input a positive integerx. It runs inO(2^{(p + x)p}n²) time, and its error ratio is at most (2 − x/(x + p − 1))p.     

Some remarks on universal graphs

LetΓ be a class of countable graphs, and let ℱ(Γ) denote the class of all countable graphs that do not contain any subgraph isomorphic to a member ofΓ. Furthermore, letTΓ andHΓ denote the class of all subdivisions of graphs inΓ and the class of all graphs contracting to a member ofΓ, respectively. As the main result of this paper it is decided which of the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ),n≦ℵ₀, contain a universal element. In fact, for ℱ(TK ⁴)=ℱ(HK ⁴) a strongly universal graph is constructed, whereas for 5≦n≦ℵ₀ the classes ℱ(TK ⁿ ) and ℱ(HK ⁿ ) have no universal elements. Dedicated to Klaus Wagner on his 75^th birthday     

On piecewise-polynomial approximation of functions with a bounded fractional derivative in an Lp-norm

We study the error in approximating functions with a bounded (r + α)th derivative in an L_p-norm. Here r is a nonnegative integer, α ε [0, 1), and ƒ^{(r + α)} is the classical fractional derivative, i.e., ƒ^{(r + α)}(y) = ∝₀¹, ^α d(ƒ^(r)(t)). We prove that, for any such function ƒ, there exists a piecewise-polynomial of degree s that interpolates ƒ at n equally spaced points and that approximates ƒ with an error (in sup-norm) ƒ^{(r + α)}_p O(n^{−(r+α−1/p}). We also prove that no algorithm based on n function and/or derivative values of ƒ has the error equal ƒ^{(r + α)}_p O(n^{−(r+α−1/p}) for any ƒ. This implies the optimality of piecewise-polynomial interpolation. These two results generalize well-known results on approximating functions with bounded rth derivative (α = 0). We stress that the piecewise-polynomial approximation does not depend on α nor on p. It does not depend on the exact value of r as well; what matters is an upper bound s on r, s r. Hence, even without knowing the actual regularity (r, α, and p) of ƒ, we can approximate the function ƒ with an error equal (modulo a constant) to the minimal worst case error when the regularity were known.     

A generalization of bounded variation

Generalized Wiener classes are considered. For these classes the exact order of Fourier coefficients with respect to the trigonometric system is established and the estimation of ‖S _n(·, f)-f(·)‖_{C [0,2π]} where S _n(·, f) are the Fourier partial sums, is given. In particular, a uniform convergence criterion for the Fourier trigonometric series is obtained. This revised version was published online in August 2006 with corrections to the Cover Date.     

BLO spaces associated with the Ornstein–Uhlenbeck operator

Let (Rn,|⋅|,dγ) be the Gauss measure metric space, where Rn denotes the n-dimensional Euclidean space, |⋅| the Euclidean norm and for all x∈Rn the Gauss measure. In this paper, for any a∈(0,∞), the authors introduce some BLOa(γ) space, namely, the space of functions with bounded lower oscillation associated with a given class of admissible balls with parameter a. Then the authors prove that the noncentered local natural Hardy–Littlewood maximal operator is bounded from BMO(γ) of Mauceri and Meda to BLOa(γ). Moreover, a characterization of the space BLOa(γ), via the local natural maximal operator and BMO(γ), is given. The authors further prove that a class of maximal singular integrals, including the corresponding maximal operators of both imaginary powers of the Ornstein–Uhlenbeck operator and Riesz transforms of any order associated with the Ornstein–Uhlenbeck operator, are bounded from L^∞(γ) to BLOa(γ).     

Bounds on margin distributions in learning problems

Let be a probability space and let P_n be the empirical measure based on i.i.d. sample (X₁,…,X_n) from P. Let be a class of measurable real valued functions on For define F_f(t):=P{ft} and F_n,f(t):=P_n{ft}. Given γ(0,1], define _n,γ(δ):=1/(n^1−γ/2δ^γ). We show that if the L₂(P_n)-entropy of the class grows as ^−α for some α(0,2), then, for all and all δ(0,Δ_n), Δ_n=O(n^1/2),

and

where and c(σ)↓1 as σ↓0 (the above inequalities hold for any fixed σ(0,1] with a high probability). Also, define

Then for all

uniformly in and with probability 1 (for the above ratio is bounded away from 0 and from ∞). The results are motivated by recent developments in machine learning, where they are used to bound the generalization error of learning algorithms. We also prove some more general results of similar nature, show the sharpness of the conditions and discuss the applications in learning theory.     

Measuring and computing natural generators for homology groups

We develop a method for measuring homology classes. This involves two problems. First, we define the size of a homology class, using ideas from relative homology. Second, we define an optimal basis of a homology group to be the basis whose elements' size have the minimal sum. We provide a greedy algorithm to compute the optimal basis and measure classes in it. The algorithm runs in O(βn³log²n) time, where n is the size of the simplicial complex and β is the Betti number of the homology group. Finally, we prove the stability of our result. The algorithm can be adapted to measure any given class.     

Minimum asymptotic error of algorithms for solving ODE

We deal with algorithms for solving systems z′(x) = f(x, z(x)), x ε [0, c], z(0) = η where f has r continuous bounded derivatives in [0, c) × ^s. We consider algorithms whose sole dependence on f is through the values of n linear continuous functionals at f. We show that if these functionals are defined by partial derivatives off then, roughly speaking, the error of an algorithm (for a fixed f) cannot converge to zero faster than n^−r as n → +∞. This minimal error is achieved by the Taylor algorithm. If arbitrary linear continuous functionals are allowed, then the error cannot converge to zero faster than n^−(r+1) as n → +∞. This minimal error is achieved by the Taylor-integral algorithm which uses integrals of f.     

Decomposable graphs and definitions with no quantifier alternation

Let D(G) be the minimum quantifier depth of a first order sentence Φ that defines a graph G up to isomorphism. Let D₀(G) be the version of D(G) where we do not allow quantifier alternations in Φ. Define q₀(n) to be the minimum of D₀(G) over all graphs G of order n.We prove that for all n we have

log^*n−log^*log^*n−2≤q₀(n)≤log^*n+22,