### Perfect Necklaces

**2016-01-29**

1601.07975 | math.CO

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.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2018-10-29**

1810.12275 | math.CO

An abelian anti-power of order $k$ (or simply an abelian $k$-anti-power) is a
concatenation of $k$ c… show more

**2018-12-18**

1812.07330 | cs.DM

Two words are $k$-binomially equivalent whenever they share the same
subwords, i.e., subsequences, o… show more

**2019-03-13**

1903.05442 | cs.FL

We consider a certain natural generalization of de Bruijn words, and use it
to compute the exact max… show more

**2019-04-22**

1904.10028 | math.CO

Rich words are characterized by containing the maximum possible number of
distinct palindromes. Seve… show more

**2019-04-25**

1904.11334 | cs.DM

A two-dimensional ($2$D) word is a $2$D palindrome if it is equal to its
reverse and it is an HV-pal… show more

**2018-10-25**

1810.11081 | cs.FL

We study the factor complexity and closure properties of automatic sequences
based on Parry or Bertr… show more

**2019-03-30**

1904.00248 | cs.DM

The length $a(n)$ of the longest common subsequence of the $n$'th Thue-Morse
word and its bitwise co… show more

**2018-07-19**

1807.07208 | cs.FL

In this paper we consider the notion of normality of sequences in shifts of
finite type. A sequence … show more

**2018-07-22**

1807.08321 | math.DS

Given an infinite word $w$ from a uniquely ergodic subshift $L$, we can
associate to it a number $\n… show more

**2017-05-24**

1705.08747 | cs.FL

The second author introduced with I. T\"orm\"a a two-player word-building
game [Playing with Subshif… show more

**2017-12-15**

1712.05876 | cs.DS

We present a new recursive generation algorithm for prefix normal words.
These are binary strings wi… show more

**2018-04-09**

1804.02844 | math.NT

We give metric theorems for the property of Borel normality for real numbers
under the assumption of… show more

**2019-06-09**

1906.03689 | cs.DM

We show that the number of length-$n$ words over a $k$-letter alphabet having
no even palindromic pr… show more

**2014-04-01**

1404.2824 | cs.FL

A prefix normal word is a binary word with the property that no substring has
more 1s than the prefi… show more

**2015-10-02**

1510.00634 | cs.DS

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced
the idea of an Abelian … show more

**2016-01-18**

1601.04661 | cs.FL

A cost Markov chain is a Markov chain whose transitions are labelled with
non-negative integer costs… show more

**2018-01-26**

1801.08707 | cs.LO

Let $\frac{p}{q}$ be a rational number. Numeration in base $\frac{p}{q}$ is
defined by a function th… show more