A geometric proof of the combinatorial bounds for the number of optimal solutions for the Euclidean 2-center problem

We provide lower and upper bounds for γ(n), the number of optimal solutions for the two-center problem: “Given a set S of n points in the real plane, find two closed discs whose union contains all of the points such that the radius of the larger disc is minimized.”The main result of the paper shows the matching upper and lower bounds for the two-center problem and demonstrates that γ(n)=n.     

Sharp inequalities for convolution-type operators

Let μ be a probability measure on [− a, a], a > 0, and let x₀ε[− a, a], f ε Cⁿ([−2a, 2a]), n 0 even. Using moment methods we derive best upper bounds to ¦∫_−a^a ([f(x₀ + y) + f(x₀ − y)]/2) μ(dy) − f(x₀)¦, leading to sharp inequalities that are attainable and involve the second modulus of continuity of f⁽ⁿ⁾ or an upper bound of it.     

Estimates of Freud-Christoffel functions for some weights with the whole real line as support

Upper and lower bounds for generalized Christoffel functions, called Freud-Christoffel functions, are obtained. These have the form λ_n,p(W,j,x) = infPW_Lp(R)/|P^(j)(X)| where the infimum is taken over all polynomials P(x) of degree at most n − 1. The upper and lower bounds for λ_n,p(W,j,x) are obtained for all 0 < p ∞ and J = 0, 1, 2, 3,… for weights W(x) = exp(−Q(x)), where, among other things, Q(x) is bounded in [− A, A], and Q″ is continuous in β(−A, A) for some A > 0. For p = ∞, the lower bounds give a simple proof of local and global Markov-Bernstein inequalities. For p = 2, the results remove some restrictions on Q in Freud's work. The weights considered include W(x) = exp(− ¦x¦^α/2), α > 0, and W(x) = exp(− exp(¦x¦)), > 0.     

On the degree of weak convergence of a sequence of finite measures to the unit measure under convexity

This is a study of the degree of weak convergence under convexity of a sequence of finite measures μ_j on ^k, k 1, to the unit measure δ_x0. LetQ denote a convex and compact subset of ^k, let ƒ ε C^m(Q), m 0, satisfy a convexity condition and let μ be a finite measure on Q. Using standard moment methods, upper bounds and best upper bounds are obtained for ¦∝_Qƒdμ − ƒ(x₀)¦. They sometimes lead to sharp inequalities which are attained for particular μ and ƒ. These estimates are better than the corresponding ones found in the literature.     

Routing Problems on the Mesh of Buses

The mesh of buses (MBUSs) is a parallel computation model which consists ofn×nprocessors,nrow buses, andncolumn buses, but no local connections between neighboring processors. Annlower bound for the permutation routing on this model is shown. The proof does not depend on common predetermined assumptions such as “if a packet has to move horizontally then it has to ride on a horizontal bus at least once.” As for upper bounds, a 1.5nalgorithm is shown.     

Pseudorandom numbers and entropy conditions

We investigate measures of pseudorandomness of finite sequences (x_n) of real numbers. Mauduit and Sárközy introduced the “well-distribution measure”, depending on the behavior of the sequence (x_n) along arithmetic subsequences (x_ak+b). We extend this definition by replacing the class of arithmetic progressions by an arbitrary class of sequences of positive integers and show that the so obtained measure is closely related to the metric entropy of the class . Using standard probabilistic techniques, this fact enables us to give precise bounds for the pseudorandomness measure of classical constructions. In particular, we will be interested in “truly” random sequences and sequences of the form {n_kω}, where {·} denotes fractional part, (n_k) is a given sequence of integers and ω[0,1).     

Bounds on Turán determinants

Let μ denote a symmetric probability measure on [−1,1] and let (p_n) be the corresponding orthogonal polynomials normalized such that p_n(1)=1. We prove that the normalized Turán determinant Δ_n(x)/(1−x²), where , is a Turán determinant of order n−1 for orthogonal polynomials with respect to . We use this to prove lower and upper bounds for the normalized Turán determinant in the interval −1<x<1.     

Diagnosability of regular systems

A novel approach aimed at evaluating the diagnosability of regular systems under the PMC model is introduced. The diagnosability is defined as the ability to provide a correct diagnosis, although possibly incomplete. This concept is somehow intermediate between one-step diagnosability and sequential diagnosability. A lower bound to diagnosability is determined by lower bounding the minimum of a “syndrome-dependent” bound t_σ over the set of all the admissible syndromes. In turn, t_σ is determined by evaluating the cardinality of the smallest consistent fault set containing an aggregate of maximum cardinality. The new approach, which applies to any regular system, relies on the “edge-isoperimetric inequalities” of connected components of units declaring each other non-faulty. This approach has been used to derive tight lower bounds to the diagnosability of toroidal grids and hypercubes, which improve the existing bounds for the same structures.     

Thin points for Brownian motion

Let Θ(x,r) denote the occupation measure of the ball of radius r centered at x for Brownian motion {W_t}_0≤t≤1 in . We prove that for any analytic set E in [0,1], we have

Full-size image

, where dim_P(E) is the packing dimension of E. We deduce that for any a≥1, the Hausdorff dimension of the set of “thin points” x for which

Full-size image

, is almost surely 2−2/a; this is the correct scaling to obtain a nondegenerate “multifractal spectrum” for the “thin” part of Brownian occupation measure. The methods of this paper differ considerably from those of our work on Brownian thick points, due to the high degree of correlation in the present case. To prove our results, we establish general criteria for determining which deterministic sets are hit by random fractals of ‘limsup type' in the presence of long-range correlations. The hitting criteria then yield lower bounds on Hausdorff dimension. This refines previous work of Khoshnevisan, Xiao and the second author, that required decay of correlations.     

Bounds for Covering Codes over Large Alphabets

Let K_q(n,R) denote the minimum number of codewords in any q-ary code of length n and covering radius R. We collect lower and upper bounds for K_q(n,R) where 6 ≤ q ≤ 21 and R ≤ 3. For q ≤ 10, we consider lengths n ≤ 10, and for q ≥ 11, we consider n ≤ 8. This extends earlier results, which have been tabulated for 2 ≤ q ≤ 5. We survey known bounds and obtain some new results as well, also for s-surjective codes, which are closely related to covering codes and utilized in some of the constructions.AMS Classification: 94B75, 94B25, 94B65Gerzson Kéri - Supported in part by the Hungarian National Research Fund, Grant No. OTKA-T029572.Patric R. J. Östergård - Supported in part by the Academy of Finland, Grants No. 100500 and No. 202315.     

On weighted Lebesgue function type sums

Let I be a finite or infinite interval and dμ a measure on I. Assume that the weight function w(x)>0, w^′(x) exists, and the function w^′(x)/w(x) is non-increasing on I. Denote by ℓ_k's the fundamental polynomials of Lagrange interpolation on a set of nodes x₁<x₂<<x_n in I. The weighted Lebesgue function type sum for 1≤i<j≤n and s≥1 is defined by

In this paper the exact lower bounds of S_n(x) on a “big set” of I and are obtained. Some applications are also given.     

A note on an error estimate for least squares approximation

An asymptotic expansion is obtained which provides upper and lower bounds for the error of the bestL ₂ polynomial approximation of degreen forx ⁿ⁺¹ on [–1, 1]. Because the expansion proceeds in only even powers of the reciprocal of the large variable, and the error made by truncating the expansion is numerically less than, and has the same sign as the first neglected term, very good bounds can be obtained. Via a result of Phillips, these results can be extended fromx ⁿ⁺¹ to anyfC ⁿ⁺¹[–1, 1], provided upper and lower bounds for the modulus off ⁽ⁿ⁺¹⁾ are available.     

Asymptotics for Lp extremal polynomials on the unit circle

Let p > 1, and dμ a positive finite Borel measure on the unit circle Γ: = {z ε C: ¦z¦ = 1}. Define the monic polynomial φ_{n, p}(z)=zⁿ+…εP_n >(the set of polynomials of degree at most n) satisfying

Full-size image

