Variations on (0, s)-Sequences

In the first part of this paper, after a survey on the general theory of (t, s)-sequences, we review the main constructions of (0, s)-sequences and point out some relations between them. From these comparisons and from examples we have met in another context, we have found new (0, s)-sequences in prime base b to which the second part is devoted; the proofs are based on the general framework of formal Laurent series introduced by Niederreiter; the construction can be randomized and should have numerical applications.     

On Positive and Copositive Polynomial and Spline Approximation inLp[−1, 1], 0<p<∞

For a functionfL_p[−1, 1], 0<p<∞, with finitely many sign changes, we construct a sequence of polynomialsP_nΠ_nwhich are copositive withfand such that f−P_npCω(f, (n+1)⁻¹)_p, whereω(f, t)_pdenotes the Ditzian–Totik modulus of continuity inL_pmetric. It was shown by S. P. Zhou that this estimate is exact in the sense that if f has at least one sign change, thenωcannot be replaced byω²if 1<p<∞. In fact, we show that even for positive approximation and all 0<p<∞ the same conclusion is true. Also, some results for (co)positive spline approximation, exact in the same sense, are obtained.     

Rate of Convergence for the Absolutely (C, α) Summable Fourier Series of Functions of Bounded Variation

A theorem of Bosanquet states that the Fourier series of a 2π-periodic function of bounded variation is absolutely (C, α) summable. In this paper we give a quantitative version of Bosanquet's result.     

Zolotarevω-Polynomials inWH[0, 1]

The main result of this paper characterizes generalizationsof Zolotarev polynomials as extremal functions in the Kolmogorov–Landauproblem

Full-size image

whereω(t) is a concave modulus of continuity,r, m: 1mr,are integers, andBB₀(r, m, ω). We show that theextremal functionsZ_Bhaver+1 points of alternance andthe full modulus of continuity ofZ^(r)_B: ω(Z^(r)_B; t)=ω(t) for allt[0, 1]. This generalizesthe Karlin's result on the extremality of classical Zolotarevpolynomials in the problem () forω(t)=tand allBB_r.     

Star discrepancy estimates for digital (t, m, 2)-nets and digital (t, 2) -sequences over Z2

Summary We prove upper bounds on the star discrepancy of digital (t, m, 2)-nets and (t, 2)-sequences over Z₂. The main tool is a decomposition lemma for digital (t, m, 2)-nets, which states that every digital (t, m, 2)-net is just the union of 2^tdigitally shifted digital (0, m - t, 2)-nets. Using this result we generalize upper bounds on the star discrepancy of digital (0, m, 2) -nets and (0, 2) -sequences.     

Logarithmic Estimates for the Density of Hypoelliptic Two-Parameter Diffusions

We consider a hypoelliptic two-parameter diffusion. We first prove a sharp upper bound in small time (s, t)[0, 1]² for the L^p-moments of the inverse of the Malliavin matrix of the diffusion process. Second, we establish the behaviour of2² log p_s, t(x, y), as ↓0, where x is the initial condition of the diffusion, = , and p_s, t(x, y) is the density of the hypoelliptic two-parameter diffusion.     

Scrambling Sobol' and Niederreiter–Xing Points

Hybrids of equidistribution and Monte Carlo methods of integration can achieve the superior accuracy of the former while allowing the simple error estimation methods of the latter. In particular, randomized (0, m, s)-nets in basebproduce unbiased estimates of the integral, have a variance that tends to zero faster than 1/nfor any square integrable integrand and have a variance that for finitenis never more thane?2.718 times as large as the Monte Carlo variance. Lower bounds thaneare known for special cases. Some very important (t, m, s)-nets havet>0. The widely used Sobol' sequences are of this form, as are some recent and very promising nets due to Niederreiter and Xing. Much less is known about randomized versions of these nets, especially ins>1 dimensions. This paper shows that scrambled (t, m, s)-nets enjoy the same properties as scrambled (0, m, s)-nets, except the sampling variance is guaranteed only to be belowb^t[(b+1)/(b−1)]^stimes the Monte Carlo variance for a least-favorable integrand and finiten.     

Calculation of the Quality Parameter of Digital Nets and Application to Their Construction

In quasi-Monte Carlo methods, point sets of low discrepancy are crucial for accurate results. A class of point sets with low theoretic upper bounds of discrepancy are the digital point sets known as digital (t, m, s)-nets which can be implemented very efficiently. The parameter t is indicative of the quality; i.e., small values of t lead to small upper bounds of the discrepancy. We introduce an effective way to establish this quality parameter t for digital nets constructed over arbitrary finite fields and give an application to the construction of digital nets of high quality.     

Approximation algorithms for MAX–MIN tiling

The MAX–MIN tiling problem is as follows. We are given A[1,…,n][1,…,n], a two-dimensional array where each entry A[i][j] stores a non-negative number. Define a tile of A to be a subarray A[ℓ,…,r][t,…,b] of A, the weight of a tile to be the sum of all array entries in it, and a tiling of A to be a collection of tiles of A such that each entry A[i][j] is contained in exactly one tile. Given a weight bound W the goal of our MAX–MIN tiling problem is to find a tiling of A such that: (1) each tile is of weight at least W (the MIN condition), and (2) the number of tiles is maximized (the MAX condition). The MAX–MIN tiling problem is known to be NP-hard; here, we present first non-trivial approximations algorithms for solving it.     

On the spectral function of the Poisson–Voronoi cells

Denote by (t)=∑_n1e^−λ_nt, t>0, the spectral function related to the Dirichlet Laplacian for the typical cell of a standard Poisson–Voronoi tessellation in . We show that the expectation E(t), t>0, is a functional of the convex hull of a standard d-dimensional Brownian bridge. This enables us to study the asymptotic behaviour of E(t), when t→0⁺,+∞. In particular, we prove that the law of the first eigenvalue λ₁ of satisfies the asymptotic relation lnP{λ₁t}−2^dω_dj_(d−2)/2^d·t^−d/2 when t→0⁺, where ω_d and j_(d−2)/2 are respectively the Lebesgue measure of the unit ball in and the first zero of the Bessel function J_(d−2)/2.