Dyadic Diaphony of Digital Nets Over ?2

The dyadic diaphony, introduced by Hellekalek and Leeb, is a quantitative measure for the irregularity of distribution of point sets in the unit-cube. In this paper we study the dyadic diaphony of digital nets over ℤ₂. We prove an upper bound for the dyadic diaphony of nets and show that the convergence order is best possible. This follows from a relation between the dyadic diaphony and the L₂{\cal L}_2 discrepancy. In order to investigate the case where the number of points is small compared to the dimension we introduce the limiting dyadic diaphony, which is defined as the limiting case where the dimension tends to infinity. We obtain a tight upper and lower bound and we compare this result with the limiting dyadic diaphony of a random sample.     

Dimensions of random recursive sets

We prove a theorem that generalizes the equality among the packing, Hausdorff, and upper and lower Minkowski dimensions for a general class of random recursive constructions, and apply it to constructions with finite memory. Then we prove an upper bound on the packing dimension of certain random distribution functions on [0, 1]. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 328, 2005, pp. 20–26.     

Cutting dense point sets in half

A halving hyperplane of a set S of n points in R ^d contains d affinely independent points of S so that equally many of the points off the hyperplane lie in each of the two half-spaces. We prove bounds on the number of halving hyperplanes under the condition that the ratio of largest over smallest distance between any two points is at most , δ some constant. Such a set S is called dense. In d = 2 dimensions the number of halving lines for a dense set can be as much as , and it cannot exceed . The upper bound improves over the current best bound of which holds more generally without any density assumption. In d = 3 dimensions we show that is an upper bound on the number of halving planes for a dense set. The proof is based on a metric argument that can be extended to d≥ 4 dimensions, where it leads to as an upper bound for the number of halving hyperplanes. Received March 22, 1995, and in revised form January 15, 1996.     

On Linear Programming Bounds for Spherical Codes and Designs

We investigate universal bounds on spherical codes and spherical designs that could be obtained using Delsartes linear programming methods. We give a lower estimate for the LP upper bound on codes, and an upper estimate for the LP lower bound on designs. Specifically, when the distance of the code is fixed and the dimension goes to infinity, the LP upper bound on codes is at least as large as the average of the best known upper and lower bounds. When the dimension n of the design is fixed, and the strength k goes to infinity, the LP bound on designs turns out, in conjunction with known lower bounds, to be proportional to k^n-1.     

Large deviations for a catalytic Fleming‐Viot branching system

We consider a jump‐diffusion process describing a system of diffusing particles that upon contact with an obstacle (catalyst) die and are replaced by an independent offspring with position chosen according to a weighted average of the remaining particles. The obstacle is a bounded nonnegative function V(x) and the birth/death mechanism is similar to the Fleming‐Viot critical branching. Since the mass is conserved, we prove a hydrodynamic limit for the empirical measure, identified as the solution to a generalized semilinear (reaction‐diffusion) equation, with nonlinearity given by a quadratic operator. A large‐deviation principle from the deterministic hydrodynamic limit is provided. The upper bound is given in any dimension, and the lower bound is proven for d = 1 and V bounded away from 0. An explicit formula for the rate function is provided via an Orlicz‐type space. © 2006 Wiley Periodicals, Inc.     

Some remarks on absolute continuity and quantization of probability measures

We introduce a notion of monotonicity of dimensions of measures. We show that the upper and lower quantization dimensions are not monotone. We give sufficient conditions in terms of so-called vanishing rates such that νμ implies . As an application, we determine the quantization dimension of a class of measures which are absolutely continuous w.r.t. some self-similar measure, with the corresponding Radon–Nikodym derivative bounded or unbounded. We study the set of quantization dimensions of measures which are absolutely continuous w.r.t. a given probability measure μ. We prove that the infimum on this set coincides with the lower packing dimension of μ. Furthermore, this infimum can be attained provided that the upper and lower packing dimensions of μ are equal.     

Cubature Formulas of a Nonalgebraic Degree of Precision