. Under certain conditions on dμ, the asymptotics of φ_{n, p}(z) for z outside, on, or inside Γ are obtained (cf. Theorems 2.2 and 2.4). Zero distributions of φ_{n, p} are also discussed (cf. Theorems 3.1 and 3.2).     

Embeddings in Spaces of Lipschitz Type, Entropy and Approximation Numbers, and Applications

We consider the embeddings of certain Besov and Triebel–Lizorkin spaces in spaces of Lipschitz type. The prototype of such embeddings arises from the result of H. Brézis and S. Wainger (1980, Comm. Partial Differential Equations5, 773–789) about the “almost” Lipschitz continuity of elements of the Sobolev spaces H^1+n/p_p( ⁿ) when 1<p<∞. Two-sided estimates are obtained for the entropy and approximation numbers of a variety of related embeddings. The results are applied to give bounds for the eigenvalues of certain pseudo-differential operators and to provide information about the mapping properties of these operators.     

Über ein simultanes Differenzenverfahren zur Abschätzung der Torsionssteifigkeit und der Kapazität nach beiden Seiten

Summary We consider the torsion of a prism. Let its cross-sectionQ be covered by a square network (lattice) of mesh sizeh.Pólya defined a functionu _i on all lattice points by means of a partial difference equation, and then a functionp onQ by bilinear continuation ofu _i in every square. Top he appliedDirichlet's principle and obtained thus lower bounds for the torsional rigidityP ofQ.—Here we define (§ 3) acell function U _i , attributing a real value to each square; usingU _i , we construct a vector field , to which we can applyThomson's principle and get upper bounds forP.—A simultaneous method for upper and lower bounds is then indicated and discussed (§ 4) and an example is given (§ 5).—Evaluations for capacity may be calculated in a very similar way (§ 6).     

Nodal volumes for eigenfunctions of analytic regular elliptic problems

We establish sharp upper bounds on the (n−1)-dimensional Hausdorff measure of the zero (nodal) sets and on the maximal order of vanishing corresponding to eigenfunctions of a regular elliptic problem on a bounded domain Ω ⊆ ℝ ⁿ with real-analytic boundary. The elliptic operator may be of an arbitrary even order, and its coefficients are assumed to be real-analytic. This extends a result of Donnelly and Fefferman ([DF1], [DF3]) concerning upper bounds for nodal volumes of eigenfunctions corresponding to the Laplacian on compact Riemannian manifolds with boundary.     

New degree bounds for polynomial threshold functions

A real multivariate polynomial p(x ₁, …, x _n ) is said to sign-represent a Boolean function f: {0,1} ⁿ →{−1,1} if the sign of p(x) equals f(x) for all inputs x∈{0,1} ⁿ . We give new upper and lower bounds on the degree of polynomials which sign-represent Boolean functions. Our upper bounds for Boolean formulas yield the first known subexponential time learning algorithms for formulas of superconstant depth. Our lower bounds for constant-depth circuits and intersections of halfspaces are the first new degree lower bounds since 1968, improving results of Minsky and Papert. The lower bounds are proved constructively; we give explicit dual solutions to the necessary linear programs.     

Estimates for the eigenvalues of Hill's equation and applications for the eigenvalues of the laplacian on toroidal surfaces

In this paper we give upper and lower bounds for each eigenvalue λ _n of Hill's differential equation. We apply the results to toroidal surfaces of revolution in order to get estimates for the eigenvalues of the Laplacian in terms of curvature expressions; they are sharp for the flat torus. As an example, we investigate the standard torus in IR³; here, the bounds depend on the radii only.     

Orlicz capacities and Hausdorff measures on metric spaces

In the setting of doubling metric measure spaces with a 1-Poincaré inequality, we show that sets of Orlicz Φ-capacity zero have generalized Hausdorff h-measure zero provided thatwhere Θ⁻¹ is the inverse of the function Θ(t)=Φ(t)/t, and s is the “upper dimension” of the metric measure space. This condition is a generalization of a well known condition in Rⁿ. For spaces satisfying the weaker q-Poincaré inequality, we obtain a similar but slightly more restrictive condition. Several examples are also provided.