1
$\begingroup$

Let M denote the sequence of values of $\mu$(n) , the Mobius function from elementary number theory. A large table is available at OEIS [A008683] . The sequence begins M = (1,-1,-1,0,-1,1,-1,0,0,1,...) and is known to be quite irregular. This suggests that it will be difficult to find many patterns in M which hold up over significant length scales.

Questions: (1) Is there any initial interval [1,n] with n$\ge$2, for which the Mobius values form a palindrome [i.e. $\mu$(1)=$\mu$(n), $\mu$(2)=$\mu$(n-1), etc. ] ? This seems highly unlikely and even rash but is there a disproof? $\quad$In any case, it would be interesting to know how close the sum$\qquad$ $\qquad$ $\quad$ $\sum_{k=1}^n$ $\mu$(k)$\mu$(n+1-k)$\;$ can be to $\sum_{k=1}^n$ $\mu$(k)$^2$ $\,$.

(2) By contrast, it is easy to find palindromes if we are allowed to vary the starting point. For example, the interval [102,110] , with values (-1,-1,0,-1,1,-1,0,-1,-1), $\,$ already provides a length 9 palindrome. In fact, is there any absolute bound at all on the length of such a palindromic interval? [Note that the Chinese Remainder Theorem can be used to find n with 2$^2$|n, 3$^2$|(n+1), 5$^2$|(n+2), etc. leading to a long stretch of 0's in M. To avoid this trivial case, we require that the palindrome not be identically zero.]

(3) Despite its irregular appearance, M cannot fully mimic a random sequence drawn from {0,1,-1}. In fact, it is constrained in many ways. For example, each string of four (all strings and substrings are consecutive) contains a multiple of 4 and leads to a corresponding Mobius value of zero. Thus, (1,1,1,1) forms a forbidden subsequence in M. [Let f.s. = forbidden (sub)sequence = any finite string which does not occur in M .]$\,$Of course, any extension of an f.s., such as (0,1,1,1,1) or (1,1,1,1,-1), is likewise forbidden so let's define a minimal f.s. to be one that contains no other f.s. within it. For instance, each length 4 string taken from {1,-1} is a minimal f.s. because (i) it's forbidden and (ii) a check (n$\le$200 suffices) shows that all such length 3 substrings do in fact arise. $\qquad$ 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$ Take a look at $\lambda(n) = (-1)^{\Omega(n)}$ (so that $\mu(n ) =|\mu(n)| \lambda(n)$) $\endgroup$
    – reuns
    Sep 28, 2017 at 21:28
  • $\begingroup$ If you omit the zeros you get a sequence appearing totally random oscillating between $-1$ and $1$. I am not sure whether the sequence exhibits good pseudo-randomness, but experiments with high starting numbers (lets say $10^{30}$) indicate that it can be used very well to generate pseudo-random bit-strings. It also appears that arbitary long blocks of zeros as well as arbitary long blocks of ones occur (if we convert $-1$ to $0$) $\endgroup$
    – Peter
    Sep 28, 2017 at 21:30
  • $\begingroup$ How many entries did you check without finding an overall-palindrome ? $\endgroup$
    – Peter
    Sep 28, 2017 at 21:37
  • $\begingroup$ thanks for the replies --only checked by hand (so not very far) but it is a near certainty that no palindrome exists starting from n=1 $\endgroup$
    – user2052
    Oct 15, 2017 at 17:00

1 Answer 1

Reset to default
0
$\begingroup$

(2) As you say, there are arbitrarily long sequences of the form $0, \ldots, 0$. If you include the entries before and after these, I would think that a good fraction of them will be palindromes $(1, 0, \ldots, 0, 1)$ or $(-1, 0, \ldots, 0, -1)$.

The first palindrome of length $n$ (from $1$ to $20$) starts at the following positions: $$ \matrix{ n & | & 1 &2 &3 &4 &5 &6 &7 &8 &9 &10 &11 &12 &13 &14 &15 &16 &17 &18 &19 &20\cr position & | & 1 &2 &3 &62 &4 &61 &15 &115 &14 &116 &13 &831 &12 &37173 &597 &457472 &596 &2955661 &595 &6495574\cr}$$

EDIT: See OEIS sequence A293041.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .