ML p(r)ior | Perfect Necklaces

### 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.

Highlights - Most important sentences from the article

# 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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

2019-04-22
1904.10028 | math.CO

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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

Highlights - Most important sentences from the article

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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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 Highlights - Most important sentences from the article 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