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?


  • $\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


You must log in to answer this question.

Browse other questions tagged .