Well dispersed sequences in [0,1]d

Given a sequence z¯=(z1,z2,…) where zk∈[0,1]d, the dispersion of z¯ is defined byμd(z¯)=infn≥1infm≥1n1/d‖zm−zm+n‖, where ‖⋅‖ is taken to be the L1 metric ‖⋅‖1 on [0,1]d. This is a natural measure for how “spread out” the sequence z¯ is. In this paper, we investigate αd:=supz¯μd(z¯). Note that the requirement μd(z¯)=αd>0 is a very stringent condition on the distribution of the zi. For example, it implies that ‖zm−zm+1‖≥αd for all m≥1. We show by construction that αd≥((2d−1(2d−1))1/d(1+∑k≥11F2k))−1>0.098 where Fn denotes the nth Fibonacci number. We also introduce a combinatorial problem for d-tuples of permutations which yields bounds on αd. This work extends previous results of the authors where the value of α1 is determined.