Sequences of large radius

A kk-radius sequence   over an nn-element alphabet AA is a sequence in which every two elements of AA occur within distance kk of each other, where the distance is defined as the difference of indices of terms. The problem of finding (for given kk and nn) such sequences of a small length, motivated by some problems occurring in large data transfer, has been investigated by several authors recently. In this paper we consider a slight modification of the problem. We change the definition of the distance between terms of the sequence by computing it as if the terms were placed on a circle. The length of the shortest such sequence is denoted by gk(n)gk(n).We investigate sequences of radius linear in the alphabet size. For some values of c<1c<1 and sufficiently large nn we find the exact values of gcn(n)gcn(n) by providing direct constructions of optimal sequences. In the constructions we use Singer difference sets. Moreover, we give a nontrivial general lower bound for gcn(n)gcn(n).