Perfect necklaces

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Alvarez, N., Becher, V., Ferrari, P.A., Yuhjtman, S.A.
Formato:	JOUR
Materias:	Combinatorics on words de Bruijn words Necklaces Statistical tests of finite size Statistical tests De Bruijn Finite alphabet Finite size Infinite periodic sequence Lexicographic order Positive integers Equivalence classes
Acceso en línea:	http://hdl.handle.net/20.500.12110/paper_01968858_v80_n_p48_Alvarez
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	todo:paper_01968858_v80_n_p48_Alvarez
record_format	dspace
spelling	todo:paper_01968858_v80_n_p48_Alvarez2023-10-03T15:09:49Z Perfect necklaces Alvarez, N. Becher, V. Ferrari, P.A. Yuhjtman, S.A. Combinatorics on words de Bruijn words Necklaces Statistical tests of finite size Statistical tests Combinatorics on words De Bruijn Finite alphabet Finite size Infinite periodic sequence Lexicographic order Necklaces Positive integers Equivalence classes 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 some k and some n, passes all statistical tests of size up to k, but not all larger tests. This last theorem motivated this work. © 2016 Elsevier Inc. All rights reserved. Fil:Becher, V. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Ferrari, P.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Yuhjtman, S.A. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. JOUR info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar http://hdl.handle.net/20.500.12110/paper_01968858_v80_n_p48_Alvarez
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Combinatorics on words de Bruijn words Necklaces Statistical tests of finite size Statistical tests Combinatorics on words De Bruijn Finite alphabet Finite size Infinite periodic sequence Lexicographic order Necklaces Positive integers Equivalence classes
spellingShingle	Combinatorics on words de Bruijn words Necklaces Statistical tests of finite size Statistical tests Combinatorics on words De Bruijn Finite alphabet Finite size Infinite periodic sequence Lexicographic order Necklaces Positive integers Equivalence classes Alvarez, N. Becher, V. Ferrari, P.A. Yuhjtman, S.A. Perfect necklaces
topic_facet	Combinatorics on words de Bruijn words Necklaces Statistical tests of finite size Statistical tests Combinatorics on words De Bruijn Finite alphabet Finite size Infinite periodic sequence Lexicographic order Necklaces Positive integers Equivalence classes
description	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 some k and some n, passes all statistical tests of size up to k, but not all larger tests. This last theorem motivated this work. © 2016 Elsevier Inc. All rights reserved.
format	JOUR
author	Alvarez, N. Becher, V. Ferrari, P.A. Yuhjtman, S.A.
author_facet	Alvarez, N. Becher, V. Ferrari, P.A. Yuhjtman, S.A.
author_sort	Alvarez, N.
title	Perfect necklaces
title_short	Perfect necklaces
title_full	Perfect necklaces
title_fullStr	Perfect necklaces
title_full_unstemmed	Perfect necklaces
title_sort	perfect necklaces
url	http://hdl.handle.net/20.500.12110/paper_01968858_v80_n_p48_Alvarez
work_keys_str_mv	AT alvarezn perfectnecklaces AT becherv perfectnecklaces AT ferraripa perfectnecklaces AT yuhjtmansa perfectnecklaces
_version_	1807322523694530560

Perfect necklaces

Ejemplares similares