Perfect necklaces

DOI10.1016/J.AAM.2016.05.002MaRDI QIDQ308973zbMATHOpenAlexFDO

Authors Nicolás Alvarez, Verónica Becher, Pablo A. Ferrari, Sergio Yuhjtman

Publication date 6 September 2016

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.07975

zbMATH Keywords

combinatorics on wordsnecklacesde Bruijn wordsstatistical tests of finite size

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Abstract: 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.

Recommendations

• Generating necklaces
• Difference necklaces
• A dynamical approach to necklaces and words
• Publication:4952625
• scientific article; zbMATH DE number 1305469

Cites work

• scientific article; zbMATH DE number 434890 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 1024080 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• Algorithmic randomness and complexity.
• Automatic Sequences
• Distribution modulo one and Diophantine approximation
• Fisher, Neyman, and the creation of classical statistics.
• On extending de Bruijn sequences
• TestU01
• The Construction of Decimals Normal in the Scale of Ten
• The definition of random sequences
• The origins of combinatorics on words

Cited in

(8)

• Lyndon pairs and the lexicographically greatest perfect necklace
• Normal numbers and nested perfect necklaces
• Difference necklaces
• On extremal factors of de Bruijn-like graphs
• Extending de Bruijn sequences to larger alphabets
• Deterministic pushdown automata can compress some normal sequences
• Insertion in constructed normal numbers
• Automatic Kolmogorov complexity, normality, and finite-state dimension revisited

Describes a project that uses

Uses Software

• TestU01

This page was built for publication: Perfect necklaces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q308973)