Constructions of asymptotically shortest k-radius sequences

Let k be a positive integer. A sequence s over an n-element alphabet A is called a k-radius sequence if every two symbols from A occur in s at distance of at most k. Let f _k(n) denote the length of a shortest k-radius sequence over A. We provide constructions demonstrating that (1) for every fixed k and for every fixed ε>0, f _k(n)=1/2k n ²+O(n ^1+ε) and (2) for every k=n ^α, where α is a fixed real such that 0<α<1, f _k(n)=1/2k n ²+O(n ^β), for some β<2-α. Since f _k(n)≥ 1/2k n ²-n/2k, the constructions give asymptotically optimal k-radius sequences. Finally, (3) we construct optimal 2-radius sequences for a 2p-element alphabet, where p is a prime.