An Algorithm to Compute Bounds for the Star Discrepancy

We propose an algorithm to compute upper and lower bounds for the star discrepancy of an arbitrary sequence of points in the s-dimensional unit cube. The method is based on a particular partition of the unit cube into subintervals and on a specialized procedure for orthogonal range counting. The cardinality of the partition depends on the dimension and on an accuracy parameter that has to be specified. We have implemented this method and here we present results of some computational experiments obtained with this implementation.     

An asymptotic relation between the extreme discrepancy and theL p -discrepancy

An asymptotic expression for the difference between the extreme discrepancy and theL _p -discrepancy of a sequence of points in thes-dimensional unit cube (0, 1] ^s ,s1, is given.     

Low-discrepancy point sets

Various point sets in thes-dimensional unit cube with small discrepancy are constructed.Dedicated to Professor E. Hlawka on the occasion of his seventieth birthday     

General discrepancy estimates III: The Erdös-Turán-Koksma inequality for the Haar function system

The classical Erdös-Turán-Koksma inequality gives us an upper bound for the discrepancy of a sequence in thes-dimensional unit cube in terms of exponential sums, more precisely, in terms of the trigonometric function system.In this paper, we shall prove the inequality of Erdös-Turán-Koksma for the extreme and the star discrepancy, for generalized Haar function systems. Further, we shall show the existence of the inequality of Erdös-Turán-Koksma for the isotropic discrepancy, for generalized Haar and Walsh function systems.Research supported by the Austrian Science Foundation, project no. P9285/TEC.     

Placing of points into the 5-dimensional unit cube

We give a very short survey of the results on placing of points into the unit n-dimensional cube with mutual distances at least one. The main result is that into the 5-dimensional unit cube there can be placed no more than 40 points.     

On the maximum number of points at least one unit away from each other in the unit <Emphasis Type="Italic">n</Emphasis>-cube

We present a very short survey of known results and many new estimates and results on the maximum number of points that can be chosen in the n-dimensional unit cube so that every distance between them is at least 1. Research was supported by Slovak national grant VEGA 1/3839/06.     

Point sets and sequences with small discrepancy

A systematic theory of a class of point sets called (t, m, s)-nets and of a class of sequences called (t, s)-sequences is developed. On the basis of this theory, point sets and sequences in thes-dimensional unit cube with the smallest discrepancy that is currently known are constructed. Various connections with other areas arise in this work, e.g. with orthogonal latin squares, finite projective planes, finite fields, and algebraic coding theory. Applications of the theory of (t, m, s)-nets to two methods for pseudorandom number generation, namely the digital multistep method and the GFSR method, are presented. Several open problems, mostly of a combinatorial nature, are stated.The author wants to thank the Universität Hannover (West Germany) for its hospitality during the period when most of this research was carried out. The results of this paper were presented at the Colloquium on Irregularities of Partitions at Fertöd (Hungary), July 7–11, 1986.     

Construction of low-discrepancy point sets of small size

We report on recently developed algorithms that construct small point sets in the d -dimensional unit cube whose star discrepancies satisfy good and meaningful bounds. These bounds are proved by probabilistic arguments and the algorithms derandomize the corresponding underlying random experiment. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Clique matchings in the <Emphasis Type="Italic">k</Emphasis>-ary <Emphasis Type="Italic">n</Emphasis>-dimensional cube

A clique matching in the k-ary n-dimensional cube (hypercube) is a collection of disjoint one-dimensional faces. A clique matching is called perfect if it covers all vertices of the hypercube. We show that the number of perfect clique matchings in the k-ary n-dimensional cube can be expressed as the k-dimensional permanent of the adjacency array of some hypergraph. We calculate the order of the logarithm of the number of perfect clique matchings in the k-ary n-dimensional cube for an arbitrary positive integer k as n→∞.     

Some open problems concerning the star-discrepancy

We discuss open problems on the minimal star-discrepancy of an n-point set in the d-dimensional unit cube [0,1]^d. We emphasize the aspect of dimension dependence and of simultaneous dependence on n and d.     

Shifted lattice rules based on a general weighted discrepancy for integrals over Euclidean space

We approximate weighted integrals over Euclidean space by using shifted rank-1 lattice rules with good bounds on the “generalised weighted star discrepancy”. This version of the discrepancy corresponds to the classic L_∞ weighted star discrepancy via a mapping to the unit cube. The weights here are general weights rather than the product weights considered in earlier works on integrals over R^d. Known methods based on an averaging argument are used to show the existence of these lattice rules, while the component-by-component technique is used to construct the generating vector of these shifted lattice rules. We prove that the bound on the weighted star discrepancy considered here is of order O(n^−1+δ) for any δ>0 and with the constant involved independent of the dimension. This convergence rate is better than the O(n^−1/2) achieved so far for both Monte Carlo and quasi-Monte Carlo methods.     

Configurations Maximizing the Number of Pairs of Hamming-Adjacent Lattice Points

