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 2 k n 2 + O ( n 1 + ε ) and (2) for every k = ⌊ n α ⌋ , where α is a fixed real such that 0 < α < 1 , f k ( n ) = 1 2 k n 2 + O ( n β ) , for some β < 2 − α . Since f k ( n ) ⩾ 1 2 k n 2 − n 2 k , 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.