Discrete correlations of order 2 of generalized Golay-Shapiro sequences: a combinatorial approach

zbMATH Open1470.11043arXiv2006.13162MaRDI QIDQ4987429FDOQ4987429

Authors: Irène Marcovici, Thomas Stoll, Pierre-Adrien Tahay 

Publication date: 3 May 2021

Abstract: We introduce a family of block-additive automatic sequences, that are obtained by allocating a weight to each couple of digits, and defining the $n$th term of the sequence as being the total weight of the integer $n$ written in base $k$. Under an additional difference condition on the weight function, these sequences can be interpreted as generalised Rudin-Shapiro sequences, and we prove that they have the same correlations of order 2 as sequences of symbols chosen uniformly and independently at random. The speed of convergence is very fast and is independent of the prime factor decomposition of $k$. This extends recent work of Tahay. The proof relies on direct observations about base-$k$ representations of integers and combinatorial considerations. We also provide extensions of our results to higher-dimensional block-additive sequences.

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

Recommendations

• Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size
• Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin–Shapiro sequences
• Correlation functions of higher-dimensional automatic sequences
• On the correlation of binary sequences. II
• Statistical properties of the arithmetic correlation of sequences

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Radix representation; digital problems (11A63) Automata sequences (11B85)

Cites Work

• Orthogonal arrays. Theory and applications
• Automatic Sequences
• Substitution sequences in \mathbb{Z}^{d} with a non-simple Lebesgue component in the spectrum
• Generalized Rudin-Shapiro sequences
• Une nouvelle propriété des suites de Rudin-Shapiro. (A new property of Rudin-Shapiro sequences)
• Prime numbers along Rudin-Shapiro sequences
• Block additive functions on the Gaussian integers
• Complexity of generalized Rudin-Shapiro sequences
• The Rudin-Shapiro sequence and similar sequences are normal along squares
• On a Golay-Shapiro-like sequence
• Correlation and spectral properties of higher-dimensional paperfolding and Rudin–Shapiro sequences
• Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin–Shapiro sequences
• Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size

Cited In (5)

• Correlation functions of higher-dimensional automatic sequences
• On a Golay-Shapiro-like sequence
• Discrete correlation of order 2 of generalized Rudin-Shapiro sequences on alphabets of arbitrary size
• Pseudorandom sequences derived from automatic sequences
• A Boolean functions view on the Golay-Rudin-Shapiro sequence

This page was built for publication: Discrete correlations of order 2 of generalized Golay-Shapiro sequences: a combinatorial approach

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