Perfect necklaces

DOI10.1016/J.AAM.2016.05.002zbMATH Open1386.68119arXiv1601.07975OpenAlexW2911532181MaRDI QIDQ308973FDOQ308973

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

Publication date: 6 September 2016

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

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.

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

Recommendations

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

zbMATH Keywords

combinatorics on wordsnecklacesde Bruijn wordsstatistical tests of finite size

Mathematics Subject Classification ID

Combinatorics on words (68R15)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Fisher, Neyman, and the Creation of Classical Statistics
• Algorithmic Randomness and Complexity
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automatic Sequences
• Title not available (Why is that?)
• The definition of random sequences
• Distribution modulo one and Diophantine approximation
• On extending de Bruijn sequences
• The Construction of Decimals Normal in the Scale of Ten
• Title not available (Why is that?)
• TestU01
• The origins of combinatorics on words

Cited In (7)

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

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)