CONICET | Buscador de Institutos y Recursos Humanos

We introduce a variant of de~Bruijn words that we call perfect necklaces.Fix a finite alphabet. Recall that a word is a finite sequence of symbols in the alphabetand a circular word, or necklace, is the equivalence class of a word under rotations.For positive integers $k$ and $n$, we call a necklace $(k,n)$-perfect if each word of length $k$ occurs exactly~$n$ times at positions whichare different modulo~$n$ for any convention on the starting point.We call a necklace perfect if it is $(k,k)$-perfect for some~$k$.We prove that every arithmetic sequence with difference coprime with the alphabet size induces a perfect necklace.In particular, the concatenation of all words of the same length in lexicographic order yields a perfect necklace.For each $k$ and $n$, we give a closed formula for the number of $(k,n)$-perfect necklaces.Finally, we prove that every infinite periodic sequence whose period coincides with some $(k,n)$-perfect necklace for any $n$, passes all statistical tests of size up to~$k$, but not all larger tests. This last theorem motivated this work.