
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 alphabet and 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 which are 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.
Combinatorics on Words, FOS: Computer and information sciences, Statistical Tests of Finite Size, Combinatorics on words, Discrete Mathematics (cs.DM), De Bruijn Words, necklaces, Probability (math.PR), statistical tests of finite size, Mathematics - Statistics Theory, Statistics Theory (math.ST), de Bruijn words, Necklaces, FOS: Mathematics, Mathematics - Combinatorics, https://purl.org/becyt/ford/1.2, combinatorics on words, Combinatorics (math.CO), https://purl.org/becyt/ford/1, Mathematics - Probability, Computer Science - Discrete Mathematics
Combinatorics on Words, FOS: Computer and information sciences, Statistical Tests of Finite Size, Combinatorics on words, Discrete Mathematics (cs.DM), De Bruijn Words, necklaces, Probability (math.PR), statistical tests of finite size, Mathematics - Statistics Theory, Statistics Theory (math.ST), de Bruijn words, Necklaces, FOS: Mathematics, Mathematics - Combinatorics, https://purl.org/becyt/ford/1.2, combinatorics on words, Combinatorics (math.CO), https://purl.org/becyt/ford/1, Mathematics - Probability, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
