Algorithmic classification of noncorrelated binary pattern sequences

JOURNAL OF NUMBER THEORY

卷:223

Article

Konieczny, Jakub^1,2 

[1] Claude Bernard Univ Lyon 1, Camille Jordan Inst, 43 Blvd 11 Novembre 1918, F-69622 Villeurbanne, France

[2] Jagiellonian Univ Krakow, Fac Math & Comp Sci, Lojasiewicza 6, PL-30348 Krakow, Poland

关键词: Pattern sequence;    Automatic sequence;    Regular sequence;    Correlation;    Spectral measure;    Thue-Morse sequence;    Rudin-Shapiro sequence;   

DOI  :  10.1016/j.jnt.2020.10.008

来源: Elsevier

【 摘 要 】

The main subject of this paper are binary pattern sequences, that is, sequences of the form (-1)(#(n,A)) where A is a set of strings of 0s and 1s, and #(n, A) denotes the total number of times patterns from A appear in the binary expansion of n. A sequence is said to be noncorrelated if the corresponding spectral measure is equal to the Lebesgue measure. We show that it is possible to algorithmically verify if a given binary pattern sequence is noncorrelated. As an application, we compute that there are exactly 2272 noncorrelated binary pattern sequences of length <= 4. If we restrict our attention to patterns that do not end with 0, we put forward a sufficient condition for a pattern sequence to be noncorrelated. We conjecture that this condition is also necessary, and verify this conjecture for lengths <= 5. (C) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free