8
$\begingroup$

This question was already asked earlier at MSE.

Let $M$ denote the sequence of values of $\mu(n)$, the Möbius function which begins $M = (1,-1,-1,0,-1,1,-1,0,\dotsc)$. The questions below concern patterns that may or may not arise within $M$.

Questions: (1) It's easy to find palindromes in $M$ if we are free to choose the starting point. For example, the values from $n=102$ through $n=110$ yield the length $9$ palindrome $(-1,-1,0,-1,1,-1,0,-1,-1)$. However, the existence of a palindrome of any length greater than $1$ beginning at $n=1$ seems far fetched. Can it be proved that none exists? In this regard, is it also true that for large $n$, the sum $\sum_{k=1}^{k=n} \mu(k) \mu(n+1-k)$ is small when compared to $\sum_{k=1}^{k=n} \mu(k)^2$?

(2) Although $M$ is perhaps best known for its random aspects, it does at least have some predictable features. For example, it vanishes on certain arithmetic progressions including $\mu(4n)= 0$. This shows that the string $1111$ does not appear anywhere in $M$. [All strings and substrings are consecutive]. Let's abbreviate f.s. = forbidden (sub)sequence to be any such finite string that does not appear in $M$. Of course, any extension of an f.s. such as $01111$ or $1111{-}1$ is likewise forbidden so define a minimal f.s. to be one which contains no shorter f.s. inside it. For instance, each length $4$ string drawn from $+1,-1$ is a minimal f.s. since (i) it's forbidden and (ii) one checks that all such length $3$ strings do in fact occur.

What can one say about the collection of all minimal forbidden sequences? In particular, is it possible that there are only finitely many of them?

Thanks!

$\endgroup$
4
  • $\begingroup$ How would you decide among the strings zw, where z is a string of n zeros and w is a shorter string which has been found to exist? I am not holding out hope for a finite classification of forbidden strings. Gerhard "Not Even For Binary Alphabet" Paseman, 2018.07.25. $\endgroup$ Jul 25, 2018 at 19:40
  • $\begingroup$ The link goes to a question that doesn't seem in any way related. $\endgroup$ Jul 25, 2018 at 22:22
  • $\begingroup$ @GerryMyerson Fixed. $\endgroup$ Jul 26, 2018 at 5:29
  • $\begingroup$ I believe the answer to the last question is no. Consider a string $11100...01$ with the number of zeros divisible by $4$. For reasons the same as for $1111$ this pattern cannot occur, but removing any character should lead to a string which appears infinitely often (though I can't prove it myself). $\endgroup$
    – Wojowu
    Aug 11, 2018 at 15:58

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.