The following question is considered: Which sets of k lattice points among the n^d points in a d-dimensional cube of length n maximize the number of pairs of points differing in only one coordinate? It is shown that maximal configurations for any (d, n, k) are obtained by choosing the first k points in a lexicographic ordering of the points by coordinates. Some possible generalizations of the problem are discussed.     

Projecting <Emphasis Type="Italic">l</Emphasis><Subscript>∞</Subscript> onto Classical Spaces

We describe an explicit construction of a linear projection of a symmetric conical section of the n-dimensional cube onto a (1+ε)-isomorphic version of the Euclidean ball of proportional dimension, or more generally onto a (1+ε)-isomorphic image of an l _p ^m -ball. Allowing non-linear projections (of logarithmic polynomial nonlinearity) we may even project the full n-dimensional cube onto the same images. This is done by gluing together explicit projections onto two-dimensional spaces, interpreting and modifying a paper of Ben-Tal and Nemirowski on polynomial reductions of conic quadratic programming problems to linear programming problems in terms of Banach spaces.      

The BMO-discrepancy suffers from the curse of dimensionality

We show that the minimal discrepancy of a point set in the d-dimensional unit cube with respect to the BMO seminorm suffers from the curse of dimensionality.     

Menger (N?beling) Manifolds versus Hilbert Cube (Space) Manifolds – A Categorical Comparison

 We show that the n-homotopy category of connected (n+1)-dimensional Menger manifolds is isomorphic to the homotopy category of connected Hilbert cube manifolds whose k-dimensional homotopy groups are trivial for each .     

Generalizations of Heilbronn’s triangle problem

For given integers d,j≥2 and any positive integers n, distributions of n points in the d-dimensional unit cube [0,1]^d are investigated, where the minimum volume of the convex hull determined by j of these n points is large. In particular, for fixed integers d,k≥2 the existence of a configuration of n points in [0,1]^d is shown, such that, simultaneously for j=2,…,k, the volume of the convex hull of any j points among these n points is Ω(1/n^{(j−1)/(1+|d−j+1|)}). Moreover, a deterministic algorithm is given achieving this lower bound, provided that d+1≤j≤k.     

On Heilbronn’s Problem in Higher Dimension

Heilbronn conjectured that given arbitrary n points in the 2-dimensional unit square [0, 1]², there must be three points which form a triangle of area at most O(1/n²). This conjecture was disproved by a nonconstructive argument of Komlós, Pintz and Szemerédi [10] who showed that for every n there is a configuration of n points in the unit square [0, 1]² where all triangles have area at least (log n/n²). Considering a generalization of this problem to dimensions d3, Barequet [3] showed for every n the existence of n points in the d-dimensional unit cube [0, 1]^d such that the minimum volume of every simplex spanned by any (d+1) of these n points is at least (1/n^d). We improve on this lower bound by a logarithmic factor (log n).     

A volume convergence theorem for Alexandrov spaces with curvature bounded above

We obtain a volume convergence theorem for Alexandrov spaces with curvature bounded above with respect to the Gromov-Hausdorff distance. As one of the main tools proving this, we construct an almost isometry between Alexandrov spaces with curvature bounded above, with weak singularities, which are close to each other. Furthermore, as an application of our researches of convergence phenomena, for given positive integer , we prove that, if a compact, geodesically complete, n-dimensional CAT(1)-space has the volume sufficiently close to that of the unit n-sphere, then it is bi-Lipschitz homeomorphic to the unit n-sphere. Received: 30 January 2001; in final form: 30 October 2001 / Published online: 4 April 2002     

A reduction of Keller's conjecture

A family of translates of a closedn-dimensional cube is called a cube tiling if the union of the cubes is the wholen-space and their interiors are disjoint. According to a famous unsolved conjecture of O. H. Keller, two of the cubes in ann-dimensional cube tiling must share a complete (n – 1)-dimensional face. In this paper we shall prove that to solve Keller's conjecture it is sufficient to examine certain factorizations of direct sum of finitely many cyclic group of order four.     

Combinatorial Integer Labeling Theorems on Finite Sets with Applications

Tucker’s well-known combinatorial lemma states that, for any given symmetric triangulation of the n-dimensional unit cube and for any integer labeling that assigns to each vertex of the triangulation a label from the set {±1,±2,…,±n} with the property that antipodal vertices on the boundary of the cube are assigned opposite labels, the triangulation admits a 1-dimensional simplex whose two vertices have opposite labels. In this paper, we are concerned with an arbitrary finite set D of integral vectors in the n-dimensional Euclidean space and an integer labeling that assigns to each element of D a label from the set {±1,±2,…,±n}. Using a constructive approach, we prove two combinatorial theorems of Tucker type. The theorems state that, under some mild conditions, there exists two integral vectors in D having opposite labels and being cell-connected in the sense that both belong to the set {0,1} ⁿ +q for some integral vector q. These theorems are used to show in a constructive way the existence of an integral solution to a system of nonlinear equations under certain natural conditions. An economic application is provided.