<abstract xmlns="http://www.w3.org/1999/xhtml">

<p>Although automatic sequences are very simple algorithmically, some of them have pseudo-random properties. In particular, some automatic sequences such as the Golay–Shapiro sequence are known to be 2-uncorrelated, meaning that they have the same correlations of order 2 as a uniform random sequence. However, the existence of <italic>ℓ</italic>-uncorrelated automatic sequences (for <italic>ℓ</italic> ⩾ 3) was left as an open question in a recent paper of Marcovici, Stoll and Tahay. We exhibit binary block-additive sequences that are 3-uncorrelated and, with the help of analytical results supplemented by an exhaustive search, we present a complete picture of the correlation properties of binary block-additive sequences of rank <italic>r</italic> ⩽ 5, and ternary sequences of rank <italic>r</italic> ⩽ 3.</p>
</abstract>

Although automatic sequences are very simple algorithmically, some of them have pseudo-random properties. In particular, some automatic sequences such as the Golay–Shapiro sequence are known to be 2-uncorrelated, meaning that they have the same correlations of order 2 as a uniform random sequence. However, the existence of ℓ-uncorrelated automatic sequences (for ℓ ⩾ 3) was left as an open question in a recent paper of Marcovici, Stoll and Tahay. We exhibit binary block-additive sequences that are 3-uncorrelated and, with the help of analytical results supplemented by an exhaustive search, we present a complete picture of the correlation properties of binary block-additive sequences of rank r ⩽ 5, and ternary sequences of rank r ⩽ 3.

Finding automatic sequences with few correlations

Pure Mathematics and Applications

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

{"article-title":"Finding automatic sequences with few correlations"}

Although automatic sequences are very simple algorithmically, some of them have pseudo-random properties. In particular, some automatic sequences such as the...

Finding automatic sequences with few correlations

Published Online: Jun 18, 2022

Page range: 75 - 81

Received: Mar 31, 2022

Accepted: May 15, 2022

DOI: https://doi.org/10.2478/puma-2022-0012

Keywords
combinatorics on words, automata sequence, well-distributed sequence

© 2022 Vincent Jugé et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Finding automatic sequences with few correlations

Published Online: Jun 18, 2022

Page range: 75 - 81

Received: Mar 31, 2022

Accepted: May 15, 2022

DOI: https://doi.org/10.2478/puma-2022-0012

Keywordscombinatorics on words, automata sequence, well-distributed sequence

© 2022 Vincent Jugé et al., published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Keywords
combinatorics on words, automata sequence, well-distributed sequence