We deal with cubature formulas that are exact for polynomials and also for polynomials multiplied by r, where r is the Euclidean distance to the origin. A general lower bound for the number of nodes for a specified degree of precision is given. This bound is improved for centrally symmetric integrals. A set of constraints (consistency conditions) is introduced for the construction of fully symmetric formulas. For one dimension and arbitrary degree, it is shown that the lower bound is sharp for centrally symmetric integrals. For higher dimensions, as an illustration, cubature formulas are only constructed for low degrees. March 6, 2000. Date revised: April 30, 2001. Date accepted: May 31, 2001.     

Extensions of Generalized Product Caps

We give some variants of a new construction for caps. As an application of these constructions, we obtain a 1216-cap in PG(9,3) a 6464-cap in PG(11,3) and several caps in ternary affine spaces of larger dimension, which lead to better asymptotics than the caps constructed by Calderbank and Fishburn [1]. These asymptotic improvements become visible in dimensions as low as 62, whereas the bound from Calderbank and Fishburn [1] is based on caps in dimension 13,500.     

On the Countability of Noetherian Dimension of Modules

Abstract

It is shown that a module M has countable Noetherian dimension if and only if the lengths of ascending chains of submodules of M has a countable upper bound. This shows in particular that every submodule of a module with countable Noetherian dimension is countably generated. It is proved that modules with Noetherian dimension over locally Noetherian rings have countable Noetherian dimension. We also observe that ω^ω is a universal upper bound for the lengths of all chains in Artinian modules over commutative rings.     

Bounds on the density of states for Schrödinger operators

We establish bounds on the density of states measure for Schrödinger operators. These are deterministic results that do not require the existence of the density of states measure, or, equivalently, of the integrated density of states. The results are stated in terms of a “density of states outer-measure” that always exists, and provides an upper bound for the density of states measure when it exists. We prove log-Hölder continuity for this density of states outer-measure in one, two, and three dimensions for Schrödinger operators, and in any dimension for discrete Schrödinger operators.     

Nesterenko’s criterion when the small linear forms oscillate

In this paper we generalize Nesterenko’s criterion to the case where the small linear forms have an oscillating behaviour (for instance given by the saddle point method). This criterion provides both a lower bound for the dimension of the vector space spanned over the rationals by a family of real numbers and a measure of simultaneous approximation to these numbers (namely, an upper bound for the irrationality exponent if 1 and only one other number are involved). As an application, we prove an explicit measure of simultaneous approximation to ζ(5), ζ(7), ζ(9), and ζ(11), using Zudilin’s proof that at least one of these numbers is irrational.     

Bounds on Oscillatory Integral Operators Based on Multilinear Estimates

We apply the Bennett–Carbery–Tao multilinear restriction estimate in order to bound restriction operators and more general oscillatory integral operators. We get improved L ^p estimates in the Stein restriction problem for dimension at least 5 and a small improvement in dimension 3. We prove similar estimates for H?rmander-type oscillatory integral operators when the quadratic term in the phase function is positive definite, getting improvements in dimension at least 5. We also prove estimates for H?rmander-type oscillatory integral operators in even dimensions. These last oscillatory estimates are related to improved bounds on the dimensions of curved Kakeya sets in even dimensions.     

VC Dimensions of Principal Component Analysis

Motivated by statistical learning theoretic treatment of principal component analysis, we are concerned with the set of points in ℝ ^d that are within a certain distance from a k-dimensional affine subspace. We prove that the VC dimension of the class of such sets is within a constant factor of (k+1)(d−k+1), and then discuss the distribution of eigenvalues of a data covariance matrix by using our bounds of the VC dimensions and Vapnik’s statistical learning theory. In the course of the upper bound proof, we provide a simple proof of Warren’s bound of the number of sign sequences of real polynomials.     

Stability of quantization dimension and quantization for homogeneous Cantor measures

We effect a stabilization formalism for dimensions of measures and discuss the stability of upper and lower quantization dimension. For instance, we show for a Borel probability measure with compact support that its stabilized upper quantization dimension coincides with its packing dimension and that the upper quantization dimension is finitely stable but not countably stable. Also, under suitable conditions explicit dimension formulae for the quantization dimension of homogeneous Cantor measures are provided. This allows us to construct examples showing that the lower quantization dimension is not even finitely stable. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

An elementary proof of the exponential blow-up for semi-linear wave equations

