Dynamically Defined Sequences with Small Discrepancy

2019/02/08 by Steinerberger, Stefan
#Classical Analysis and ODEs (math.CA) #Combinatorics (math.CO) #FOS: Mathematics #Number Theory (math.NT)

paper · doi:10.48550/arxiv.1902.03269

Abstract

We study the problem of constructing sequences (x_n)_n=1^∞ on [0,1] in such a way that D_N^* = sup_{0 ≤ x ≤ 1} | \frac \1 ≤ i ≤ N: x_i ≤ x \N - x | is uniformly small. A result of Schmidt shows that necessarily D_N^* \gtrsim (logN) N^-1 for infinitely many N and there are several classical constructions attaining this growth. We describe a type of uniformly distributed sequence that seems to be completely novel: given \x₁, …, x_N-1 \, we construct x_N in a greedy manner x_N = argmin_{mink |x-xk| ≥ N^-10} ∑_k=1^N-11-log(2sin(π|x-x_k|)). We prove that D_N \lesssim (logN) N^-1/2 and conjecture that D_N \lesssim (logN) N^-1. Numerical examples illustrate this conjecture in a very impressive manner. We also establish a discrepancy bound D_N \lesssim (logN)^d N^-1/2 for an analogous construction in higher dimensions and conjecture it to be D_N \lesssim (logN)^d N^-1.

Related

• Outperforming the Best 1D Low-Discrepancy Constructions with a Greedy Algorithm
• Low discrepancy sequences: Theory and Applications
• Variants of the Littlewood conjecture, their connection to uniformly distributed sequences, and the exact order of the discrepancy of van der Corput--Kronecker-type sequences
• The discrepancy of (n_kx) with respect to certain probability measures
• Smooth discrepancy and Littlewood's conjecture