Does such an "extremely" equally distributed real, bounded sequence exist?

160 Views Asked by At

For each $\ n\in\mathbb{N},\ $ define the set $\ [n] := \{1,2,\ldots, n\}.\ $ Does there exist a real sequence $\ (a_n)_{n\in\mathbb{N}}\subset [0,1),\ $ such that for each $\ n\in\mathbb{N}\ $ there exists a bijection $\ f:[n]\to [n],\ $ such that $\ a_{f(k)} \in \left[ \frac{k-1}{n}, \frac{k}{n} \right)\ \forall\ k\in [n]\ ?$

In other words, can we construct a sequence $\ (a_n)_{n\in\mathbb{N}}\subset [0,1),\ $ such that for each $\ n\in\mathbb{N},\ \not\exists\ i,j,k\in [n]\ $ with $\ i\neq j\ $ and $\ a_i,a_j\in\left[ \frac{k-1}{n}, \frac{k}{n} \right)\ ?$

2

There are 2 best solutions below

1
On BEST ANSWER

This is Steinhaus’s irregularity of distributions problem, and the answer is no: Berlekamp and Graham (1970) showed that such a sequence cannot be continued beyond $n = 17$.

2
On

I'm pretty sure the Van der Corput sequence basically works (always a good example to keep in mind when looking for small "discrepancy" sequences).

Because you have the closed interval at $0$ and the open interval at $1$, I think we need to do $1$ minus the Van der Corput sequence: $a_n := 1-v_n$, where, for this problem, we start $v_1 := 1$ and have $v_2,v_3,\dots := \frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{5}{8},\frac{3}{8},\frac{7}{8},\frac{1}{16},\frac{9}{16},\frac{5}{16},\frac{13}{16},\frac{3}{16},\frac{11}{16},\frac{7}{16},\frac{15}{16},\dots$.

This sequence has been studied to death. It is quite likely someone has already proved it satisfies what you request (possibly by just looking at $(v_n)_n$ and putting the closed interval at $1$ rather than $0$).

If you can't find a reference and can't prove this sequence works for your problem, let me know, and I'll try to write a proof.