This paper deals with the upper bound of the life span of classical solutions to □u = ∣u∣^p, u∣_{t = 0} = εφ(x), u_t∣_t=0 = εψ(x) with the critical power of p in two or three space dimensions. Zhou has proved that the rate of the upper bound of this life span is exp(ε^−p(p−1)). But his proof, especially the two-dimensional case, requires many properties of special functions. Here we shall give simple proofs in each space dimension which are produced by pointwise estimates of the fundamental solution of □. We claim that both proofs are done in almost the same way.     

An explicit bound for uniform perfectness of the Julia sets of rational maps

A compact set C in the Riemann sphere is called uniformly perfect if there is a uniform upper bound on the moduli of annuli which separate C. Julia sets of rational maps of degree at least two are uniformly perfect. Proofs have been given independently by Ma né and da Rocha and by Hinkkanen, but no explicit bounds are given. In this note, we shall provide such an explicit bound and, as a result, give another proof of uniform perfectness of Julia sets of rational maps of degree at least two. As an application, we provide a lower estimate of the Hausdorff dimension of the Julia sets. We also give a concrete bound for the family of quadratic polynomials in terms of the parameter c. Received: 7 June 1999; in final form: 9 November 1999 / Published online: 17 May 2001     

Smooth interval maps have symbolic extensions

We prove that if X denotes the interval or the circle then every transformation T:X→X of class C ^r , where r>1 is not necessarily an integer, admits a symbolic extension, i.e., every such transformation is a topological factor of a subshift over a finite alphabet. This is done using the theory of entropy structure. For such transformations we control the entropy structure by providing an upper bound, in terms of Lyapunov exponents, of local entropy in the sense of Newhouse of an ergodic measure ν near an invariant measure μ (the antarctic theorem). This bound allows us to estimate the so-called symbolic extension entropy function on invariant measures (the main theorem), and as a consequence, to estimate the topological symbolic extension entropy; i.e., a number such that there exists a symbolic extension with topological entropy arbitrarily close to that number. This last estimate coincides, in dimension 1, with a conjecture stated by Downarowicz and Newhouse [13, Conjecture 1.2]. The passage from the antarctic theorem to the main theorem is applicable to any topological dynamical system, not only to smooth interval or circle maps.     

On the performance of the ICP algorithm

We present upper and lower bounds for the number of iterations performed by the Iterative Closest Point (ICP) algorithm. This algorithm has been proposed by Besl and McKay as a successful heuristic for matching of point sets in d-space under translation, but so far it seems not to have been rigorously analyzed. We consider two standard measures of resemblance that the algorithm attempts to optimize: The RMS (root mean squared distance) and the (one-sided) Hausdorff distance. We show that in both cases the number of iterations performed by the algorithm is polynomial in the number of input points. In particular, this bound is quadratic in the one-dimensional problem, under the RMS measure, for which we present a lower bound construction of Ω(nlogn) iterations, where n is the overall size of the input. Under the Hausdorff measure, this bound is only O(n) for input point sets whose spread is polynomial in n, and this is tight in the worst case.We also present several structural geometric properties of the algorithm under both measures. For the RMS measure, we show that at each iteration of the algorithm the cost function monotonically and strictly decreases along the vector Δt of the relative translation. As a result, we conclude that the polygonal path π, obtained by concatenating all the relative translations that are computed during the execution of the algorithm, does not intersect itself. In particular, in the one-dimensional problem all the relative translations of the ICP algorithm are in the same (left or right) direction. For the Hausdorff measure, some of these properties continue to hold (such as monotonicity in one dimension), whereas others do not.     

The Representation of Polyhedra by Polynomial Inequalities

A beautiful result of Brocker and Scheiderer on the stability index of basic closed semi-algebraic sets implies, as a very special case, that every d -dimensional polyhedron admits a representation as the set of solutions of at most d(d+1)/2 polynomial inequalities. Even in this polyhedral case, however, no constructive proof is known, even if the quadratic upper bound is replaced by any bound depending only on the dimension. Here we give, for simple polytopes, an explicit construction of polynomials describing such a polytope. The number of used polynomials is exponential in the dimension, but in the two- and three-dimensional case we get the expected number d(d+1)/2 .