Bounds for the discrete correlation of infinite sequences on k symbols and generalized Rudin-Shapiro sequences
arXiv:0812.3186 · doi:10.4064/aa140-4-5
Abstract
Motivated by the known autocorrelation properties of the Rudin-Shapiro sequence, we study the discrete correlation among infinite sequences over a finite alphabet, where we just take into account whether two symbols are identical. We show by combinatorial means that sequences cannot be "too" different, and by an explicit construction generalizing the Rudin-Shapiro sequence, we show that we can achieve the maximum possible difference.
Improved Introduction and new Section 6 (Lovasz local lemma)