Constructing $k$-radius sequences

Abstract:

An $n$-ary $k$-radius sequence is a finite sequence of elements taken from an alphabet of size $n$ such that any two distinct elements of the alphabet occur within distance $k$ of each other somewhere in the sequence. These sequences were introduced by Jaromczyk and Lonc to model a caching strategy for computing certain functions on large data sets such as medical images. Let $f_k(n)$ be the shortest length of any $k$-radius sequence. We improve on earlier estimates for $f_k(n)$ by using tilings and logarithms. The main result is that $f_k(n)\sim \frac {1}{k}\binom {n}{2}$ as $n\rightarrow \infty$ whenever there exists a tiling of $\mathbb {Z}^{\pi (k)}$ by a certain cluster of $k$ hypercubes. In particular this result holds for infinitely many $k$, including all $k\le 194$ and all $k$ such that $k+1$ or $2k+1$ is prime. For certain $k$, in particular when $2k+1$ is prime, we get a sharper error term using the theory of logarithms.